二叉树
树(Tree)的基本概念
节点
- 节点:
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、21、22、221、222、223
就是一颗子树。 - 左子树:左侧的子节点称为左子树,例如
21
是2
的左子树。 - 右子树:右侧的子节点称为右子树,例如
22
是2
的右子树。
度
- 节点的度:子树的个数,即子节点的个数,就是节点的度,例如根节点
1
有5
个子节点,所以根节点1
的度是5
。 - 树的度:所有节点度的
最大值
,上图中节点度最大的是根节点, 所以这棵树的度是5
。 - 叶子节点:度为
0
的节点,即没有子节点的节点。 - 非叶子节点:度不为
0
的节点,即有子节点的节点。
深度&高度
- 层数:根节点第一层,根节点的子节点在第
2
层,以此类推(有些教程是从第0层开始计算)。 节点的深度:从根节点到当前节点的唯一路径上的节点总数。
- 节点
2
的深度:1->2,经历2
个节点,所以深度为2
。 - 节点
223
的深度:1->2->22->223,经历4
个节点,所以深度是4
。
- 节点
节点的高度:从当前节点到最远叶子节点的路径上的节点总数。
- 节点
2
的高度:2->22->221,经历3
个节点,所以深度是3 - 节点
223
的深度: 223,只有一个节点,所以深度是1
。
- 节点
树的深度:所有节点深度的最大值。
- 1->2->22->221,所以树的深度是
4
。
- 1->2->22->221,所以树的深度是
树的高度:所有节点高度的最大值。
- 1->2->22->221,所以树的高度是
4
。
- 1->2->22->221,所以树的高度是
树的分类
- 有序树:树种任意节点的子节点之间有顺序关系,即两个树所有的值都一样,但是其中的子节点顺序不一样,就是两颗不同的有序树。
- 无序树:树中任意节点的子节点之间没有顺序关系,也称为自由树。
- 森林:由m(m >= 0)颗互不相交的树组成的集合。
二叉树
二叉树的性质
- 每个节点的
度
最大为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。
二叉树的种类
真二叉树
- 所有节点的
度
要么为0
,要么为2
,即没有只有一个子节点的节点。
满二叉树
- 所有节点的
度
要么为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)
- n =
完全二叉树
- 叶子节点只会出现最后
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
为向下取整