数据结构核心：树与二叉树详解

三、二叉树

二叉树的概念

二叉树是一棵特殊的树，是一个 n(n>=0) 个节点的有限集合，具有以下特征：

1. 每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点）。
2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成。
3. 二叉树的子树有左右之分，其次序不能任意颠倒。

从上图可以看出：

1. 二叉树不存在度大于 2 的结点。
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

注意：对于任意的二叉树都是由以下几种情况复合而成的。

特殊的二叉树

满二叉树

满二叉树指每一层的节点数量均达到最大值的二叉树。具体而言，若某二叉树的深度为 h，且其节点总数为 2^h - 1，则该树即为满二叉树。

对于一棵满二叉树而言，假设其高度为 h，节点总数为 N：

• 第一层有：2^0 个节点
• 第二层有：2^1 个节点
• 第三层有：2^2 个节点
• ...
• 第 h 层有：2^(h-1) 个节点

用 N 表示这棵二叉树的总节点数，则有 N = 2^0 + 2^1 + 2^2 + ... + 2^(h-1) = 2^h - 1。 所以也可得出 h = log₂N + 1，对于一棵二叉树而言其深度可以被近似为 h ≈ log₂N。

完全二叉树

完全二叉树：除最后一层外，每一层的节点数均达到最大值，最后一层的节点从左到右连续排列，缺失的节点只能在右侧。

对于完全二叉树，满足如下特征：

1. 叶子节点仅可能出现在最下两层，且最下层叶子一定靠左集中。
2. 适合用数组存储，无需额外空间记录指针，通过索引即可计算父子节点位置。
3. 不存在只有右子节点而无左子节点的节点，右子节点存在的前提是左子节点已存在。

注：满二叉树也被视为特殊的完全二叉树。

二叉树的性质

二叉树的性质围绕节点数、深度、子树关系及特殊类型展开，核心是'每个节点最多 2 个子节点'的结构约束。

所有二叉树的性质

1. 节点数与度数关系：若总节点数为 N，度为 0（叶子）、1、2 的节点数分别为 n₀、n₁、n₂，则 N = n₀ + n₁ + n₂，且 n₀ = n₂ + 1（叶子节点数比度为 2 的节点数多 1）。

   推导过程： 从总结点数角度考虑：N = n0 + n1 + n2 ① 从边的角度考虑：N 个结点的任意二叉树，总共有 N-1 条边。因为二叉树中每个结点都有父节点，根结点没有父节点，每个节点向上与其父节点之间存在一条边，因此 N 个结点的二叉树总共有 N-1 条边。 因为度为 0 的结点没有孩子，故度为 0 的结点不产生边；度为 1 的结点只有一个孩子，故每个度为 1 的结点产生一条边；度为 2 的结点有 2 个孩子，故每个度为 2 的结点产生两条边，所以总边数为：n1 + 2n2。 故从边的角度考虑：N-1 = n1 + 2n2 ② 结合① 和 ②得：n0 + n1 + n2 - 1 = n1 + 2*n2，即：n0 = n2 + 1

2. 深度与节点数上限：若深度为 k（根节点深度为 1），则该二叉树最多有 2ᵏ - 1 个节点（满二叉树的情况），最少有 k 个节点。

   二叉树最多节点的情况： 第 1 层：最多有 2^0 个节点。 第 2 层：最多有 2^1 个节点。 第 3 层：最多有 2^2 个节点。 ... 第 k 层：最多有 2^(k-1) 个节点。 最多节点的总数为：N = 2^0 + 2^1 + 2^2 + ... + 2^(k-1) = 2^k - 1 个节点。 二叉树最少节点的情况：每层只有一个节点，则 k 层有 k 个节点。

3. 层数与节点分布：第 k 层（根为第 1 层）最多有 2^(k-1) 个节点，最少有 1 个节点。

满二叉树的性质

1. 所有层的节点数均达到最大值，即第 k 层有 2^(k-1) 个节点，总节点数 n = 2ᵏ - 1（k 为深度）。
2. 叶子节点全部在最底层，且不存在度为 1 的节点（n₁ = 0），叶子节点数 n₀ = 2ᵏ⁻¹。
3. 假设树的深度 k，则总节点数 n = 2ᵏ - 1，深度 k ≈ log₂n。

完全二叉树的性质

1. 节点总数 n 满足 (2ᵏ⁻¹ - 1) + 1 <= n <= 2ᵏ - 1（k 为深度），深度 k ≈ log₂n。
2. 数组存储索引规则：
   • 父节点 i 的左子节点为 2i、右子节点为 2i+1；
   • 子节点 j 的父节点为 j / 2（索引从 1 开始）。
