bitworld 的博客
二叉树上的二级结论
bitworld 最强壮的男人 SU @ 2025-8-21 16:18:04

二叉树上的二级结论

一、核心概念与基本性质

在深入探讨二级结论之前，我们必须先建立对二叉树基本概念的共识。这些是理解后续所有性质的基石。

1.1 什么是二叉树

二叉树是一种特殊的树形数据结构，其每个节点最多有两个子节点，分别称为“左子节点”和“右子节点”。由于这种结构，二叉树的子树被明确区分为“左子树”和“右子树”，即使树中某节点只有一个子节点，也要区分它是左子节点还是右子节点。

节点 (Node)：树的基本组成单元，包含数据元素以及指向其子节点的指针。
根节点 (Root)：没有父节点的唯一节点。
叶子节点 (Leaf Node)：没有子节点的节点，其度 (degree) 为0。
内部节点 (Internal Node)：非叶子节点，即度不为0的节点。
度 (Degree)：一个节点拥有的子树数量或子节点数量。
层次 (Level)：从根节点开始定义，根为第1层，根的子节点为第2层，以此类推。
高度/深度 (Height/Depth)：树中节点的最大层次。空树的高度为0。

1.2 几类特殊的二叉树

在笔试题中，常常会考察几类具有特殊形态的二叉树。

满二叉树 (Full Binary Tree)：一棵深度为 $h$ 且有 $2^h - 1$ 个节点的二叉树。在满二叉树中，每一层的节点数都达到了该层的最大值。也就是说，除了叶子节点外，每个节点的度都是2。
完全二叉树 (Complete Binary Tree)：若设二叉树的深度为 $h$ ，除第 $h$ 层外，其它各层 (1～ $h-1$ ) 的节点数都达到最大个数，第 $h$ 层的所有节点都连续集中在最左边。满二叉树是一种特殊的完全二叉树。
二叉搜索树 (Binary Search Tree, BST)：也称二叉排序树。它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左、右子树也分别为二叉搜索树。

二、基础结论（一级结论）

这些是直接由定义可以推导出的最直接的性质，是二级结论的基础。

性质1：节点与层次的关系

在二叉树的第 $i$ 层上，最多有 $2^{i-1}$ 个节点 ( $i \ge 1$ )。

性质2：高度与节点总数的关系

深度为 $h$ 的二叉树，最多有 $2^h - 1$ 个节点。这个上限在满二叉树时取到。

性质3：边与节点数的关系

对于任意一棵非空二叉树，如果其节点总数为 $n$ ，则其边数为 $n-1$ 。这是所有树形结构共有的性质。

三、核心二级结论

二级结论是在基本性质之上，通过更深一层的代数推导或组合分析得出的重要性质。这些结论在解决选择题、判断题和程序填空题时极为高效。

3.1 节点数量关系： $n_0 = n_2 + 1$

结论：对于任何非空二叉树，如果其叶子节点（度为0的节点）个数为 $n_0$ ，度为2的节点个数为 $n_2$ ，则恒有 $n_0 = n_2 + 1$ 。

证明: 这个结论的证明非常巧妙，可以从两个不同的角度看待整棵树的连接关系。设 $n$ 为节点总数， $E$ 为边的总数。设 $n_0, n_1, n_2$ 分别为度为0、1、2的节点个数。

从节点的角度看：树的总节点数是所有类型节点的加和。
$n = n_0 + n_1 + n_2$
从边的角度看：树的总边数等于（根节点外的节点数），即 $E = n - 1$ （性质3）。同时，总边数也可以由每个节点的度数来计算：度为1的节点贡献1条边（指向它），度为2的节点贡献2条边（指向它）。但这样计算的是入度，我们换个角度，从出度计算。每条边都从一个父节点指向一个子节点。度为1的节点有1个孩子，射出1条边；度为2的节点有2个孩子，射出2条边；度为0的节点没有孩子，射出0条边。所以总边数 $E$ 也可以表示为：
$E = 1 \cdot n_1 + 2 \cdot n_2$
联立方程：我们现在有两个关于 $n$ 的表达式。将 $n = n_0 + n_1 + n_2$ 代入 $E = n - 1$ 中，得到：
$E = (n_0 + n_1 + n_2) - 1$
我们又有 $E = n_1 + 2 \cdot n_2$ 。于是：
$n_1 + 2 \cdot n_2 = n_0 + n_1 + n_2 - 1$
化简方程，两边同时减去 $n_1$ 和 $n_2$ ：
$n_2 = n_0 - 1$
即：
$n_0 = n_2 + 1$
证明完毕。

