攀枝花市网站建设_网站建设公司_页面权重_seo优化

一、二叉树的核心性质

1. 满二叉树的结点数：深度为kkk的满二叉树，其结点总数为2k−12^k - 12k−1。这是因为每一层的结点数为2i−12^{i-1}2i−1（第iii层），从第 1 层到第kkk层求和即得：
   ∑i=1k2i−1=2k−1 \sum_{i=1}^{k} 2^{i-1} = 2^k - 1i=1∑k​2i−1=2k−1

2. 终端结点与度 2 结点的关系：在任意二叉树中，设终端结点（叶子）个数为n0n_0n0​，度为 2 的结点个数为n2n_2n2​，则有：
   n0=n2+1 n_0 = n_2 + 1n0​=n2​+1
   推导依据是总边数等于所有结点出度之和，也等于父结点指向孩子的边数。

3. 完全二叉树的深度：含有nnn个结点的完全二叉树，其深度为：
   ⌊log⁡2n⌋+1 \lfloor \log_2 n \rfloor + 1⌊log2​n⌋+1
   因为前k−1k-1k−1层构成满二叉树结构，最多包含2k−1−12^{k-1}-12k−1−1个结点。

二、二叉树的分类（结合图示）

三、二叉树的顺序存储结构

存储方式：使用数组按层次遍历顺序（自上而下、自左至右）存放结点，适用于完全二叉树，能高效利用空间并快速计算父子关系。

对于编号为iii的结点（1≤i≤n1 \leq i \leq n1≤i≤n）：

• 双亲结点：若i>1i > 1i>1，其双亲编号为⌊i2⌋\left\lfloor \frac{i}{2} \right\rfloor⌊2i​⌋；当i=1i = 1i=1时为根结点，无双亲。
• 左孩子结点：若2i≤n2i \leq n2i≤n，左孩子编号为2i2i2i；否则不存在左孩子。
• 右孩子结点：若2i+1≤n2i+1 \leq n2i+1≤n，右孩子编号为2i+12i+12i+1；否则不存在右孩子。

注：该编号规则基于从 1 开始编号。若编程中使用从 0 开始的数组索引，则需调整公式为：

• 父节点：⌊i−12⌋\left\lfloor \frac{i-1}{2} \right\rfloor⌊2i−1​⌋
• 左孩子：2i+12i + 12i+1
• 右孩子：2i+22i + 22i+2

要证明在任意二叉树中，叶子结点（终端结点）个数 $ n_0 $ 与度为 2 的结点个数 $ n_2 $ 满足关系：

n0=n2+1 n_0 = n_2 + 1n0​=n2​+1

我们可以通过结点总数和边的总数两个角度进行推导。

证明过程

设一棵二叉树中有：

• $ n_0 $：度为 0 的结点数（即叶子结点）
• $ n_1 $：度为 1 的结点数（只有左孩子或右孩子）
• $ n_2 $：度为 2 的结点数（有两个孩子）

则整棵树的总结点数为：

n=n0+n1+n2(1) n = n_0 + n_1 + n_2 \tag{1}n=n0​+n1​+n2​(1)

另一方面，从边的数量来看：

• 每个结点（除根结点外）都由一条边连接到其父结点。
• 所以总的边数为：$ n - 1 $

而这些边也可以通过各结点的出度（孩子数）来计算：

• 度为 1 的结点贡献 1 条边，
• 度为 2 的结点贡献 2 条边，
• 度为 0 的结点贡献 0 条边。

因此，总边数也可表示为：

边数=0⋅n0+1⋅n1+2⋅n2=n1+2n2 \text{边数} = 0 \cdot n_0 + 1 \cdot n_1 + 2 \cdot n_2 = n_1 + 2n_2边数=0⋅n0​+1⋅n1​+2⋅n2​=n1​+2n2​

又因为边数等于 $ n - 1 $，所以有：

n1+2n2=n−1(2) n_1 + 2n_2 = n - 1 \tag{2}n1​+2n2​=n−1(2)

将式 (1) 中的 $ n = n_0 + n_1 + n_2 $ 代入式 (2)：

n1+2n2=(n0+n1+n2)−1 n_1 + 2n_2 = (n_0 + n_1 + n_2) - 1n1​+2n2​=(n0​+n1​+n2​)−1

两边同时减去 $ n_1 $：

2n2=n0+n2−1 2n_2 = n_0 + n_2 - 12n2​=n0​+n2​−1

移项得：

2n2−n2=n0−1⇒n2=n0−1 2n_2 - n_2 = n_0 - 1 \Rightarrow n_2 = n_0 - 12n2​−n2​=n0​−1⇒n2​=n0​−1

即：

n0=n2+1 n_0 = n_2 + 1n0​=n2​+1

✅ 得证。

直观理解

这个性质的本质是：每一个新增的“分叉”（即度为 2 的结点）都会增加一个额外的分支路径，从而最终导致多出一个叶子。根结点开始是一个叶子（单节点树），每增加一个度为 2 的结点，相当于把一个叶子变成内部结点，并生成两个新叶子，净增一个叶子。