数据结构 - 二叉树

1. 树(Tree)

(1) 基础概念

1> 节点

节点、根节点、父节点、子节点、兄弟节点

2> 树、子树

一棵树可以没有任何节点，称为空树

一棵树可以只有1个节点，也就是只有根节点

子树、左子树、右子树

3> 度(degree)

节点的度：子树的个数

树的度：所有节点度中的最大值

4> 叶子节点(leaf)

叶子节点：度为0的节点

非叶子节点：度不为0的节点

5> 层数(level)

层数：根节点在第1层，根节点的子节点在第2层，以此类推

6> 深度(depth)、高度(height)

节点的深度：从根节点到当前节点的唯一路径上的节点总数

节点的高度：从当前节点到最远叶子节点的路径上的节点总数

树的深度：所有节点深度中的最大值

树的高度：所有节点高度中的最大值

树的深度等于树的高度

二叉树

(2) 树的种类

有序树：树中任意节点的子节点之间有顺序关系

无序树(自由树)：树中任意节点的子节点之间没有顺序关系

森林：由m(m≥0)棵互不相交的树组成的集合

2. 二叉树(Binary Tree)

(1) 基础概念

1> 二叉树的特点

每个节点的度最大为2 (最多拥有2棵子树)

左子树和右子树是有顺序的

即使某节点只有一棵子树，也要区分左右子树

2> 二叉树的性质

非空二叉树的第i层，最多有 $2^{(i-1)}$ 个节点(i≥1)

在高度为h的二叉树上最多有 $2^{h}$ - 1个节点(h≥1)

对于任何一棵非空二叉树，如果叶子节点个数为 $n_0$ ，度为1的节点个数为 $n_1$ ，度为2的节点个数为 $n_2$

则有: $n_0$ = $n_2$ + 1

二叉树的节点总数n = $n_0$ + $n_1$ + $n_2$

二叉树的边数T = $n_1$ +2* $n_2$ = n-1 = n0+ $n_1$ + $n_2$ -1

(2) 真二叉树(Proper Binary Tree)

真二叉树：所有节点的度要么为0，要么为2

真二叉树、满二叉树

(3) 满二叉树(Full Binary Tree)

满二叉树：最后一层节点的度都为0，其他节点的度都为2

在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多

满二叉树一定是真二叉树，真二叉树不一定是满二叉树

假设满二叉树的高度为h(h≥1)，那么

第i层的节点数量： $2^{i}$ - 1

叶子节点数量： $2^{h}$ - 1

总节点数量n

n= $2^{h}$ - 1= $2^{0}$ + $2^{1}$ + $2^{2}$ + ... + $2^{(h-1)}$

h = $log_2{(n+1)}$

(4) 完全二叉树(Complete Binary Tree)

1> 概念

完全二叉树：对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应

叶子节点只会出现最后2层，最后1层的叶子结点都靠左对齐

完全二叉树从根结点至倒数第2层是一棵满二叉树

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

完全二叉树

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 ≤ $log_2{n}$ < h

h = floor( $log_2{n}$ ) + 1

【floor是向下取整，ceiling是向上取整】

一棵有 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，它无右子节点

3. 面试题

Q: 如果一棵完全二叉树有768个节点，求叶子节点的个数？

解题步骤一：

假设叶子节点个数为 $n_0$ ，度为1的节点个数为 $n_1$ ，度为2的节点个数为 $n_2$
总结点个数n = $n_0$ + $n_1$ + $n_2$ ，而且 $n_0$ = $n_2$ + 1
n = 2 $n_0$ + $n_1$ - 1

解题步骤二：

完全二叉树的 $n_1$ 要么为0，要么为1：
$n_1$ 为1时，n = 2 $n_0$ ，n必然是偶数
叶子节点个数 $n_0$ = n / 2，非叶子节点个数 $n_1$ + $n_2$ = n / 2
$n_1$ 为0时，n = 2 $n_0$ - 1，n必然是奇数
叶子节点个数 $n_0$ = (n + 1) / 2，非叶子节点个数 $n_1$ + $n_2$ = (n - 1) / 2

解题步骤三：

叶子节点个数 $n_0$ = floor((n + 1) / 2) = ceiling(n / 2)

非叶子节点个数 $n_1$ + $n_2$ = floor(n / 2) = ceiling((n - 1) / 2)

floor((n + 1) / 2) 即 (n + 1) / 2 或 (n + 1) >> 1

得出答案：

因此叶子节点个数为 768 / 2 = 384

数据结构 - 二叉树

1. 树(Tree)

(1) 基础概念

1> 节点

2> 树、子树

3> 度(degree)

4> 叶子节点(leaf)

5> 层数(level)

6> 深度(depth)、高度(height)

(2) 树的种类

2. 二叉树(Binary Tree)

(1) 基础概念

1> 二叉树的特点

2> 二叉树的性质

(2) 真二叉树(Proper Binary Tree)

(3) 满二叉树(Full Binary Tree)

(4) 完全二叉树(Complete Binary Tree)

1> 概念

2> 性质

3. 面试题

推荐阅读更多精彩内容