应用与考题示例：

判断题：在一棵二叉树中，度为2的节点数量总是比叶子节点数量少1。 (√)
选择题：若一棵二叉树共有100个节点，其中度为1的节点有40个，那么该二叉树的叶子节点有多少个？
- 解：已知 $n = 100$ , $n_1 = 40$ 。根据 $n = n_0 + n_1 + n_2$ ，我们有 $100 = n_0 + 40 + n_2$ 。又根据本结论 $n_0 = n_2 + 1$ ，即 $n_2 = n_0 - 1$ 。将后者代入前者： $100 = n_0 + 40 + (n_0 - 1)$ $100 = 2n_0 + 39$ $2n_0 = 61$ $n_0 = 30.5$ 这个结果是错误的，因为节点数必须是整数。这说明题目给出的数据“度为1的节点有40个”在节点总数为100的树中是不可能存在的。在实际考题中，数据都会是合法的。例如，若度为1的节点有39个。 $100 = n_0 + 39 + (n_0 - 1)$ $100 = 2n_0 + 38$ $2n_0 = 62 \implies n_0 = 31$ 。此时叶节点为31个，度为2的节点为 $n_2 = n_0 - 1 = 30$ 个。

3.2 完全二叉树的性质

完全二叉树由于其结构的高度规律性，引出了一系列重要的数值结论，尤其是在使用数组（顺序存储）表示时。

3.2.1 节点编号与位置关系

如果我们将一棵有 $n$ 个节点的完全二叉树按层序遍历（从上到下，从左到右）进行编号，节点编号从1到 $n$ ，那么对于任意编号为 $i$ 的节点：

父节点：若 $i > 1$ ，其父节点的编号为 $\lfloor i/2 \rfloor$ 。根节点1没有父节点。
左子节点：若 $2i \le n$ ，其左子节点的编号为 $2i$ 。否则，它没有左子节点。
右子节点：若 $2i + 1 \le n$ ，其右子节点的编号为 $2i + 1$ 。否则，它没有右子节点。

注意：如果编号从0开始，对于编号为 $i$ 的节点，其父节点为 $\lfloor (i-1)/2 \rfloor$ ，左子节点为 $2i+1$ ，右子节点为 $2i+2$ 。考题中需注意编号的起始值是0还是1。

3.2.2 完全二叉树的深度与节点数

对于一个有 $n$ 个节点的完全二叉树，其深度（或高度） $h$ 为：

h = \lfloor \log_2 n \rfloor + 1

或者

h = \lceil \log_2 (n+1) \rceil

这两个公式是等价的。

应用与考题示例：

程序填空：用数组存储一个完全二叉树，实现查找编号为 idx 的节点的右兄弟节点。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// tree[] 存储完全二叉树，n为节点总数
// 编号从1开始
int getRightSibling(int tree[], int n, int idx) {
    // 节点不存在或为根节点，或为最右侧节点
    if (idx <= 0 || idx >= n) return -1; 
    
    // 如果idx是其父节点的右孩子，则它没有右兄弟
    // 父节点是 floor(idx/2)，右孩子是 2*floor(idx/2)+1
    // 如果idx是奇数，它可能是左孩子；如果是偶数，一定是左孩子
    // 更简单的判断：检查它是否是该层的最后一个节点
    // 或者检查下一个编号是否还是同一个父节点
    int p_idx = idx / 2; // 父节点
    if (idx + 1 > n || (idx + 1) / 2 != p_idx) {
        return -1; // 超出范围，或者下一个节点的父节点不是当前父节点
    }

    // 检查idx是否为奇数，如果是奇数说明是左孩子
    if (idx % 2 != 0) {
        // 如果它是左孩子，它的右兄弟就是 idx + 1
        if (idx + 1 <= n) {
            return tree[idx + 1];
        }
    }
    
    return -1; // 偶数节点(右孩子) 或 奇数节点但没有右兄弟
}

