树与二叉树

核心定义

树 是一种 递归定义 的层次结构，通常存在唯一 根结点，根以下通过边连接若干子树。树的关键在于 层次关系，与线性表的本质差异是 一对多 对 一对一。

二叉树 是每个结点最多有 两个孩子 的树，并且必须严格区分 左子树 与 右子树。二叉树的关键在于 左右区分，即使只有一个孩子也要区分左右。

二叉排序树（BST）的中序遍历结果是 递增序列，这是它最重要的性质。BST 必须满足 左子树所有结点 < 根 < 右子树所有结点。

完全二叉树 允许最后一层不满，但必须 从左向右连续填充；满二叉树 要求 每层结点数都达到最大——两者不同。

完全二叉树中，若结点按层序编号 $i$（从 1 开始），则左孩子下标为 $2i$，右孩子下标为 $2i+1$，父结点下标为 $\lfloor i/2 \rfloor$。

哈夫曼树 是 带权路径长度最小 的二叉树，构造方法是每次选 权值最小的两个结点合并。哈夫曼编码是 前缀编码。

$n$ 个结点的二叉树，度为 0 的结点数 $n_0$ 和度为 2 的结点数 $n_2$ 满足关系 $n_0 = n_2 + 1$。总结点数 $n$、边数 $e$ 满足 $e = n - 1$。

树的遍历是考研核心：前序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）、层序遍历（逐层从左到右，用 队列）。

关键细节 / 操作步骤

1. 先判断题目是在问 概念、遍历、建树，还是 性质。
2. 若题目给”根-左-右”，立刻想到 前序遍历。
3. 若题目给”左-根-右”，立刻想到 中序遍历。
4. 若题目给”左-右-根”，立刻想到 后序遍历——常用于 释放树的空间（先释放子树再释放根）。
5. 若题目给”按层访问”，立刻想到 层序遍历 与队列（是 BFS 不是 DFS）。
6. 若题目问 BST，先看是否满足 左小右大，再利用中序有序性质。
7. 若题目问还原二叉树，优先考虑 前序 + 中序 或 后序 + 中序，前序 + 后序 不能唯一还原（除非附加条件）。
8. 若题目涉及完全二叉树编号，先套 $2i$、$2i+1$、$\lfloor i/2 \rfloor$ 的下标关系。
9. 若题目问结点统计，用公式 $n = n_0 + n_1 + n_2$ 且 $n_0 = n_2 + 1$。
10. 若题目问存储方式，先区分 顺序存储（适合完全二叉树）与 链式存储（通用，每个结点含 lchild、data、rchild 三个域）。
11. 若题目问 线索二叉树，核心目的是 加速查找前驱后继，利用 空指针域 存线索，线索化的过程本质是 中序遍历的修改版。
12. 若题目问树、森林与二叉树的转换，规则是 左孩子右兄弟，森林中第二棵树变为二叉树根的 右子树。
13. 若题目问二叉树深度，可用递归公式 $\text{depth} = \max(\text{depth}(左), \text{depth}(右)) + 1$。
14. 若题目问完全二叉树高度，含 $n$ 个结点时高度为 $\lfloor \log_2 n \rfloor + 1$。

⚠️ 易错辨析 BST 的中序有序只对 二叉排序树 成立，不适用于普通二叉树——真题常拿”二叉树”和”BST”互换概念设陷阱。层序遍历是 BFS 不是 DFS，若把层序写成深度优先则整题结论会错。前序 + 中序通常能 唯一还原 二叉树，但前序 + 后序一般不能唯一还原。完全二叉树和满二叉树不同——完全二叉树允许最后一层不满但必须从左向右连续。度为 1 的结点在完全二叉树中最多有 1 个。反例：一棵只有左孩子的二叉树，前序为 A B，后序为 B A，无法唯一确定树形。

💡 技巧与口诀 口诀：前序看结构，中序看有序，后序做收尾，层序看层次。适用场景：只要题目出现”遍历次序""还原树形""BST 有序”这三个关键词，就直接调用这句口诀。还原树形时先从 前序/后序找根，再用中序分左右。树的高度本质上就是 从根到最深叶子的路径长度。哈夫曼树中叶子结点的路径长度乘以权值之和即为 带权路径长度（WPL）。哈夫曼树中不存在度为 1 的结点，即 $n_1 = 0$。

📝 真题闭环 题目：前序遍历为 A B D E C，中序遍历为 B D E A C，能否唯一确定二叉树？画出该树。

解题思路：审题先抓”前序 + 中序”，切入点是 唯一还原；定理选择为二叉树重建规则；计算关键点是先从前序找根（第一个元素 A），再从中序分左右子树；易错防范是不要把前序 + 后序也当可唯一还原。

答案：能唯一确定。根为 A，左子树中序 B D E（前序 B D E），右子树中序 C（前序 C）。继续递归：左子树根 B，B 的右子树 D E 中序 D E（前序 D E），根 D 右孩子 E。

// T=O(n) S=O(h)
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        printf("%c ", T->data);
        InOrder(T->rchild);
    }
}