文档章节

二叉树知识点

o
 osc_gu9d45li
发布于 2019/04/07 12:47
字数 720
阅读 8
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

概念

树:是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。

二叉树:是一种特殊的树。

结点的度:结点拥有的子树个数

叶结点(叶):度为0的结点,即没有儿子的结点

分支结点:度不为0的结点

兄弟结点:具有相同父亲的结点

树的度:树中最大的结点度

结点的层次:根为第一层,依次类推

深度:树中节点的最大层次

高度:从下往上数层数

如果根结点第0,层数=深度=高度-1
如果根结点第1,层数=深度=高度

特点

1、每个结点最多有两颗子树,结点的度最大为2。 
2、左子树和右子树是有顺序的,次序不能颠倒。 
3、即使某结点只有一个子树,也要区分左右子树。

类型

满二叉树:顾名思义,布满结点的树,从高到低,除了叶节点外,每一个结点都有左右子叶,且叶子结点都处在最底层的二叉树。

完全二叉树:比满二叉树少几个叶节点,除最底层外,其它各层结点数都达到最大个数,底层的叶子结点都是从左到右依次排布。

平衡二叉树(AVL树):空树或者它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树也都是平衡树。

二叉搜索树:空树或者二叉树的所有节点比他的左子节点大,比他的右子节点小。(左<=根<=右)

红黑树:不仅是具有二叉搜索树的属性,还具有平衡树的属性,有序且子树差不超过1,颜色规则:结点要么红要么黑,上下层结点红黑交替,根节点和特殊节点(即叶节点下面两个虚无的节点)是黑的,红节点的左右子节点是黑的,最重要的是从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

遍历方式

深度遍历前中后序三种

前序遍历:根结点->左子树->右子树

中序遍历:左子树->根结点->右子树

后序遍历:左子树->根结点->根节点

广度遍历

层次遍历:按层,从上到下,从左到右遍历。

扩展

红黑树插入结点问题

一般默认插入节点是红色的。

若插入以后树不符合颜色规则,则需要进行颜色调整。

若插入以后树已经不是一个平衡的二叉树,则需要进行结构调整。

结构调整过程包含两个基本操作:左旋(Rotate Left),右旋(RotateRight)

左旋

右旋

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
视图各种动画效果

自定义视图变换的各种动画效果。其中包括:CALayer、UIViewAnimation、CATransition、CABasicAnimation、CAKeyframeAnimation、CAAnimationGroup、CATransform3D各个知识点实现的动画效果,实...

匿名
2013/03/21
1.4K
0
高效 Java Web 开发框架--JessMA

JessMA 是功能完备的高性能 Full-Stack Web 应用开发框架,内置可扩展的 MVC Web 基础架构和 DAO 数据库访问组件(内部已提供了 Hibernate、MyBatis 与 JDBC DAO 组件),集成了 Action 拦截...

伤神小怪兽
2012/11/13
9.2K
3
iOS9系列专题6——iOS9其他适配注意点

iOS9适配注意点 一、后台定位类app适配点 在iOS8中,APP的定位服务apple就做了一些修改,需要用户申请相应的权限,并在info.plist文件中添加对应的键值。具体的做法在这篇博客中有详细的讲解...

珲少
2015/10/07
3.5K
3
Spring 源码分析(三) —— AOP(一)AOP原理

AOP概论 AOP(Aspect-Oriented Programming,面向切面的编程),谈起AOP,则一定会追溯到OOP(Object Oriented Programming,面向对象编程),因为AOP可以说是对OOP的补充和完善,而这一切的理...

水门-kay
2016/02/29
3.8K
2
Swift笔记-让你2小时学会Swift

过年不能闲着,一边学习Swift,一边写笔记,相信在有一定其他语言基础的情况下用1.5小时看完该文章即可掌握。然后再花30分钟打开XCode写个Demo. 生命中拿出2小时来认识一门语言,很值吧! 笔...

程序员孟帅
2016/02/10
6.6K
20

没有更多内容

加载失败,请刷新页面

加载更多

SQL 语句大全

点击上方“掌上编程”,选择“置顶或者星标” 优质文章第一时间送达! 一、基础 「1、说明:创建数据库」 CREATE DATABASE database-name    「2、说明:删除数据库」 drop database ...

GeneralMa
昨天
0
0
山东创睦网络科技有限公司:使用Python爬取全球新冠肺炎疫情数据

使用Python爬取全球新冠肺炎疫情数据 导入所需库包 获取实时数据的url 正式编写程序 查看输出结果 导入所需库包 在获取数据之前,我们需要先安装好所需的包requests和pandas: 1.如果是使用p...

osc_qv1fwke0
34分钟前
14
0
如何1年获得别人3年的工作经验(深度好文)

最近有同学问我,为什么你的工作年限不长,技术却这么厉害,我笑了笑,啥也没说。 我不是不想回答,是不知道怎么回答。在他们的定位可能就是,每方面都懂一点,遇到问题能够快速解决,就是比...

zhang_rick
今天
1
0
新基建带动行业

什么是“新基建”? 什么是“新基建”? 根据央视发布的信息来看,其涵盖了5G基站建设、新能源汽车充电桩、大数据中心、人工智能、工业互联网,特高压,城际以及城轨交通,涉及了七大领域和相...

osc_anefoz50
35分钟前
16
0
怕入错行?这群技术人写了本“择业指南”

计算机专业好找工作吗?哪些方向是当前的主流和热门方向呢? 计算机专业的你是不是还在为职业发展纠结犹豫呢? 刚经历完高考选专业的你是不是还在迷茫徘徊呢? 那么福利来啦! 《软件技术职业...

阿里云云栖号
35分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部