// 另一个更简洁的判断方式
int getRightSibling_v2(int tree[], int n, int idx) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (idx <= 0 || idx >= n) return -1; // 无效输入
    // 如果idx是偶数，它是右孩子，没有右兄弟
    // 如果idx是奇数，它是左孩子，它的右兄弟是idx+1
    // 必须确保idx+1不超过n
    if (idx % 2 != 0 && idx + 1 <= n) {
        // 关键点：在完全二叉树中，如果一个节点是奇数编号（且不是最后一个节点），
        // 那么它一定是某个节点的左孩子，它的右兄弟必然是idx+1。
        // 因为节点是连续排列的。
        // 但是要考虑它是不是其父节点的右孩子
        // 比如节点3(父1), idx+1是4(父2),就不是兄弟
        int p_idx = idx / 2;
        if ( (idx + 1) / 2 == p_idx )
            return tree[idx + 1];
    }
    return -1;
}

复杂度分析: 时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

3.2.3 完全二叉树的叶子节点数

对于一个有 $n$ 个节点的完全二叉树，其叶子节点数 $n_0$ 可以通过 $n_0 = n_2 + 1$ 的通用公式计算，但也有其自身的特点。在完全二叉树中，最后一个非叶子节点的编号是 $\lfloor n/2 \rfloor$ 。因此，所有编号大于 $\lfloor n/2 \rfloor$ 的节点都是叶子节点。所以叶子节点的个数是 $n - \lfloor n/2 \rfloor = \lceil n/2 \rceil$ 。

选择题：一个有1001个节点的完全二叉树，其叶子节点有多少个？

解：根据公式 $\lceil n/2 \rceil = \lceil 1001/2 \rceil = \lceil 500.5 \rceil = 501$。所以叶子节点有501个。

3.3 由遍历序列还原二叉树

这是一个非常高频的考点，深刻揭示了不同遍历序之间的内在关系。

结论：

(前序遍历 + 中序遍历) 可以唯一确定一棵二叉树。
（后序遍历 + 中序遍历) 可以唯一确定一棵二叉树。
（前序遍历 + 后序遍历) 不能唯一确定一棵二叉树。这是因为，当一个节点只有一个子树时，无法判断这个子树是左子树还是右子树。

原理:

前序遍历的特点是第一个元素永远是当前（子）树的根节点。
后序遍历的特点是最后一个元素永远是当前（子）树的根节点。
中序遍历的特点是根节点位于序列的中间，其左边的所有元素都属于左子树，右边的所有元素都属于右子树。

还原过程（以前序+中序为例）:

从前序遍历序列中取出第一个元素，这个元素就是整棵树的根节点。
在中序遍历序列中找到这个根节点。
根据根节点在中序遍历中的位置，可以将中序遍历序列分为两部分：根节点左边的部分是左子树的中序遍历，右边的部分是右子树的中序遍历。
根据左子树中序遍历的节点数量，可以在前序遍历序列中（从第二个元素开始）划分出左子树的前序遍历。剩下的部分就是右子树的前序遍历。
现在我们拥有了左子树的（前序+中序）序列和右子树的（前序+中序）序列，问题规模变小了。递归地重复上述步骤，直到处理的子序列为空。

考题示例：

解答题：已知某二叉树的前序遍历为 GDAFEMHZ，中序遍历为 ADEFGHMZ，请求出其后序遍历。
解题步骤:
1. 根：前序首位是 G，所以 G 是根。
2. 划分：在中序中找到 G，ADEF 是 G 的左子树，HMZ 是 G 的右子树。
3. 左子树：
  - 左子树前序：DAFE (根据中序ADEF的4个节点，在前序中取G后面的4个)
  - 左子树中序：ADEF
  - 递归：左子树的根是 D (前序首位)。在中序ADEF中，A是D的左子树，EF是D的右子树。
  - D的左子树：前序A，中序A。它只有一个节点A。
  - D的右子树：前序FE，中序EF。根是F。在中序EF中，E是F的左子树，无右子树。
4. 右子树：
  - 右子树前序：MHZ
  - 右子树中序：HMZ
  - 递归：右子树的根是 M (前序首位)。在中序HMZ中，H是M的左子树，Z是M的右子树。
5. 构建树形图:
```
      G
     / \
    D   M
   / \ / \
  A  F H  Z
     /
    E
```
6. 后序遍历 (左右根):
  - 左子树后序：A (D的左) -> E (F的左) -> F (D的右) -> D
  - 右子树后序：H (M的左) -> Z (M的右) -> M
  - 总后序：(左子树后序) -> (右子树后序) -> (根) = AEFDH ZMG
程序实现:

#include<bits/stdc++.hh>
using namespace std;
using ll = long long;