3. 叶子节点索引范围为 n/2 + 1 到 n，非叶子节点为 1 到 n/2，无'只有右子节点'的情况。
4. 对于完全二叉树，度为 1 的节点：只有 1 个或者 0 个。

四、树与二叉树的转换

普通树转换为二叉树

核心方法

1. 加线（连兄弟）：在所有兄弟节点之间加一条连线。
2. 抹线（断父子）：保留最左边的孩子（长子），抹掉其他孩子。
3. 旋转（理层次）：以树的根节点为轴心，将整棵树顺时针旋转 45 度，使其看起来像一棵标准的二叉树。

简记：兄弟相连留长子

图解演示

如图所示一棵普通树：

操作一：兄弟间加线

操作二：保留长子

操作三：以根为轴心顺时针旋转 45°

二叉树转换为普通树

核心方法

1. 加线（认父亲）：对于某个节点（比如 P），如果它有左孩子（L），那么把 L 的所有右链上的节点（即 L 的兄弟们），都与 P 用线连起来。
2. 抹线（断兄弟）：抹掉二叉树中所有节点与它右孩子之间的连线。
3. 旋转（理层次）：整理结构，使其恢复为普通树的层次。

简记为：左孩右右连双亲，去掉原来右孩线

图解演示

如图所示有一棵二叉树：

操作一：加线（认父亲）

操作二：抹线（断兄弟）

操作三：旋转（理层次）

森林转换为二叉树

核心方法

1. 各树自转：先把森林中的每一棵树，各自转换为二叉树。
2. 根根相连：将每棵树的根节点用线连起来。
3. 唯一树根：第一棵树的根节点，就是转换后整棵二叉树的根节点。

简记：树变二叉，根相连

图解演示

如图所示有如下森林：

操作一：各树自转

操作二：根根相连

操作三：唯一树根

二叉树转换为森林

核心方法

1. 抹线（断开树与树的联系）：沿着二叉树根节点的右链一直走下去，把这根链上的所有连线全部剪断。
2. 提取（确定每棵树的根）：断开后，右链上的每一个节点，现在都成为了独立的二叉树的根节点。
3. 还原（各自变回普通树）：对这散落出来的每一棵小二叉树，分别执行'二叉树转普通树'的操作。

简记：去掉根部右孩线，孤立二叉再还原

图解演示

如图所示一棵二叉树：

操作一：抹线（断开树与树的联系）

操作二：提取（确定每棵树的根）

操作三：还原（各自变回普通树）

五、小试牛刀

试题一

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

A. 不存在这样的二叉树 B. 200 C. 198 D. 199

解析：对于任何一棵二叉树，都满足这样一个性质：n0（度为 0 的节点）= n2（度为 2 的节点）+ 1。故而叶子节点（即度为 0 的节点）个数为：199 + 1 = 200，B 选项符合题意。

试题二

2. 下列数据结构中，不适合采用顺序存储结构的是（ ）

A. 非完全二叉树 B. 堆 C. 队列 D. 栈

解析：

• B. 堆：基于完全二叉树连续排列的特性，故而可以采用顺序结构存储。
• C. 队列：对于循环队列采用顺序存储结构。
• D. 栈：一般基于数组实现，采用顺序结构。

答案为：A

试题三

3. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

A. n B. n+1 C. n-1 D. n/2

解析：对于任何一棵二叉树而言其节点总数 N，由度为 0 的节点、度为 1 的节点、度为 2 的节点所组成，N = n0 + n1 + n2。任意一棵二叉树满足如下性质：n0 = n2 + 1。故而 2n = n0 + n1 + n0 - 1，当且仅当 n1 = 1 时左边为偶数，且右边为偶数，所以 n0 = n。

答案为：A

试题四

4. 一棵完全二叉树的结点数为 531 个，那么这棵树的高度为（ ）

A. 11 B. 10 C. 8 D. 12

解析：对于一棵完全二叉树而言，假设这棵树的高度为 k，则其节点的范围：2^(k-1) ~ 2^k - 1。

答案为：B

试题五

5. 一个具有 767 个结点的完全二叉树，其叶子结点个数为（ ）

A. 383 B. 384 C. 385 D. 386

解析：对于任何一棵二叉树而言其节点总数 N，由度为 0 的节点、度为 1 的节点、度为 2 的节点所组成，N = n0 + n1 + n2。任意一棵二叉树满足如下性质：n0 = n2 + 1。对于 N = 767，则有 767 = n0 + n1 + n0 - 1，当且仅当 n1 等于 0 时，才满足左右两边为奇数，所以 n1 = 0。

答案为：B，n0 = 384