4.2.3二叉树的性质

性质1：层节点数上限

表述：二叉树的第​i层（​i \geq 1）上至多有​2^{i-1}个节点。

性质2：总节点数上限

表述：深度为​k（​k \geq 1）的二叉树至多有​2^{k} - 1个节点。

性质3：叶节点与分支节点关系

表述：对任何二叉树​T，若其终端节点数为​n_0，度为2的节点数为​n_2，则​n_0 = n_2 + 1。

证明

设：

• ​n_1为度为1的节点数
• ​n为总节点数
• ​B为分支总数

1. 节点总数关系：

   n = n_0 + n_1 + n_2 \quad (4-2)

2. 分支总数计算：

   B = n_1 + 2n_2 \quad (4-4)

3. 节点与分支关系：

   n = B + 1 \quad (4-3)

4. 联立方程：将(4-4)代入(4-3)：

   n = n_1 + 2n_2 + 1 \quad (4-5)

5. 消元求解：
   联立(4-2)和(4-5)：

   n_0 + n_1 + n_2 = n_1 + 2n_2 + 1

   化简得：

   n_0 = n_2 + 1

性质4：完全二叉树深度公式

表述：具有​n个节点的完全二叉树的深度为​\lfloor \log_2 n \rfloor + 1（​\lfloor x \rfloor表示不大于​x的最大整数）。

证明

设深度为​k（​k \geq 1）：

1. 节点范围：

   2^{k-1} - 1 < n \leq 2^k - 1

2. 取对数化简：

   2^{k-1} \leq n < 2^k
   \log_2 n < k \leq \log_2 n + 1

3. 深度公式：

   k = \lfloor \log_2 n \rfloor + 1

性质5：完全二叉树节点关系

表述：对完全二叉树中按层序编号的节点​i（​0 \leq i < n）：

1. 双亲节点：

   • 若​i = 0，节点为根（无双亲）
   • 若​i > 0，双亲节点为​\lfloor (i-1)/2 \rfloor

2. 左孩子：

   • 若​2i + 1 \geq n，无左孩子
   • 若​2i + 1 < n，左孩子为​2i + 1

3. 右孩子：

   • 若​2i + 2 \geq n，无右孩子
   • 若​2i + 2 < n，右孩子为​2i + 2

节点关系示例

符号说明：

• ​\lfloor x \rfloor：不大于​x的最大整数
• ​\lceil x \rceil：不小于​x的最小整数