struct Node {
    char val;
    Node *l, *r;
    Node(char v) : val(v), l(nullptr), r(nullptr) {}
};

// pre: 前序遍历序列, in: 中序遍历序列
// ps, pe: 前序的开始和结束索引
// is, ie: 中序的开始和结束索引
Node* build(const string& pre, const string& in, int& p_idx, int is, int ie) {
    if (is > ie) return nullptr;
    
    char root_val = pre[p_idx++];
    Node* root = new Node(root_val);
    
    int i_idx = -1; // 在中序中找到根节点的位置
    for (int i = is; i <= ie; ++i) {
        if (in[i] == root_val) {
            i_idx = i;
            break;
        }
    }
    
    // 递归构建左右子树
    // 必须先构建左子树，因为前序遍历是根-左-右，p_idx会自然地移动到右子树的根
    root->l = build(pre, in, p_idx, is, i_idx - 1);
    root->r = build(pre, in, p_idx, i_idx + 1, ie);
    
    return root;
}

void postOrder(Node* root) {
    if (!root) return;
    postOrder(root->l);
    postOrder(root->r);
    cout << root->val;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string pre = "GDAFEMHZ";
    string in = "ADEFGHMZ";
    
    int p_idx = 0;
    Node* root = build(pre, in, p_idx, 0, in.length() - 1);
    
    postOrder(root);
    cout << endl; // 输出 AEFDHZMG
    
    return 0;
}

复杂度分析: 每次 build 函数调用都需要在中序序列中进行一次线性查找。如果树不退化，时间复杂度为 $O(N \log N)$ 。如果树退化成链表，则为 $O(N^2)$ 。可以通过使用一个哈希表来预存中序序列中每个值的位置，将查找时间降为 $O(1)$ ，从而使得总时间复杂度优化到 $O(N)$ 。空间复杂度为递归栈的深度，最坏情况下为 $O(N)$ ，平均为 $O(\log N)$ 。

3.4 二叉搜索树(BST)与遍历

结论：对一棵二叉搜索树进行中序遍历，得到的序列必然是一个非递减的有序序列。

证明: 根据中序遍历“左-根-右”的顺序和BST“左<根<右”的定义：

递归地访问左子树，根据定义，左子树所有节点的值都小于根节点。
访问根节点。
递归地访问右子树，根据定义，右子树所有节点的值都大于根节点。这个过程保证了访问节点的顺序是严格按照节点值从小到大（或非递减，如果允许重复值）进行的。

应用与考题示例：

判断题：一个序列 1, 2, 5, 4, 6 是否可能是一棵二叉搜索树的中序遍历结果？ (×)
- 解：因为序列不是有序的（5后面是4），所以它不可能是任何BST的中序遍历结果。
程序阅读题：下面这段代码的功能是什么？

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    int val;
    Node *l, *r;
};

bool chk(Node* u, int min, int max) {
    if (!u) return true;
    if (u->val <= min || u->val >= max) return false;
    return chk(u->l, min, u->val) && chk(u->r, u->val, max);
}

bool isBST(Node* root) {
    return chk(root, INT_MIN, INT_MAX);
}

答案：判断一棵二叉树是否是二叉搜索树。
逻辑解释: chk 函数递归地验证每个节点 u 的值是否在其合法的取值范围 (min, max) 内。对于根节点，范围是 (INT_MIN, INT_MAX)。当递归到左子树 u->l 时，其所有节点的值必须小于当前节点 u->val，所以新的上界是 u->val。当递归到右子树 u->r 时，其所有节点的值必须大于当前节点 u->val，所以新的下界是 u->val。这种方法正确地保证了BST的全局性质，避免了只比较父子节点大小的局部错误判断。
复杂度分析: 时间复杂度 $O(N)$ ，因为每个节点被访问一次。空间复杂度 $O(H)$ ，其中 $H$ 是树的高度，用于递归栈。

对于节点数量关系 $n_0=n_2+1$ ，关键在于从“节点总数”和“边总数”两个角度建立方程。

对于完全二叉树，其价值在于结构的高度规律性，使得数组下标能完美映射父子关系，大量性质也由此产生。

对于遍历序列还原树，核心在于理解不同遍历序（特别是前序、后序和中序）如何揭示树的“根”与“子树”结构。

对于二叉搜索树，其与中序遍历的内在联系（有序性）是考察的重点。