小码哥《恋上数据结构与算法》笔记(七):二叉树
我的Github地址
小码哥《恋上数据结构与算法》笔记
极客时间《iOS开发高手课》笔记
iOS大厂面试高频算法题总结
iOS面试资料汇总
参考:小码哥数据结构与算法(七): 树
数据结构和算法动态可视化
一、树(Tree)的基本概念
1、节点
- 节点:
1、2、3、4、5、6、21、22、31、51、52、61、221、222、223
- 根节点:
1
- 父节点:
1
是2、3、4、5、6
的父节点,2
是21、22
的父节点,以此类推。
- 子节点:与父节点相反,
2、3、4、5、6
是1
的子节点,21、22
是2
的子节点,以此类推。
- 兄弟节点:同一个父节点下的子节点互为兄弟节点,例如上图中的
21
和22
是兄弟节点,但是22
和31
虽然都在同一层,而父节点不同,所以不是兄弟节点。
- 空树:一棵树没有任何节点,包括没有根节点。
- 一棵树可以只有一个节点,也就是根节点。
2、子树
- 子树:一棵树可以有很多节点,而其中除了整体是一颗树外,其中的子节点也可以单独看成一棵树,例如
2、21、22、221、222、223
就是一颗子树。
- 左子树:左侧的子节点称为左子树,例如
21
是2
的左子树。
- 右子树:右侧的子节点称为右子树,例如
22
是2
的右子树。
2、度
- 节点的度:子树的个数,即子节点的个数,就是节点的度,例如根节点
1
有5
个子节点,所以根节点1
的度是5
。
- 树的度:所有节点度的
最大值
,上图中节点度最大的是根节点, 所以这棵树的度是5
。
- 叶子节点:度为
0
的节点,即没有子节点的节点。
- 非叶子节点:度不为
0
的节点,即有子节点的节点。
3、深度&高度
- 层数:根节点第一层,根节点的子节点在第
2
层,以此类推(有些教程是从第0层开始计算)。
- 节点的深度:从根节点到当前节点的唯一路径上的节点总数。
- 节点
2
的深度:1->2,经历2
个节点,所以深度为2
。
- 节点
223
的深度:1->2->22->223,经历4
个节点,所以深度是4
。
- 节点的高度:从当前节点到最远叶子节点的路径上的节点总数。
- 节点
2
的高度:2->22->221,经历3
个节点,所以深度是3
- 节点
223
的深度: 223,只有一个节点,所以深度是1
。
- 树的深度:所有节点
深度
的最大值
。
- 树的高度:所有节点
高度
的最大值
。
4、树的分类
- 有序树:树种任意节点的子节点之间有顺序关系,即两个树所有的值都一样,但是其中的子节点顺序不一样,就是两颗不同的有序树。
- 无序树:树中任意节点的子节点之间没有顺序关系,也称为自由树。
- 森林:由m(m >= 0)颗互不相交的树组成的集合。
二、二叉树
1、二叉树的性质
- 每个节点的
度
最大为2
,即最多拥有2
颗子树。
左子树
和右子树
是有顺序
的,比如所有节点左子树
小于右子树
。
- 即使某节点只有一颗子树,也要区分左右子树。
- 非空二叉树的第
i
层,最多有2^(i-1)
个节点(i >= 1)。
- 高度为
h
的二叉树最多有2^h - 1
个节点(h >= 1)。
- 对于任意一颗
非空二叉树
,如果叶子节点
个数为n0
,度
为2
的节点个数为n2
,则有:n0 = n2 + 1
。
- 假设度为1 的节点个数为n1,那么二叉树的总结点n = n0 + n1 + n2
二叉树的边数T = n1 + 2 * n2,这是因为n1的每个节点下有1个子节点,所以边是n1,n2的每一个节点都有2个子节点所以是n2 * 2。反过来看,因为所有的节点上面都有一条边,只有根节点上没有边。所以,二叉树的边数T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1。即: n1 + 2 * n2 = n0 + n1 + n2 - 1 可以推出 n0 = n2 + 1。
2、二叉树的种类
a、真二叉树
- 所有节点的
度
要么为0
,要么为2
,即没有只有一个子节点的节点。
b、满二叉树
- 所有节点的
度
要么为0
,要么为2
。且所有的叶子节点
都在最后一层。
- 在
同样高度
的二叉树中,满二叉树
的叶子节点
数量最多
,总结点
数量最多
。
- 满二叉树
一定是
真二叉树,真二叉树不一定是
满二叉树。
- 假设满二叉树的高度为h(h >= 1),那么:
- 第i层的节点数量:
2^(i - 1)
- 叶子节点数量:
2^h - 1
- 总结点数量 n:
- n =
2^h - 1 = 2^0 + 2^1 + 2^2 + 2^3 +...+ h^(h - 1)
- h =
log2(n + 1)
c、完全二叉树
- 叶子节点只会出现最后
2
层,最后1
层的叶子节点都靠左
对齐。
- 完全二叉树从
根节点
至倒数第2层
是一颗满二叉树
。
- 满二叉树
一定是
完全二叉树,完全二叉树不一定是
满二叉树。
- 度为
1
的节点只有左子树。
- 度为
1
的节点要么是1
个,要么是0
个。
- 同样节点数量的二叉树,完全二叉树的高度最小。
- 假设完全二叉树的高度为
h
(h >= 1),那么:
- 至少有
2^(h - 1)
个节点(2^0 + 2^1 + 2^2 + ... + 2^(h - 2) + 1)。
- 最多有
2^h - 1
个节点(2^0 + 2^1 + 2^2 + ... + 2^(h - 1), 满二叉树)。
- 总节点数量为 n:
- 2^(h - 1) <= n < 2^h
- h - 1 <= log2(n) < h
- h = floor(log2n) + 1
- 一个有
n
个节点的完整二叉树(n > 0),从上到下,从左到右对节点从1
开始编号,对任意第i
个节点:
- 如果
i = 1
,它是根节点
。
- 如果
i > 1
,它的父节点
编号为floor(i/2)
。
- 如果
2i <= n
,它的左子节点编号为2i
。
- 如果
2i > n
,它无
左子点。
- 如果
2i + 1 <= n
,他的右子节点编号为2i + 1
。
- 如果
2i + 1 > n
,它无
右子节点。
- 一个有
n
个节点的完整二叉树(n > 0), 从上到下,从左到右对节点从0
开始编号, 对任意第i
个节点:
- 如果
i = 0
,它是根节点
。
- 如果
i > 0
,它的父节点
编号为floor((i- 1)/2)
。
- 如果
2i + 1 <= n - 1
,它的左子节点编号为2i + 1
。
- 如果
2i + 1 > n - 1
,它无
左子点。
- 如果
2i + 2 <= n - 1
,他的右子节点编号为2i + 2
。
- 如果
2i + 2 > n - 1
,它无
右子节点。
三、leetcode算法题
总节点
数量为n
。
n
如果是偶数
,叶子节点
数量n0 = n / 2
。
n
如果是奇数
,叶子节点
数量n0 = (n + 1) / 2
。
- 可以一并写成:
n0 = floor((n + 1) / 2)
。
floor
为向下取整
。