树与二叉树

7.1 树的定义与术语体系

7.1.1 树的递归定义：为什么必须递归地定义

线性表可以一句话说清：n 个元素的有限序列。树不行，因为树里边套着树。 我们只能这样定义它：

这个定义里有三个词是「锁死」的，考试经常在这里挖坑，我们逐个拆开看：

• 「有且仅有一个根」：这排除了「一个集合里有两个独立的部分」的情况，也排除了环形结构。 一个结点集如果能分成两块彼此没有边相连的部分，那它就不是一棵树，而是森林（forest）。
• 「互不相交」：这是最关键的一句。它保证了树中任意两个结点之间有且仅有一条路径， 也就是说树里绝不会有环。反过来说，只要一张连通图里出现了环，它就不是树。
• 「每个子集又是一棵树」：这叫递归定义，它直接决定了树上的算法几乎全部写成递归函数。 你后面会看到，求深度、求结点数、四种遍历，代码骨架都是「处理根 + 递归处理子树」。

换个角度看，树其实是一个满足下面三条的有向图：有且仅有一个入度为 0 的结点（根）、 其余结点入度全部为 1、从根出发能到达所有结点。这三条等价于「n 个结点、n − 1 条边、连通、无环」， 这是第 09 讲判断生成树时会反复用到的结论。所以树的边数是固定的：n 个结点的树恰好有 n − 1 条边， 不多不少。这个「n − 1」在证明性质 3 时会成为主角。

7.1.2 术语体系：一张图看懂全部概念

树的术语是整章最「碎」的部分，硬背很容易串。下面这张图把 16 个术语全部标在了同一棵树上， 建议先看图记位置，再看后面的定义表补精确定义。

结点

树中的基本单位，包含数据元素和指向其子树的分支信息。图 7-1 中共有 10 个结点。

结点的度

结点拥有的子树个数，也就是它孩子的个数。A 的度是 3，C 的度是 1，G、H、I、J 的度是 0。

树的度

树中所有结点度的最大值。图 7-1 中 max{3,2,2,1,2,0,…} = 3，所以这棵树的度是 3，它是一棵「3 次树」。m 次树就是度为 m 的树。

叶子（终端结点）

度为 0 的结点，它没有孩子。图 7-1 中 G、H、I、J 是叶子。

分支结点（非终端结点）

度不为 0 的结点。A、B、C、D、E、F 都是分支结点。其中度 ≥ 1 但 < 树度的分支结点（如 C）有时叫「内部结点」。

孩子

结点子树的根称为该结点的孩子。B、C、D 都是 A 的孩子。

双亲（父结点）

与孩子相对。除根以外每个结点有且仅有一个双亲——这是树与图最本质的区别之一。

兄弟

同一个双亲的孩子之间互称兄弟。B、C、D 互为兄弟；E、F 互为兄弟。

堂兄弟

双亲在同一层、但不是同一个结点的结点互为堂兄弟。E（双亲 B，第 2 层）与 G（双亲 C，第 2 层）是堂兄弟。注意：堂兄弟的双亲同层不同点，兄弟的双亲是同一个点。

祖先

从根到该结点所经分支上的所有结点。J 的祖先是 A、B、F（以及 J 自己按某些教材的约定也计入，考试一般只问「除自己外」的祖先）。

子孙

以某结点为根的子树中的任一结点。B 的子孙是 E、F、J。

层次

根为第 1 层，根的孩子为第 2 层，依此类推。有的教材从第 0 层开始编号，做题时先看清约定，两者只差一个常数。

深度（高度）

结点的深度是从根到该结点所经过的边数 + 1（= 该结点的层次）；树的深度是树中结点的最大层次。结点的高度是从该结点到最远叶子的最长路径边数。两者对整棵树来说数值相等（都等于层数），但对单个结点通常不等：F 的深度是 3，高度是 2。考试里若只说「深度」，通常指树的深度 = 层数。

有序树

结点的各子树从左到右有次序、不能互换。交换后就是另一棵树。二叉树、语法树都是有序树。

无序树

结点的子树之间没有顺序关系，交换任意两棵子树仍是同一棵树。一般的「家族关系树」是无序树。

森林

m（m ≥ 0）棵互不相交的树的集合。一棵树砍掉根，剩下的子树集合就是一个森林。树和森林是可以互相转化的，见 7.7 节。

路径与路径长度

从结点 X 到结点 Y 的路径是一个结点序列，其中相邻结点之间都有边相连（树中这条路径唯一）。路径长度 = 路径上边的条数。A 到 J 的路径是 A→B→F→J，长度为 3。

7.1.3 由定义直接推出的两条常用结论

树的定义非常强，强到可以直接推出两条后面反复要用的结论：

把这两条拼起来，就得到一条万能的恒等式：树的结点数 = 所有结点的度数之和 + 1。 别看它简单，二叉树性质 3（n0 = n2 + 1）就是它的直接系。

7.2 树的存储结构

树是「一对多」的逻辑结构，但计算机的内存是「一格一格、一条一条」的线性空间。 所谓设计存储结构，本质就是回答一个问题：怎么用线性内存把这个一对多关系记下来？ 下面三种表示法只是侧重点不同——分别把「找双亲」「找孩子」「把树变成二叉树」这三件事做成了 O(1) 或接近 O(1)。

7.2.1 双亲表示法：一组数组就够

思路最朴素：把结点按某种顺序（通常是层序）塞进一维数组，每个结点再存一个整数， 记下它双亲在数组中的下标。根的双亲记成 −1。

#include <iostream>
using namespace std;

/* ============================================================
   1) 双亲表示法（parent representation）
   结点只存"数据 + 双亲下标"，用一整块连续数组保存，根的双亲记 -1。
   ============================================================ */
const int MAXN = 100;

struct PTNode {          // 一个结点
    char data;           // 数据域
    int  parent;         // 双亲在数组中的下标，根为 -1
};

struct PTree {
    PTNode nodes[MAXN];  // 结点数组
    int    n;            // 当前结点个数
};

/* 求双亲：O(1)，这就是双亲表示法存在的唯一理由 */
int parentOf(const PTree& t, int i) { return t.nodes[i].parent; }

/* 求某结点的所有孩子：要扫全表，O(n)。
   想快就得再挂一张"孩子表"，那就变成孩子表示法了。 */
void printChildren(const PTree& t, int i) {
    cout << t.nodes[i].data << " 的孩子: ";
    for (int k = 0; k < t.n; ++k)
        if (t.nodes[k].parent == i) cout << t.nodes[k].data << ' ';
    cout << "\n";
}

int main() {
    /* 手动构造图 7-2 那棵树：下标 0..9 对应 A..J */
    PTree t;
    t.n = 10;
    const char* d = "ABCDEFGHIJ";
    int par[10] = { -1, 0, 0, 0, 1, 1, 2, 3, 3, 5 };   // 每个结点的双亲下标
    for (int i = 0; i < 10; ++i) { t.nodes[i].data = d[i]; t.nodes[i].parent = par[i]; }

    cout << "F 的双亲是 " << t.nodes[parentOf(t, 5)].data << "\n";   // B
    printChildren(t, 0);                                          // B C D
    printChildren(t, 1);                                          // E F
    return 0;
}

双亲表示法最大的价值在于：它能 O(1) 地向上走。凡是算法里频繁需要「找父亲 / 找根」的场景， 都会采用这种表示法——最典型的就是 7.9 节的并查集。

7.2.2 孩子表示法：把每个结点的孩子串成链表

既然双亲表示法找孩子慢，那就反着来：给每个结点挂一条链表，链表里存它所有孩子的下标。 这就是孩子表示法（child representation），也叫「孩子链表」。

C++ 里最简单的写法是「数组 + vector」： vector<int> ch[n]，ch[i] 里按从左到右的顺序存着结点 i 的所有孩子下标。 如果要手写链表（考试常见），则用「结点数组 + 孩子链表结点」两张表。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   2) 孩子表示法（child representation）—— 每个结点挂一条孩子链表
   这里用 vector 代替手写链表，语义完全一致，还免去了内存管理。
   ============================================================ */
struct CTree {
    vector<char>              data;   // 结点数据
    vector<vector<int>> child;  // child[i] = 结点 i 的所有孩子下标（从左到右有序）
    int root;                          // 根的下标

    explicit CTree(int n) : data(n), child(n), root(0) {}

    /* 找孩子：直接返回引用，O(度) 而不是 O(n)，这就是孩子表示法的意义 */
    const vector<int>& childrenOf(int i) const { return child[i]; }
};

/* 求双亲：孩子表示法的软肋，只能扫所有链表，最坏 O(n + 边数) */
int parentOf(const CTree& t, int x) {
    for (int i = 0; i < (int)t.child.size(); ++i)
        for (int c : t.child[i])
            if (c == x) return i;
    return -1;
}

/* 求根：入度为 0 的那个结点。用一个标记数组，O(n + 边数) */
int findRoot(const CTree& t) {
    vector<bool> isChild(t.data.size(), false);
    for (int i = 0; i < (int)t.child.size(); ++i)
        for (int c : t.child[i]) isChild[c] = true;
    for (int i = 0; i < (int)t.data.size(); ++i)
        if (!isChild[i]) return i;
    return -1;
}

int main() {
    /* 构造图 7-2 的树：0=A 1=B 2=C 3=D 4=E 5=F 6=G 7=H 8=I 9=J */
    CTree t(10);
    const char* d = "ABCDEFGHIJ";
    for (int i = 0; i < 10; ++i) t.data[i] = d[i];
    t.child[0] = { 1, 2, 3 };   // A -> B C D
    t.child[1] = { 4, 5 };      // B -> E F
    t.child[2] = { 6 };         // C -> G
    t.child[3] = { 7, 8 };      // D -> H I
    t.child[5] = { 9 };         // F -> J
    t.root = findRoot(t);

    cout << "根是 " << t.data[t.root] << "\n";                 // A
    cout << "F 的双亲是 " << t.data[parentOf(t, 5)] << "\n";   // B
    for (int c : t.childrenOf(0)) cout << t.data[c] << ' ';     // B C D
    cout << "\n";
    return 0;
}

7.2.3 孩子兄弟表示法：把树变成二叉树

第三种表示法是全章最重要的一个转折点。它的观察非常巧妙： 与其直接记录「谁是孩子」，不如记录两条关系——「我的第一个孩子是谁」和「我的下一个兄弟是谁」。

因为「第一个孩子」唯一，「下一个兄弟」也唯一，所以每个结点只要两个指针就够了， 而且结点的结构变成了和二叉树链表结点一模一样的两指针结构：

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   3) 孩子兄弟表示法（左孩子右兄弟）—— 也叫"二叉链表表示法"
   每个结点只有两个指针：
       firstChild ：指向第一个孩子（最左边的孩子）
       nextSibling：指向右边紧邻的下一个兄弟
   结点结构与二叉树结点完全相同，因此"树"被存成了"二叉树"。
   ============================================================ */
struct CSNode {
    char     data;
    CSNode*  firstChild;    // 左指针：第一个孩子
    CSNode*  nextSibling;   // 右指针：下一个兄弟
    CSNode(char d) : data(d), firstChild(nullptr), nextSibling(nullptr) {}
};

/* ---------- 求某结点的度：沿 firstChild 的同级链数一遍 ---------- */
int degreeOf(CSNode* p) {
    int d = 0;
    for (CSNode* c = p->firstChild; c; c = c->nextSibling) ++d;
    return d;
}

/* ---------- 求双亲：只能从根开始找，O(n) ---------- */
CSNode* parentOf(CSNode* root, CSNode* target) {
    if (!root) return nullptr;
    for (CSNode* c = root->firstChild; c; c = c->nextSibling) {
        if (c == target) return root;
        if (CSNode* r = parentOf(c, target)) return r;   // 递归到子树里找
    }
    return nullptr;
}

/* ---------- 用"树的层序序列 + 每结点的度"直接建树（不用指针操作） ----------
   输入：层序的结点值 vals，以及对应的度 deg（孩子个数），按层序依次给出。
   做法：用一个队列保存"已经建好、但孩子还没接完"的结点，依次分配孩子。 */
CSNode* buildByLevel(const vector<char>& vals, const vector<int>& deg) {
    if (vals.empty()) return nullptr;
    vector<CSNode*> node(vals.size());
    for (size_t i = 0; i < vals.size(); ++i) node[i] = new CSNode(vals[i]);

    int child = 1;                       // 下一个待分配的结点下标（根是 0）
    for (size_t i = 0; i < vals.size(); ++i) {
        CSNode* prev = nullptr;
        for (int k = 0; k < deg[i]; ++k) {
            if (child >= (int)vals.size()) break;
            if (k == 0) node[i]->firstChild = node[child];   // 第一个孩子挂在左指针
            else        prev->nextSibling = node[child];     // 其余孩子串在兄弟链上
            prev = node[child];
            ++child;
        }
    }
    return node[0];
}

int main() {
    /* 图 7-2 的树，按层序给出：A(3) B(2) C(1) D(2) E(0) F(1) G(0) H(0) I(0) J(0) */
    vector<char> v = { 'A','B','C','D','E','F','G','H','I','J' };
    vector<int>  d = {  3,  2,  1,  2,  0,  1,  0,  0,  0,  0 };
    CSNode* root = buildByLevel(v, d);

    cout << "A 的度 = " << degreeOf(root) << "\n";                 // 3
    cout << "B 的度 = " << degreeOf(root->firstChild) << "\n";     // 2
    cout << "J 的双亲 = " << parentOf(root, root->firstChild->firstChild->nextSibling
                                        ->firstChild)->data << "\n";  // F
    return 0;
}

对照图 7-4 仔细看：左指针画出的是竖着的「父子边」，右指针画出的是横着的「兄弟边」。 把兄弟边「旋转 45°压平」来看，整棵树就变成了一棵标准二叉树。 这正是教材上说的：孩子兄弟表示法把一棵普通树变成了一棵二叉树， 而它对应的二叉树恰好就是 7.7 节要讲的「树转二叉树」的结果——两者其实是同一个东西的两种说法。

7.3 二叉树：定义、形态与存储

7.3.1 二叉树的定义与五种基本形态

把这句话和树的定义对照着读，你会发现二叉树的定义多限制了两点：每个结点至多两棵子树， 而且这两棵子树有左右之分，次序不能颠倒。这两点决定了二叉树的一切特殊性质。 由定义直接可以枚举出二叉树只有五种基本形态：

7.3.2 斜树、满二叉树与完全二叉树

斜树

所有结点都只有左孩子（左斜树）或都只有右孩子（右斜树）的二叉树。 斜树每一层只有 1 个结点，因此 n 个结点的斜树深度为 n，是同一结点数下深度最大的二叉树， 退化成了一条「链表」。它也是顺序存储的噩梦（见 7.3.4）。

满二叉树

深度为 k 且含有 2^k − 1 个结点的二叉树。 等价说法：每一层的结点数都达到了最大值，即第 i 层恰有 2ⁱ⁻¹ 个结点； 也等价于「所有分支结点都有左右两个孩子，且所有叶子都在最下一层」。 n 个结点的满二叉树，叶子数 = (n+1)/2，分支结点数 = (n−1)/2。

完全二叉树

深度为 k、有 n 个结点的二叉树，当且仅当它的每一个结点都与深度为 k 的满二叉树中编号 1 ~ n 的结点一一对应时， 称为完全二叉树。通俗判断法：把结点按层序（从上到下、从左到右）编号后，编号序列不留空—— 即「只有最下面两层结点的度可以小于 2，且最下面一层的结点都集中在最左边」。

7.3.3 顺序存储：完全二叉树的天然表示法

二叉树是「一对二」的结构，用数组存再合适不过：把结点按层序依次放进数组， 那么父子关系可以直接用下标算术算出来，连指针都不用。 这正是第 10 讲的堆（heap）和线段树都用数组存树的原因。

7.3.4 普通二叉树用顺序存储有多浪费

顺序存储的公式之所以成立，全靠「层序编号不留空」这条约束。一旦换成普通二叉树， 为了让下标公式仍然有效，就只能把空缺的位置也留出来（通常填一个特殊标记，如 '#' 或 0）。 可空缺有多少呢？看最坏情况：

7.3.5 链式存储：二叉链表与三叉链表

链式存储才是二叉树的通用表示法。二叉链表的结点里放数据加左右孩子指针， 它是本章所有算法的默认存储结构：

7.3.6 建树工具箱：从数组、先序序列、层序序列建树

考试里「给你序列，让你建树」的题非常多。下面这段代码一口气给出三个建树工具： 用数组建完全二叉树、用带 # 的先序序列建任意二叉树、用层序序列建树。 这三个函数是后面所有算法实验的入口，建议直接背下来。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

/* ============================================================
   二叉树结点（二叉链表）
   ============================================================ */
struct TreeNode {
    char      val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

/* ---------- 工具 1：从数组建"完全二叉树" ----------
   arr 按层序存放，arr[i] 的左孩子是 arr[2i+1]，右孩子是 arr[2i+2]（0 基）
   值为 '#' 表示该位置为空（用于稀疏的完全二叉树） */
TreeNode* buildComplete(const vector<char>& arr) {
    int n = arr.size();
    if (n == 0 || arr[0] == '#') return nullptr;
    vector<TreeNode*> node(n, nullptr);
    for (int i = 0; i < n; ++i)
        if (arr[i] != '#') node[i] = new TreeNode(arr[i]);
    for (int i = 0; i < n; ++i) {
        if (!node[i]) continue;
        int l = 2 * i + 1, r = 2 * i + 2;
        if (l < n) node[i]->left  = node[l];
        if (r < n) node[i]->right = node[r];
    }
    return node[0];
}

/* ---------- 工具 2：从"带 # 的先序序列"建树 ----------
   例如 "ABD##E##C#F##" 表示：A 的左子树是 B，B 的左右孩子是 D、E，
   D、E 都是叶子；A 的右子树是 C，C 没有左孩子，右孩子是 F。
   '#' 表示空子树，因此序列长度一定是 2n+1。 */
TreeNode* buildByPreorder(const string& s, int& pos) {
    if (pos >= (int)s.size()) return nullptr;
    char c = s[pos++];
    if (c == '#') return nullptr;              // 空子树
    TreeNode* root = new TreeNode(c);
    root->left  = buildByPreorder(s, pos);      // 先建左子树
    root->right = buildByPreorder(s, pos);      // 再建右子树
    return root;
}

/* ---------- 工具 3：从"层序序列"建树 ----------
   vals[i] 为 '#' 表示空结点；用队列保存"孩子还没接完"的结点。
   注意：这里必须为每个位置都给出取值（哪怕孩子为空也要占一个 '#'
   或直接跳过），否则无法确定父子对应关系。 */
TreeNode* buildByLevelOrder(const vector<char>& vals) {
    if (vals.empty() || vals[0] == '#') return nullptr;
    TreeNode* root = new TreeNode(vals[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < vals.size()) {
        TreeNode* cur = q.front(); q.pop();
        if (i < vals.size()) {                       // 左孩子
            if (vals[i] != '#') { cur->left = new TreeNode(vals[i]); q.push(cur->left); }
            ++i;
        }
        if (i < vals.size()) {                       // 右孩子
            if (vals[i] != '#') { cur->right = new TreeNode(vals[i]); q.push(cur->right); }
            ++i;
        }
    }
    return root;
}

/* 中序遍历，用来验证三种建树结果是否一致 */
void inorder(TreeNode* r, string& out) {
    if (!r) return;
    inorder(r->left, out);
    out += r->val;
    inorder(r->right, out);
}

/* 释放整棵树：必须用后序，否则会访问已释放结点的孩子指针 */
void destroy(TreeNode* r) {
    if (!r) return;
    destroy(r->left);
    destroy(r->right);
    delete r;
}

int main() {
    /* 工具 1：数组 {A,B,C,D,E,#,F} 建出的树，中序应为 D B E A C F */
    vector<char> arr = { 'A','B','C','D','E','#','F' };
    TreeNode* t1 = buildComplete(arr);
    string s1; inorder(t1, s1);
    cout << "由数组建树      中序 = " << s1 << "\n";      // DBEACF

    /* 工具 2：先序序列建树，同一棵树 */
    int pos = 0;
    TreeNode* t2 = buildByPreorder("ABD##E##C#F##", pos);
    string s2; inorder(t2, s2);
    cout << "由先序序列建树  中序 = " << s2 << "\n";      // DBEACF

    /* 工具 3：层序序列建树，同一棵树 */
    vector<char> lv = { 'A', 'B', 'C', 'D', 'E', '#', 'F' };
    TreeNode* t3 = buildByLevelOrder(lv);
    string s3; inorder(t3, s3);
    cout << "由层序序列建树  中序 = " << s3 << "\n";      // DBEACF

    destroy(t1); destroy(t2); destroy(t3);
    return 0;
}

7.4 二叉树的五大性质（重点，每条都要会证）

二叉树的性质之所以能成为「必考」，是因为它们是纯粹的推理题：不写代码、不看图， 只给几个数就能算出答案。下面五条性质我们逐条证明，每条后面跟一道典型例题。 考试要求：不仅要背结论，还要能写出证明过程——尤其是性质 3，几乎年年考证明。

7.4.1 性质 1：第 i 层至多有 2ⁱ⁻¹ 个结点

证明（数学归纳法）

1. 基础：i = 1 时，第 1 层只有根结点，共 1 个，而 2¹⁻¹ = 2⁰ = 1，成立。
2. 归纳假设：设第 i − 1 层上至多有 2ⁱ⁻² 个结点。
3. 归纳步骤：第 i 层的结点全是第 i − 1 层结点的孩子。二叉树的每个结点至多有两个孩子， 所以第 i 层的结点数至多是第 i − 1 层的 2 倍，即 ≤ 2 × 2ⁱ⁻² = 2ⁱ⁻¹。
4. 由归纳原理，对一切 i ≥ 1 成立。∎

注意证明里用的关键条件是「每个结点至多两个孩子」。这就是为什么性质 1 对二叉树成立， 而对一般的 m 次树要改成 mⁱ⁻¹（第 i 层最多 mⁱ⁻¹ 个结点）。

7.4.2 性质 2：深度为 k 的二叉树至多有 2^k − 1 个结点

证明：把每一层的最大结点数加起来（等比数列求和）：

每一项的上界来自性质 1，求和用等比数列公式 (2k − 1)/(2 − 1) = 2k − 1。∎

推论（考试超高频）：n 个结点的满二叉树，叶子数 = (n + 1)/2，分支结点数 = (n − 1)/2。 推导：满二叉树有 n₀ = 2^k−1 个叶子、n₂ = 2^k−1 − 1 个度为 2 的结点 （可由性质 3 得出），两者之和正好是 2^k − 1 = n。

7.4.3 性质 3：n₀ = n₂ + 1（最重要的一个证明）

这条结论惊人地干净：叶子数永远比双分支结点数多 1，与 n₁ 无关、与树的形状无关。 证明的核心只有一个工具——「结点数 = 度数之和 + 1」，也就是 7.1.3 节推出的恒等式。

证明（数边法，考试标准写法）

1. 设二叉树共有 n 个结点，则 n = n₀ + n₁ + n₂。（按度数分类，不重不漏）
2. 二叉树是一棵树，所以边数（分支数）= n − 1。
3. 另一方面，从「结点发出多少条边」来看，度数为 1 的结点发出 1 条边，度数为 2 的结点发出 2 条边， 叶子不发出边，所以总边数 = n₁ + 2n₂。
4. 两条式子都等于边数，于是 n − 1 = n1 + 2n2。
5. 把第 1 步代入：n0 + n1 + n2 − 1 = n1 + 2n2， 两边消去 n₁ 得 n0 − 1 = n2，即 n₀ = n₂ + 1。∎

7.4.4 性质 4：n 个结点的完全二叉树深度为 ⌊log₂ n⌋ + 1

证明（夹逼法，看清「恰好」是怎么来的）

1. 设完全二叉树的深度为 k。由性质 2，深度为 k 的二叉树最多有 2^k − 1 个结点，所以 n ≤ 2k − 1，即 n + 1 ≤ 2k。
2. 关键的一步：完全二叉树的结点是「从上到下、从左到右」连续编号的， 所以只要深度是 k，前 k − 1 层的全部位置必然都有结点——如果前 k − 1 层缺了任何一个位置， 编号就会断档，那它就不是完全二叉树了。既然前 k − 1 层是满的，结点数就严格大于 2^k−1 − 1：n > 2k−1 − 1，即 n + 1 > 2k−1。
3. 把两式合起来：2k−1 < n + 1 ≤ 2k。
4. 两边取以 2 为底的对数：k − 1 < log2(n+1) ≤ k， 说明 k 就是「不小于 log₂(n+1) 的最小整数」，即 k = ⌈log₂(n+1)⌉。
5. 对整数 n，⌈log₂(n+1)⌉ 与 ⌊log₂ n⌋ + 1 恒等（可分别验证 n = 2^k − 1 与 n = 2^k−1 这两个边界），故深度 = ⌊log₂ n⌋ + 1。∎

为什么普通二叉树没有这个公式？因为第 2 步「前 k−1 层全满」对普通二叉树不成立： 一棵 10 个结点的右斜树深度是 10，而 ⌊log₂ 10⌋ + 1 = 4。 所以 性质 4 是「完全二叉树」四个字换来的特权，做题时一定要先确认题目说的是完全二叉树。

7.4.5 性质 5：完全二叉树的下标性质

证明（归纳法，直观版）

1. 先证 ②：对层序编号做归纳。根编号 1，它的左孩子是编号 2 = 2 × 1 ✓。 假设结点 i 的左孩子编号是 2i，那么结点 i + 1 的左孩子应该是多少？ 按层序编号的规则，结点按「父结点编号从小到大」的顺序依次认领孩子， 结点 i 的两个孩子占据了编号 2i 与 2i + 1，于是结点 i + 1 的孩子紧接着排在后面， 即 2i + 2 = 2(i + 1) ✓。归纳完成。
2. 再证 ③：由 ② 立刻得到——两个孩子是连续编号的，右孩子自然是 2i + 1。
3. 最后证 ①：既然左孩子是 2i、右孩子是 2i + 1，那么「谁是结点 j 的双亲」就是解方程 2i = j 或 2i + 1 = j，即 i = ⌊j/2⌋。∎

0 基版本（写代码时用）：把 tree[1..n] 改成 tree[0..n−1]， 只需把所有编号整体减 1 再化简：左孩子 2i + 1、右孩子 2i + 2、双亲 (i − 1) / 2。 建议自己动手推一遍这个换算；考试时若记混了两套公式，就用 i = 0（根）的特殊情况检验： 根没有双亲，(0 − 1)/2 在整数除法下等于 0，正好落在根自己身上。

7.5 二叉树的四种遍历（重点）

7.5.1 遍历的本质：把非线性结构线性化

树是非线性结构：一个结点有两条「往下的路」，程序没法像数组那样「顺着下标走一遍」。 要想系统地访问到每个结点、且每个结点恰好访问一次，就必须人为规定一个次序。 这个次序就是遍历（traversal）。

这句话不是空话，它直接解释了三件事：
① 为什么树能存进一维数组——先序 / 层序序列配上空标记就能唯一确定树形；
② 为什么树的很多算法都长一个样——都是「递归处理根和左右子树」，只是「访问根」的位置不同；
③ 为什么「已知两种遍历序列就能还原二叉树」——序列携带了完整的结构信息。

既然二叉树只有「根 D、左子树 L、右子树 R」三部分，那么按「先访问谁」排列， 就有 3! = 6 种次序。其中规定必须先左后右（左子树永远先于右子树）后，只剩三种：

7.5.2 手工遍历练习：一棵树写出四种序列

下面这棵树是本章的「主角」，后面的序列还原、遍历应用、线索化都用它。 请先自己在纸上写出四种序列，再展开答案核对。

7.5.3 四种遍历的动画演示

先看动画，再回来看代码。四个动画分别对应四种遍历，都会高亮「当前正在访问的结点」， 把「已经输出到序列里的结点」标成绿色，并在下方实时显示访问序列， 右侧还会显示递归栈 / 队列的内容。建议对照上面的手推结果逐帧核对。

① 先序遍历（根左右）：先把根处理掉，再一路向左，最后回到右边。注意「入栈即访问」的节奏。

② 中序遍历（左根右）：先钻进最左边，再出来访问根。注意根总是在「左子树全部走完之后」才出现。

③ 后序遍历（左右根）：根最后才被访问，所以每个结点都要等它的两棵子树都处理完——注意观察「结点被重复经过但不输出」的现象。

④ 层序遍历（队列）：没有递归，全靠一个队列。右侧会显示队列中当前的结点，请仔细观察「出队一个、入队它的孩子」这个节奏。

7.5.4 递归实现：三种遍历只差一行代码的位置

递归实现几乎是「照抄定义」，因为二叉树本身就是递归定义的。请特别注意三行代码的相对位置—— 它们的顺序一变，遍历方式就变了。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct TreeNode {
    char      val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

/* ============================================================
   三种递归遍历：只有"访问根"这一行的位置不同
   ============================================================ */

void preorder(TreeNode* root, vector<char>& out) {
    if (!root) return;                       // 递归出口：空子树
    out.push_back(root->val);                // ★ 位置 1：先访问根  → 根左右
    preorder(root->left, out);               // 再递归左子树
    preorder(root->right, out);              // 最后递归右子树
}

void inorder(TreeNode* root, vector<char>& out) {
    if (!root) return;
    inorder(root->left, out);                // 先递归左子树
    out.push_back(root->val);                // ★ 位置 2：中间访问根  → 左根右
    inorder(root->right, out);
}

void postorder(TreeNode* root, vector<char>& out) {
    if (!root) return;
    postorder(root->left, out);
    postorder(root->right, out);
    out.push_back(root->val);                // ★ 位置 3：最后访问根  → 左右根
}

/* ---------- 调试用：从"带 # 的先序序列"建树 ---------- */
TreeNode* build(const string& s, int& pos) {
    char c = s[pos++];
    if (c == '#') return nullptr;
    TreeNode* r = new TreeNode(c);
    r->left  = build(s, pos);
    r->right = build(s, pos);
    return r;
}

void printVec(const vector<char>& v) {
    for (char c : v) cout << c;
    cout << "\n";
}

int main() {
    /* 图 7-9 的主角树，先序带 # 的完整形态 */
    string s = "ABD##EG###C#F##";
    int pos = 0;
    TreeNode* root = build(s, pos);

    vector<char> a, b, c;
    preorder(root, a);  cout << "先序: "; printVec(a);   // ABDECFG
    inorder(root, b);   cout << "中序: "; printVec(b);   // DBEAFCG
    postorder(root, c); cout << "后序: "; printVec(c);   // DEBGFCA
    return 0;
}

复杂度：每个结点恰好被访问一次，每次访问做 O(1) 的工作，所以时间 O(n)； 空间是递归栈的深度，最好 O(log n)（完全二叉树），最坏 O(n)（斜树）。 这一点很关键——递归遍历的空间复杂度取决于树的高度，而不是结点总数。

7.5.5 非递归实现：用栈模拟递归

递归虽好，但有两个现实问题：① 树很深时（斜树）会撑爆系统栈，直接段错误； ② 有些场合（内存受限的嵌入式环境）不允许递归。所以必须会写非递归版。

本质：递归靠「函数调用栈」记住「回来之后该干什么」。 非递归就是自己开一个栈，把这个「待办事项」显式存起来。

• 先序非递归：最简单。访问根 → 右孩子入栈 → 左孩子入栈（注意先压右再压左， 这样出栈顺序才是先左后右）。
• 中序非递归：一路向左并把沿途结点压栈，直到空；然后弹栈访问， 再转向被弹出结点的右孩子，重复。这正好模拟了中序「左到底 → 根 → 右」的节奏。
• 后序非递归：最麻烦，因为根要最后访问，而根在栈里会「提前暴露」。 两种常用写法：双栈法（先序的变体：把压栈顺序改成先左后右， 得到「根右左」，再整体反转就是「左右根」）；或单栈 + last 指针 （记录上一次访问的结点，用来判断右子树是否已经处理完）。

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

struct TreeNode {
    char      val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

/* ---------- 先序非递归：栈。压栈顺序 = 先右后左 ---------- */
vector<char> preorderIter(TreeNode* root) {
    vector<char> out;
    if (!root) return out;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* p = st.top(); st.pop();
        out.push_back(p->val);                       // 出栈即访问
        if (p->right) st.push(p->right);              // 右孩子先入栈
        if (p->left)  st.push(p->left);               // 左孩子后入栈 → 先出栈
    }
    return out;
}

/* ---------- 中序非递归：一路向左压栈，弹栈访问后转向右子树 ---------- */
vector<char> inorderIter(TreeNode* root) {
    vector<char> out;
    stack<TreeNode*> st;
    TreeNode* p = root;
    while (p || !st.empty()) {
        while (p) { st.push(p); p = p->left; }       // 阶段 1：左到底，沿途全部入栈
        p = st.top(); st.pop();                      // 阶段 2：弹出栈顶
        out.push_back(p->val);                       //         访问它
        p = p->right;                                // 阶段 3：转向右子树，重复
    }
    return out;
}

/* ---------- 后序非递归（写法 A）：双栈法 ----------
   思路：模仿先序，但压栈顺序改成"先左后右"，得到的是"根右左"，
   把它整个反转就是"左右根" = 后序。 */
vector<char> postorderIter2Stack(TreeNode* root) {
    vector<char> out;
    if (!root) return out;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* p = st.top(); st.pop();
        out.push_back(p->val);                       // 此时得到的是"根右左"
        if (p->left)  st.push(p->left);               // 注意：与先序相反
        if (p->right) st.push(p->right);
    }
    reverse(out.begin(), out.end());                 // 反转 → 左右根
    return out;
}

/* ---------- 后序非递归（写法 B）：单栈 + last 指针 ----------
   last 记录"上一个被访问的结点"。弹栈前判断：
   若右子树存在且右子树不是刚访问完的那个，说明右子树还没走，先转过去。 */
vector<char> postorderIter1Stack(TreeNode* root) {
    vector<char> out;
    stack<TreeNode*> st;
    TreeNode* p = root;
    TreeNode* last = nullptr;
    while (p || !st.empty()) {
        while (p) { st.push(p); p = p->left; }        // 左到底
        TreeNode* top = st.top();
        if (top->right && top->right != last) {
            p = top->right;                           // 右子树还没走，先去走
        } else {
            out.push_back(top->val);                  // 左右都走完了，可以访问根
            last = top;
            st.pop();
        }
    }
    return out;
}

TreeNode* build(const string& s, int& pos) {
    char c = s[pos++];
    if (c == '#') return nullptr;
    TreeNode* r = new TreeNode(c);
    r->left = build(s, pos);
    r->right = build(s, pos);
    return r;
}

void printVec(const vector<char>& v) {
    for (char c : v) cout << c;
    cout << "\n";
}

int main() {
    string s = "ABD##EG###C#F##";
    int pos = 0;
    TreeNode* root = build(s, pos);

    printVec(preorderIter(root));            // ABDECFG
    printVec(inorderIter(root));             // DBEAFCG
    printVec(postorderIter2Stack(root));     // DEBGFCA
    printVec(postorderIter1Stack(root));     // DEBGFCA（两种写法结果必须一致）
    return 0;
}

层序遍历必须借助队列（先进先出，保证「同一层的结点按从左到右的顺序排队」）。 它的代码短得出奇，但用途极广：求树宽、按层输出、判断完全二叉树都要用它。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

struct TreeNode {
    char      val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

/* ---------- 层序遍历（BFS）：队列，出队一个就把它的孩子入队 ---------- */
vector<char> levelOrder(TreeNode* root) {
    vector<char> out;
    if (!root) return out;                      // ★ 一定要判空！
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* p = q.front(); q.pop();
        out.push_back(p->val);                   // 访问
        if (p->left)  q.push(p->left);           // 左孩子入队（保证同层从左到右）
        if (p->right) q.push(p->right);          // 右孩子入队
    }
    return out;
}

/* ---------- 分层输出：每层单独收集成一个 vector ---------- */
vector<vector<char>> levelOrderByLevel(TreeNode* root) {
    vector<vector<char>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();                       // ★ 关键：先固定住"这一层有多少个"
        vector<char> cur;
        for (int i = 0; i < sz; ++i) {           // 只处理这一层的 sz 个
            TreeNode* p = q.front(); q.pop();
            cur.push_back(p->val);
            if (p->left)  q.push(p->left);
            if (p->right) q.push(p->right);
        }
        res.push_back(cur);
    }
    return res;
}

/* ---------- 求树的最大宽度（结点数最多的那一层的结点数） ---------- */
int maxWidth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int best = 0;
    while (!q.empty()) {
        int sz = q.size();
        best = max(best, sz);
        for (int i = 0; i < sz; ++i) {
            TreeNode* p = q.front(); q.pop();
            if (p->left)  q.push(p->left);
            if (p->right) q.push(p->right);
        }
    }
    return best;
}

TreeNode* build(const string& s, int& pos) {
    char c = s[pos++];
    if (c == '#') return nullptr;
    TreeNode* r = new TreeNode(c);
    r->left = build(s, pos);
    r->right = build(s, pos);
    return r;
}

int main() {
    string s = "ABD##EG###C#F##";
    int pos = 0;
    TreeNode* root = build(s, pos);

    for (char c : levelOrder(root)) cout << c;           // ABCDEFG
    cout << "\n";
    for (auto& lv : levelOrderByLevel(root)) {
        for (char c : lv) cout << c;
        cout << " | ";
    }
    cout << "\n";                                        // A | BC | DEF | G |
    cout << "最大宽度 = " << maxWidth(root) << "\n";      // 3
    return 0;
}

7.5.6 已知遍历序列还原二叉树

这是遍历部分最爱考的题型。先记住三条结论，再学怎么做：

下面用主角树（先序 ABDECFG，中序 DBEAFCG）演示还原过程的每一步。 动画会把「当前处理的先序区间、中序区间」以及「哪一段是左子树、哪一段是右子树」全部标出来。

分治思路可以概括成三句话，代码就照着这三句话写：

1. 定位根：先序区间的第一个元素 pre[pl] 就是当前子树的根。
2. 划分区间：在中序序列里找到这个根的位置 k，则中序区间被分成 [il, k-1]（左子树）与 [k+1, ir]（右子树）；左子树的结点数是 k - il， 据此把先序区间也切成 [pl+1, pl+k-il]（左）与 [pl+k-il+1, pr]（右）。
3. 递归：对两个子区间分别递归，返回值接到根的左右指针上。

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

/* ============================================================
   由「先序 + 中序」序列重建二叉树（竞赛标准写法：全局数组 + 递归）
   ------------------------------------------------------------
   先序定根，中序分左右：
       pre[pl..pr] 是当前子树的先序区间，in[il..ir] 是对应的中序区间
       ① 根 = pre[pl]
       ② 在中序里找到根的位置 k ⇒ 左子树结点数 leftLen = k - il
          左子树：先序 [pl+1, pl+leftLen]   中序 [il, k-1]
          右子树：先序 [pl+leftLen+1, pr]   中序 [k+1, ir]
       ③ 对两个子区间递归，返回值直接接到根的左右孩子上
   用桶 pos[c] 把「在中序里找根」从 O(n) 降到 O(1)（字符可以直接开 128 的桶）
   时间复杂度 O(n)，空间 O(n)

   二叉树的静态数组表示：lc[u] / rc[u] 存左右孩子的下标，0 表示空子树
   ============================================================ */

const int N = 100005;             /* 结点数上限 */
char pre[N], in[N], post[N];      /* 先序、中序、后序序列（都按 1..n 存，1 基好写区间） */
int  pos[128];                    /* pos[c] = 字符 c 在「中序」里的下标，O(1) 找根 */
char val[N];                      /* 每个结点的值 */
int  lc[N], rc[N];                /* 左、右孩子的下标，0 表示空 */
int  q[N];                        /* 层序遍历用的手写队列 */
int  tot;                         /* 已经用掉的结点编号（从 1 开始） */
int  n;                           /* 结点个数 */

/* 申请一个新结点：静态数组版的 new */
int newNode(char c) {
    ++tot;
    val[tot] = c;
    lc[tot] = rc[tot] = 0;
    return tot;
}

/* 先序 + 中序：返回当前子树的根，0 表示空子树 */
int build(int pl, int pr, int il, int ir) {
    if (pl > pr || il > ir) return 0;                      /* 空子树 */
    char rootVal = pre[pl];                                /* ① 先序区间的第一个就是根 */
    int  k = pos[(int)rootVal];                            /* ② 根在中序中的位置 */
    int  leftLen = k - il;                                 /*    左子树结点个数 */
    int  u = newNode(rootVal);
    lc[u] = build(pl + 1, pl + leftLen, il, k - 1);        /* ③ 递归左子树 */
    rc[u] = build(pl + leftLen + 1, pr, k + 1, ir);        /*    递归右子树 */
    return u;
}

/* 后序 + 中序：只需把「先序取第一个」换成「后序取最后一个」，其余一模一样 */
int buildFromPost(int pl, int pr, int il, int ir) {
    if (pl > pr || il > ir) return 0;
    char rootVal = post[pr];                               /* ★ 后序的最后一个才是根 */
    int  k = pos[(int)rootVal];
    int  leftLen = k - il;
    int  u = newNode(rootVal);
    lc[u] = buildFromPost(pl, pl + leftLen - 1, il, k - 1);
    rc[u] = buildFromPost(pl + leftLen, pr - 1, k + 1, ir);
    return u;
}

/* ---------- 校验：对建出来的树做一次层序遍历（手写队列，竞赛常用） ---------- */
int levelOrder(int root, char out[]) {
    int len = 0;
    if (root == 0) return len;
    int head = 0, tail = 0;
    q[tail++] = root;
    while (head < tail) {
        int u = q[head++];
        out[len++] = val[u];
        if (lc[u]) q[tail++] = lc[u];
        if (rc[u]) q[tail++] = rc[u];
    }
    return len;
}

/* 顺便打印先序 / 中序，肉眼确认建出来的树与输入序列一致 */
void printPre(int u) { if (!u) return; putchar(val[u]); printPre(lc[u]); printPre(rc[u]); }
void printIn (int u) { if (!u) return; printIn(lc[u]); putchar(val[u]); printIn(rc[u]); }

/* 把字符串按 1 基装进数组（等价于竞赛里的 cin >> (pre + 1)） */
void load(const char* s, char dst[]) {
    n = (int)strlen(s);
    for (int i = 1; i <= n; ++i) dst[i] = s[i - 1];
}

int main() {
    load("ABDECFG", pre);
    load("DBEAFCG", in);
    load("DEBFGCA", post);
    for (int i = 1; i <= n; ++i) pos[(int)in[i]] = i;      /* 预处理：值 → 中序下标 */

    char out[N];

    tot = 0;
    int t1 = build(1, n, 1, n);
    int len1 = levelOrder(t1, out);
    printf("pre+in  -> 层序 ");
    for (int i = 0; i < len1; ++i) putchar(out[i]);
    printf("  先序 "); printPre(t1);
    printf("  中序 "); printIn(t1);
    printf("\n");                                          /* 层序 ABCDEFG */

    tot = 0;
    int t2 = buildFromPost(1, n, 1, n);
    int len2 = levelOrder(t2, out);
    printf("post+in -> 层序 ");
    for (int i = 0; i < len2; ++i) putchar(out[i]);
    printf("\n");                    /* ABCDEFG：两种方式得到同一棵树 */
    return 0;
}

7.5.7 遍历的七大应用（每个都要会默写）

学遍历不是为了背序列，而是为了用遍历的框架去解决一切树上的问题。 下面这七个函数几乎是所有二叉树习题的「零件库」，请把它们的代码骨架刻进肌肉记忆。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

struct TreeNode {
    char      val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

/* ---------- 1. 统计结点总数：后序，O(n) ---------- */
int countNodes(TreeNode* r) {
    if (!r) return 0;
    return 1 + countNodes(r->left) + countNodes(r->right);
}

/* ---------- 2. 求树的深度：后序，O(n) ----------
   注意空树深度为 0，叶子深度为 1。 */
int depth(TreeNode* r) {
    if (!r) return 0;
    return 1 + max(depth(r->left), depth(r->right));
}

/* ---------- 3. 统计叶子结点个数 ---------- */
int countLeaves(TreeNode* r) {
    if (!r) return 0;
    if (!r->left && !r->right) return 1;               // 左右都空 → 是叶子
    return countLeaves(r->left) + countLeaves(r->right);
}

/* ---------- 4. 交换所有结点的左右子树 ---------- */
void swapChildren(TreeNode* r) {
    if (!r) return;
    swap(r->left, r->right);                          // 交换本结点
    swapChildren(r->left);                            // 继续处理（已经换过位置的）左右子树
    swapChildren(r->right);
}

/* ---------- 5. 判断两棵二叉树是否完全相同 ---------- */
bool isSame(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;                        // 都空 → 相同
    if (!a || !b) return false;                       // 一个空一个不空 → 不同
    if (a->val != b->val) return false;                // 根的值不同 → 不同
    return isSame(a->left, b->left) && isSame(a->right, b->right);
}

/* ---------- 6. 求第 k 层的结点个数（根算第 1 层） ---------- */
int countLevelK(TreeNode* r, int k) {
    if (!r || k < 1) return 0;
    if (k == 1) return 1;                             // 到达目标层
    return countLevelK(r->left, k - 1) + countLevelK(r->right, k - 1);
}

/* ---------- 7. 判断是否为完全二叉树：层序 + 标记法 ----------
   思路：层序遍历，一旦遇到"孩子不全"的结点（缺左或缺右），
   就把 seenIncomplete 置为 true；之后遇到的任何结点都必须是叶子，
   否则编号就断档了，不是完全二叉树。
   还要特别注意：只有右孩子没有左孩子，直接判定失败。 */
bool isComplete(TreeNode* root) {
    if (!root) return true;                           // 空树约定为完全二叉树
    queue<TreeNode*> q;
    q.push(root);
    bool seenIncomplete = false;                      // 是否已经遇到过"孩子不全"的结点
    while (!q.empty()) {
        TreeNode* p = q.front(); q.pop();
        if (p->left) {
            if (seenIncomplete) return false;         // 断档之后又出现了孩子 → 失败
            q.push(p->left);
        } else {
            seenIncomplete = true;                    // 没有左孩子 → 从这里开始断档
        }
        if (p->right) {
            if (seenIncomplete) return false;         // 包含了"只有右孩子"的非法情形
            q.push(p->right);
        } else {
            seenIncomplete = true;
        }
    }
    return true;
}

/* ---------- 附加：销毁整棵树（必须后序） ---------- */
void destroy(TreeNode* r) {
    if (!r) return;
    destroy(r->left);
    destroy(r->right);
    delete r;
}

TreeNode* build(const string& s, int& pos) {
    char c = s[pos++];
    if (c == '#') return nullptr;
    TreeNode* r = new TreeNode(c);
    r->left = build(s, pos);
    r->right = build(s, pos);
    return r;
}

int main() {
    int pos = 0;
    TreeNode* root = build("ABD##EG###C#F##", pos);   // 图 7-9 的主角树

    cout << "结点数   = " << countNodes(root) << "\n";   // 7
    cout << "深度     = " << depth(root) << "\n";        // 4
    cout << "叶子数   = " << countLeaves(root) << "\n";  // 3（D、G、F）
    cout << "第 3 层   = " << countLevelK(root, 3) << "\n"; // 3（D、E、F）
    cout << "是完全二叉树? " << (isComplete(root) ? "是" : "否") << "\n";  // 否

    int pos2 = 0;
    TreeNode* same = build("ABD##EG###C#F##", pos2);
    cout << "两棵树相同? " << (isSame(root, same) ? "是" : "否") << "\n"; // 是

    swapChildren(root);                                // 交换后层序应为 ACBFGED
    vector<char> lv;
    {   /* 内联层序遍历，避免与其它文件重名 */
        queue<TreeNode*> q; q.push(root);
        while (!q.empty()) {
            TreeNode* p = q.front(); q.pop();
            lv.push_back(p->val);
            if (p->left) q.push(p->left);
            if (p->right) q.push(p->right);
        }
    }
    cout << "交换左右子树后层序: ";
    for (char c : lv) cout << c;
    cout << "\n";

    destroy(root); destroy(same);
    return 0;
}

7.6 线索二叉树

7.6.1 为什么需要线索：n + 1 个空指针的浪费

先算一笔账。二叉链表有 n 个结点，每个结点 2 个指针域，共 2n 个指针域。 其中真正被用上的只有「连向孩子」的那些，恰好每条树边对应一个，即 n − 1 个。 于是空指针域有：

也就是说，整整一半以上的指针是空的（当 n 较大时，空指针占比接近 1/2）。 与此同时，我们在遍历时还得额外开一个栈（或者递归栈）来记住「从哪来、该回哪去」—— 而这些信息其实恰好就是「前驱 / 后继」关系。两边一对照，想法自然就出来了：

具体做法是：给每个结点加两个标志位 ltag 与 rtag：

ltag

ltag = 0：left 指向左孩子（原本的含义）； ltag = 1：left 指向该结点在遍历序列中的前驱（我们称这根指针为「前驱线索」）。

rtag

rtag = 0：right 指向右孩子； rtag = 1：right 指向该结点在遍历序列中的后继（称为「后继线索」）。

线索链表

加上线索的二叉链表。相应地，树就叫线索二叉树（threaded binary tree）； 按线索化的次序不同，分为先序线索二叉树、中序线索二叉树、后序线索二叉树。

线索化

把二叉树变成线索二叉树的过程。做法就是一次遍历，在「访问结点」时顺手把空指针改成线索。

下图是主角树的中序线索化结果。对照中序序列 DBEAFCG 看： D 的后继是 B、G 的前驱是 E、G 的后继是 F……每一条线索都对应序列里相邻的一对结点。

7.6.2 三种线索化的规则

线索化的规则可以用一句话统一概括：按某种次序遍历二叉树，遍历过程中把「上一个访问的结点」记成 pre， 遇到当前结点 p 有空指针域时，就用 pre 和 p 互相连线。具体来说：

• 若 p->left 为空 → 令 p->left = pre（ltag = 1），即 p 的前驱线索；
• 若 pre 非空且 pre->right 为空 → 令 pre->right = p（rtag = 1）， 即 pre 的后继线索。

「按什么次序遍历」决定了得到哪种线索二叉树，三种次序的差别如下表。 中序线索二叉树是考得最多、也是唯一能完美 O(1) 双向找前驱后继的一种（后序线索找后继通常还需要知道双亲）。

7.6.3 中序线索化的 C++ 实现

代码只有二十来行，但有一个细节必须小心：递归线索化左子树时， 原来的 p->left 可能已经被改成了前驱线索，所以要先判断 ltag == 0 再递归， 否则会顺着线索跑到别的子树上去，造成死循环或错误。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

/* ============================================================
   中序线索二叉树
   ltag / rtag = 0 表示指针指向孩子；= 1 表示指针是线索
   ============================================================ */
struct ThreadNode {
    char        val;
    ThreadNode* left;
    ThreadNode* right;
    int         ltag;      // 0: left 是左孩子   1: left 是前驱线索
    int         rtag;      // 0: right 是右孩子  1: right 是后继线索
    explicit ThreadNode(char v)
        : val(v), left(nullptr), right(nullptr), ltag(0), rtag(0) {}
};

/* ---------- 建树工具（普通二叉树） ---------- */
ThreadNode* build(const string& s, int& pos) {
    char c = s[pos++];
    if (c == '#') return nullptr;
    ThreadNode* r = new ThreadNode(c);
    r->left  = build(s, pos);
    r->right = build(s, pos);
    return r;
}

/* ============================================================
   中序线索化核心：一次中序遍历，pre 始终指向"刚访问过的那个结点"
   ============================================================ */
void inorderThread(ThreadNode* p, ThreadNode*& pre) {
    if (!p) return;

    inorderThread(p->left, pre);          // ① 递归左子树（此时 p->left 一定还是孩子指针）

    /* ② 处理当前结点的左空指针 → 前驱线索 */
    if (!p->left) { p->left = pre; p->ltag = 1; }

    /* ③ 处理前驱结点的右空指针 → 后继线索（此时 pre 就是 p 的前驱） */
    if (pre && !pre->right) { pre->right = p; pre->rtag = 1; }

    pre = p;                              // ④ p 成为下一个结点的前驱

    /* ⑤ 递归右子树。注意：此处必须用 rtag 判断！
       因为如果 p 没有右孩子，上面的步骤已经把 p->right 改成了后继线索，
       直接递归会顺着线索跑到别的子树里，造成死循环。 */
    if (p->rtag == 0) inorderThread(p->right, pre);
}

/* ---------- 封装的线索化入口：带一个"头结点" ----------
   头结点是常用的工程技巧：它的 left 指向根，right 指向中序最后一个结点，
   于是"第一个结点的前驱"和"最后一个结点的后继"都有地方指了。 */
ThreadNode* createInorderThread(ThreadNode* root) {
    ThreadNode* head = new ThreadNode('\0');    // 头结点，值无意义
    head->ltag = 0; head->rtag = 1;
    if (!root) { head->left = head; head->right = head; return head; }
    head->left = root;
    ThreadNode* pre = head;                     // pre 从头结点开始，天然处理"第一个结点无前驱"
    inorderThread(root, pre);
    pre->right = head; pre->rtag = 1;           // 最后一个结点的后继指向头结点
    head->right = pre;                          // 头结点的右指针指向中序最后一个结点
    return head;
}

/* ============================================================
   在中序线索树上找后继：不用栈、不用递归，O(1)
   ============================================================ */
ThreadNode* inorderNext(ThreadNode* p) {
    if (p->rtag == 1) return p->right;          // 有后继线索，直接用
    ThreadNode* q = p->right;                   // 否则后继 = 右子树"最左下"的结点
    while (q->ltag == 0 && q->left) q = q->left;
    return q;
}

/* ---------- 在中序线索树上找前驱（对称） ---------- */
ThreadNode* inorderPrev(ThreadNode* p) {
    if (p->ltag == 1) return p->left;
    ThreadNode* q = p->left;                    // 前驱 = 左子树"最右下"的结点
    while (q->rtag == 0 && q->right) q = q->right;
    return q;
}

/* ---------- 利用线索做中序遍历：空间 O(1)，没有栈也没有递归 ---------- */
vector<char> inorderByThread(ThreadNode* head) {
    vector<char> out;
    ThreadNode* p = head->left;                 // 从头结点出发到根
    while (p && p->ltag == 0 && p->left) p = p->left;   // 走到中序第一个结点（最左下）
    while (p && p != head) {
        out.push_back(p->val);
        p = inorderNext(p);                     // 顺着后继线索一路走
    }
    return out;
}

int main() {
    int pos = 0;
    ThreadNode* root = build("ABD##EG###C#F##", pos);   // 图 7-9 的主角树
    ThreadNode* head = createInorderThread(root);

    cout << "中序遍历（靠线索，无栈无递归）: ";
    for (char c : inorderByThread(head)) cout << c;      // DBEAFCG
    cout << "\n";

    /* 验证"找前驱/后继"：找出中序第一个结点 D，然后一路顺着后继走 */
    ThreadNode* first = head->left;
    while (first->ltag == 0 && first->left) first = first->left;
    cout << "第一个结点是 " << first->val << "\n";         // D
    cout << "D 的后继是 " << inorderNext(first)->val << "\n";  // B
    ThreadNode* last = head->right;                      // 头结点右指针 = 中序最后一个结点
    cout << "最后一个结点是 " << last->val << "\n";         // G
    cout << "G 的前驱是 " << inorderPrev(last)->val << "\n";   // E
    return 0;
}

7.7 树、森林与二叉树的转换

7.7.1 三条互逆的转换规则

7.2.3 节已经埋下伏笔：孩子兄弟表示法用两个指针就存下了一棵普通树。 既然存储结构已经和二叉树一模一样，那么「树」与「二叉树」之间就必然存在一一对应关系。 转换规则其实只有一句话：把「第一个孩子」当作左孩子，把「下一个兄弟」当作右孩子。

把上图的做法推广到森林，规则同样机械：

下面是「树 → 二叉树」的动画演示。左侧是原树，右侧是逐步长出来的二叉树， 动画会依次完成「加兄弟线」「抹掉非长子的连线」「旋转定型」三个阶段。

7.7.2 必背结论：树与森林的遍历对应关系

转换规则本身不难记，难的是考试里那句「树的后序遍历 = 对应二叉树的中序遍历」—— 很多人第一次看到都会怀疑是不是印错了。我们用一个可以直接验证的方法说明它。

另外还要知道树的层序遍历：它和二叉树的层序遍历没有上述对应关系， 因为转换会改变结点的层次（兄弟被压到了下一层）。树的层序遍历要自己用队列做： 根入队，出队时把它的所有孩子（而不是两个孩子）依次入队。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

/* ============================================================
   树 <-> 二叉树 的相互转换
   统一用"左孩子右兄弟"的结点结构，从而两种形态共用一份数据
   ============================================================ */
struct Node {
    char  val;
    Node* child;      // 树：第一个孩子      二叉树：左孩子
    Node* sibling;    // 树：下一个兄弟      二叉树：右孩子
    explicit Node(char v) : val(v), child(nullptr), sibling(nullptr) {}
};

/* ---------- 树的前序遍历 = 二叉树的前序遍历 ---------- */
void treePre(Node* r, vector<char>& out) {         // 对树：根 → 各子树
    if (!r) return;
    out.push_back(r->val);
    for (Node* c = r->child; c; c = c->sibling) treePre(c, out);
}
void btPre(Node* r, vector<char>& out) {           // 对二叉树：根 → 左 → 右
    if (!r) return;
    out.push_back(r->val);
    btPre(r->child, out);
    btPre(r->sibling, out);
}

/* ---------- 树的后序遍历 = 二叉树的中序遍历 ---------- */
void treePost(Node* r, vector<char>& out) {        // 对树：各子树 → 根
    if (!r) return;
    for (Node* c = r->child; c; c = c->sibling) treePost(c, out);
    out.push_back(r->val);
}
void btIn(Node* r, vector<char>& out) {            // 对二叉树：左 → 根 → 右
    if (!r) return;
    btIn(r->child, out);
    out.push_back(r->val);
    btIn(r->sibling, out);
}

/* ---------- 树的层次遍历：出队一个，把它的"所有孩子"入队 ---------- */
vector<char> treeLevel(Node* root) {
    vector<char> out;
    if (!root) return out;
    queue<Node*> q; q.push(root);
    while (!q.empty()) {
        Node* p = q.front(); q.pop();
        out.push_back(p->val);
        for (Node* c = p->child; c; c = c->sibling) q.push(c);   // 注意是所有孩子
    }
    return out;
}

/* ---------- 森林 → 二叉树：把各棵树的根用右链串起来 ---------- */
Node* forestToBinary(const vector<Node*>& roots) {
    if (roots.empty()) return nullptr;
    for (size_t i = 0; i + 1 < roots.size(); ++i)
        roots[i]->sibling = roots[i + 1];        // 前一棵树的根 → 右孩子 = 后一棵树的根
    return roots[0];
}

/* ---------- 二叉树 → 森林：沿根的右链依次劈开 ---------- */
vector<Node*> binaryToForest(Node* root) {
    vector<Node*> res;
    Node* p = root;
    while (p) {
        Node* nxt = p->sibling;                  // 先存下一条右链
        p->sibling = nullptr;                    // 断开
        res.push_back(p);
        p = nxt;
    }
    return res;
}

void print(const char* tag, const vector<char>& v) {
    cout << tag;
    for (char c : v) cout << c;
    cout << "\n";
}

int main() {
    /* 构造图 7-11 的树：A(B(E,F), C, D(G)) */
    Node* A = new Node('A'); Node* B = new Node('B'); Node* C = new Node('C');
    Node* D = new Node('D'); Node* E = new Node('E'); Node* F = new Node('F');
    Node* G = new Node('G');
    A->child = B;  B->sibling = C;  C->sibling = D;      // A 的孩子链：B → C → D
    B->child = E;  E->sibling = F;                        // B 的孩子链：E → F
    D->child = G;                                        // D 的孩子链：G

    vector<char> a, b;
    treePre(A, a);  print("树的前序   : ", a);            // ABEFCDG
    btPre(A, b);    print("二叉树的前序: ", b);           // ABEFCDG（相同！）

    vector<char> c, d;
    treePost(A, c); print("树的后序   : ", c);            // EFBCGDA
    btIn(A, d);     print("二叉树的中序: ", d);           // EFBCGDA（相同！）

    print("树的层序   : ", treeLevel(A));                 // ABCDEFG

    /* 森林 → 二叉树 → 森林 */
    Node* X = new Node('X'); Node* Y = new Node('Y');
    X->child = Y;
    vector<Node*> fo = { A, X };                          // 森林：两棵树
    Node* bin = forestToBinary(fo);
    cout << "森林转二叉树后，根的右链长度 = " << binaryToForest(bin).size() << "\n";  // 2
    return 0;
}

7.8 赫夫曼树与最优前缀编码（重点）

7.8.1 路径长度与带权路径长度 WPL

前面讲的是「树长什么样」，现在换个角度：给叶子结点赋上权值，然后问 「怎么把树造成让所有叶子的『代价之和』最小」。这就是赫夫曼树要解决的问题。 先精确定义两个量：

路径长度

从树中一个结点到另一个结点所经过的边数。

结点的带权路径长度

从根到该结点的路径长度 × 该结点的权值，即 depth(v) × weight(v)（根深度记 0）。

树的带权路径长度（WPL

Weighted Path Length：树中所有叶子结点的带权路径长度之和。

其中 n 是叶子个数，w_i 是第 i 个叶子的权值，l_i 是该叶子到根的路径长度（层数 − 1）。 只有叶子参与计算——这是最容易出错的地方。

赫夫曼树（最优二叉树）

在给定 n 个权值作为 n 个叶子结点的所有二叉树中， WPL 最小的那棵（可能不唯一），称为赫夫曼树（Huffman tree），也叫最优二叉树。

7.8.2 赫夫曼算法：每次合并两个最小的

一句话本质：把所有叶子当作一堆独立的树，反复取出权值最小的两棵合并成一棵新树， 新树的权是两者之和，直到只剩一棵树。

算法步骤（n 个叶子，共需 n − 1 次合并）：

1. 把 n 个权值 w1, w2, …, wn 看成 n 棵只有一个根结点的树，组成森林 F。
2. 从 F 中选出根结点权值最小的两棵树，作为左、右子树构造一棵新树，新树的根权值为两者之和。
3. 从 F 中删除这两棵树，把新树加入 F。
4. 重复 2、3，直到 F 中只剩一棵树。这棵树就是赫夫曼树。

下面用权值集合 {2, 3, 4, 7, 8, 9}（总和 33）完整手推一遍。 请务必自己先算一遍再看表，这个例子在考卷上出现的频率极高。

下面动画逐帧演示这五步合并，并实时累加 WPL。注意观察「每次合并后森林中权值的排序变化」。

7.8.3 为什么赫夫曼树是最优的

严格的证明要用「贪心选择性质 + 最优子结构」的交换论证，这里给出直观而不失严谨的说明。 先看两条关于最优树的显然性质：

1. 权值越大的叶子离根越近。 反证：如果存在两个叶子 x、y 满足 w_x > w_y 但 depth(x) > depth(y)， 把两个叶子的位置对调，WPL 的变化量是 wx·depth(y) + wy·depth(x) − wx·depth(x) − wy·depth(y) = (wx − wy)(depth(y) − depth(x)) < 0， 即 WPL 变小了，与最优性矛盾。
2. 最优树一定是一棵「满」的树，没有度为 1 的结点。 反证：若存在度为 1 的结点，把它的唯一孩子直接接到它的位置上，所有后代深度减 1，WPL 严格变小。

贪心选择性质：设 w₁、w₂ 是最小的两个权值，则存在一棵最优树， 其中 w₁ 与 w₂ 是兄弟，且深度最大。
论证：由性质 1 与 2 可知，深度最大的叶子必然成对出现（否则会有度为 1 的结点）， 取其中两个叶子 a、b，深度都是 L。交换论证：把 w₁ 换到 a 的位置、w₂ 换到 b 的位置， WPL 的变化量是 (w1 − wa)L + (w2 − wb)L = L[(w1 + w2) − (wa + wb)] ≤ 0， 因为 w₁、w₂ 是最小的两个，所以 w₁ + w₂ ≤ w_a + w_b。 也就是说，把最小的两个放到最深处不会让结果变差，于是可以放心地先把它们合并。

最优子结构：合并 w₁、w₂ 得到新权值 w' = w₁ + w₂ 之后， 原问题变成了「用 {w', w₃, …, w_n} 这 n − 1 个权值构造最优树」的同型子问题： WPL(原) = WPL(子问题) + w1 + w2。 因为 w₁ + w₂ 是固定开销，最小化原 WPL 等价于最小化子问题的 WPL。 于是对子问题继续贪心即可，这正是一个标准的贪心 + 归纳结构。

7.8.4 赫夫曼编码：让常用字符用短码

赫夫曼树最著名的应用是数据压缩。想法非常自然：一篇文章里不同字符出现的频率差别极大 （英文里 e 出现得最多，z 最少），如果所有字符都用同样长度的编码（如 ASCII 的 8 位）， 那就是对高频字符的浪费。要让总长度最短，就该让高频字符用短编码、低频字符用长编码—— 这恰好就是「构造一棵 WPL 最小的二叉树」！

前缀编码

一组编码中，任何一个编码都不是另一个编码的前缀。 例如 {0, 10, 110, 111} 是前缀编码；而 {0, 01, 011} 不是（0 是 01 的前缀）。

为什么前缀编码能唯一译码

译码时从左往右逐位读：一旦读到的位串等于某个字符的编码，就立刻确定这个字符， 然后从头开始读下一段。因为没有任何编码是别人的前缀，所以中途绝不会出现「读到的这一段既可能是 A 也可能是 B 的前半截」的歧义， 译码路径唯一。

赫夫曼编码

以字符出现频率为权值构造赫夫曼树，令左分支为 0、右分支为 1， 则从根到每个叶子路径上的 0/1 序列就是该字符的编码。它一定是前缀编码—— 因为字符只放在叶子上，任何一条从根到叶的路径都不会是另一条路径的前缀。

平均码长

编码一个字符的平均位数 = WPL / Σwi（总权值）。 对赫夫曼编码，这个平均值是所有前缀编码中最小的。

回到刚才的例子：字符 a~f 的频率分别是 2, 3, 4, 7, 8, 9，总频率 33。 把 7.8.2 节构造出的赫夫曼树每个左分支标 0、右分支标 1，从根走到叶子，就得到编码表。 下表把两种编码的总位数放在一起对比（等长编码需要 ⌈log₂ 6⌉ = 3 位）。 请注意：这里约定「权值相同时，先被合并出来的那棵树作左孩子」， 这样左右不再随意，编码表就是唯一确定的（这也是 7.8.5 节要讲的「唯一化」问题）。

这里有一个必须专门讲清楚的细节：为什么频率最低的 a、b 拿到了 4 位码，而频率居中的 d、e、f 只有 2 位？ 因为这棵树的形状是「一边深、一边浅」：合并过程 2+3=5 → 4+5=9 → 7+8=15 → 9+9=18 → 15+18=33 中， a、b 最早被合并，所以在树里被「压」到了最深处（第 5 层，码长 4）； 而 7、8、9 这三棵子树直到最后才被合并，离根最近（第 3 层，码长 2）。 这正是 7.8.1 节那条规律的体现：权越大的叶子离根越近。 但请注意一个反直觉的现象：d(7)、e(8)、f(9) 的权值互不相同，码长却都是 2—— 码长只由树形决定，并不严格随频率单调，千万不要用「按频率排序」去猜码长。

把这个编码表用起来看看效果。假设原文一共 33 个字符（a 出现 2 次、b 3 次、c 4 次、d 7 次、e 8 次、f 9 次）：

• 用 3 位等长编码存储：需要 33 × 3 = 99 位。
• 用 赫夫曼编码存储：需要 80 位。
• 压缩后是原来的 80/99 ≈ 80.8%，节省约 19.2%。 真实文本的字符频率分布比这个例子更悬殊（英文里 e 约占 12.7%，z 只占 0.07%）， 所以实际压缩率通常更好。
• 顺便验证前缀性质：编码集合是 {1110, 1111, 110, 00, 01, 10}。 可以发现 11 本身不是任何字符的编码，因此以 11 开头的 1110、1111 不会与别人冲突；0、1 也都不是编码。 任意两个编码之间都不存在前缀关系，所以译码时从左往右读、读到一个完整编码就立刻切分，绝不会产生歧义。

下面动画演示赫夫曼编码的生成过程：先构造树，再沿树从根到叶读出每个字符的 0/1 编码， 最后把赫夫曼编码总位数与等长编码总位数放在一起比较。

7.8.5 规范赫夫曼编码与「按字典序的赫夫曼编码」

赫夫曼编码有一个工程上的小麻烦：它不唯一。左右孩子可以互换，导致编码不同； 解码方如果没有拿到编码表，就无法解码。解决办法是约定一套标准规则， 让双方各算各的也能算出完全一样的编码。这就是规范赫夫曼编码（canonical Huffman code）。

规范编码的两条规则（工程与竞赛中通用的约定）：

1. 码长分配规则：先算出每个字符的码长（这一步用赫夫曼算法，只保留长度信息，不关心左右）。
2. 字典序赋值规则：按 (码长, 字符) 排序—— 先按码长从小到大排，码长相同的按字符的字典序排； 然后依次赋码：
   • 第一个（最短码长中的最小编号字符）赋 全 0；
   • 设当前码长为 L、当前编码为 c，则下一个字符的编码是 把 c 加 1（作为 L 位二进制数），再在末尾补 0 直到长度等于它的码长；
   • 若下一个字符的码长与当前相同，就只加 1 不补 0。

用我们的例子演示：字符 a~f 的频率是 2, 3, 4, 7, 8, 9， 由赫夫曼算法得到的码长是 a=4, b=4, c=3, d=2, e=2, f=2 （注意 e、f 的码长是 2 而不是 3——这就是为什么必须先老老实实跑一遍赫夫曼算法， 不能用「频率排序」去猜码长）。按 (码长, 字符) 排序后依次赋码：

有意思的是，这一组规范编码与 7.8.4 节表格里的赫夫曼编码一模一样。这不是巧合： 7.8.4 节约定的「权值相同时先合并出来的作左孩子、左 0 右 1」， 恰好使字典序小的字符拿到了字典序小的编码。但如果把左右子树互换， 得到的编码就变成 a=0001, b=0000, c=001, d=11, e=10, f=01—— WPL 仍然是 80（最优），但编码已经乱序了。规范编码的价值就在这里： 它不依赖「谁在左谁在右」，只要双方用同一份码长表，就一定算出同一份编码。 这正是 DEFLATE（zip / gzip / PNG 用的压缩格式）等真实压缩格式的做法： 传输时只传「每个字符的码长」，编码本身由规范规则在两端各自算出来。

7.8.6 构造赫夫曼树 + 生成编码的完整实现

实现要点有三条：① 用小根堆（priority_queue 配 greater）每次取最小的两个， 复杂度 O(n log n)；② 编码用从叶子往上回溯的方式生成（避免从根递归传字符串）； ③ 因为要判断「左 0 右 1」，回溯时要记录当前结点是双亲的左孩子还是右孩子，所以结点里要存一个 parent 字段——写成数组版就是双亲的下标 t[i].par。

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

/* ============================================================
   赫夫曼树 + 赫夫曼编码（竞赛写法：静态数组建树 + 小根堆合并）
   ------------------------------------------------------------
   结点用数组 t[] 存：前 n 个是叶子，后面是合并出来的 n-1 个内部结点
       t[i].w    权值（叶子是频率；内部结点是两个孩子权值之和）
       t[i].l/r  左 / 右孩子下标（-1 表示没有）
       t[i].par  双亲下标（-1 表示根）—— 专门为了「从叶子往上回溯」求编码
       t[i].ch   该叶子对应的字符（内部结点无意义）

   合并顺序：每次取权值最小的两棵树合并成新结点，用小根堆维护，
             共合并 n-1 次，复杂度 O(n log n)。
   两个重要结论（算出来一定相等，本例都是 80）：
       ① WPL = Σ 叶子权值 × 叶子深度（也就是码长）
       ② WPL = 所有非叶（内部）结点权值之和   ← 边合并边累加即可，竞赛最常用
   ============================================================ */

const int N = 5005;                  /* 叶子数上限：结点总数 2N-1 不超过数组 */
struct Node {
    int  w;                          /* 权值 */
    int  l, r;                       /* 左、右孩子下标，-1 表示空 */
    int  par;                        /* 双亲下标，-1 表示根 */
    char ch;                         /* 该叶子对应的字符 */
};
Node t[2 * N];
int  n;                              /* 叶子个数 */

/* 小根堆里存 (权值, 结点下标)：按权值升序取最小；
   权值相同时按下标升序，保证每次合并的结果可复现 */
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

/* 建树：chars / w 是 n 个叶子的字符与频率，返回根的下标 */
int buildHuffman(const char chars[], const int w[]) {
    while (!pq.empty()) pq.pop();
    for (int i = 0; i < n; ++i) {
        t[i].w = w[i]; t[i].l = t[i].r = t[i].par = -1; t[i].ch = chars[i];
        pq.push(make_pair(t[i].w, i));
    }
    int tot = n;                             /* 下一个可用的内部结点下标 */
    while (pq.size() > 1) {                  /* 一共合并 n-1 次 */
        int a = pq.top().second; pq.pop();   /* 先取出的是较小的 → 做左孩子（左 0 右 1） */
        int b = pq.top().second; pq.pop();
        t[tot].w = t[a].w + t[b].w;
        t[tot].l = a; t[tot].r = b; t[tot].par = -1; t[tot].ch = 0;
        t[a].par = t[b].par = tot;           /* 孩子记住双亲，方便往上回溯 */
        pq.push(make_pair(t[tot].w, tot));
        ++tot;
    }
    return tot - 1;                          /* 最后合并出来的就是根 */
}

/* 从叶子往上回溯到根求编码：左 0 右 1。
   回溯拿到的是「从下往上」的序列，最后要反转一次。
   （从根 DFS 往下传字符串也行，但回溯法不用递归传参，代码更短） */
string codeOf(int leaf) {
    string s;
    int cur = leaf;
    while (t[cur].par != -1) {
        int p = t[cur].par;
        s += (t[p].l == cur) ? '0' : '1';
        cur = p;
    }
    reverse(s.begin(), s.end());
    return s;
}

/* 法一：WPL = Σ 权值 × 深度（叶子顺着 par 往上数深度） */
long long wplByLeaves() {
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        int d = 0, cur = i;
        while (t[cur].par != -1) { ++d; cur = t[cur].par; }
        sum += 1LL * d * t[i].w;
    }
    return sum;
}

/* 法二：WPL = 所有内部结点（非叶结点）权值之和 */
long long wplByInternal(int root) {
    long long sum = 0;
    for (int i = n; i <= root; ++i) sum += t[i].w;
    return sum;
}

/* 只求 WPL 时连树都不用建：小根堆里合并 n-1 次，把每次的合并结果加起来 */
long long wplByHeap(int w[]) {
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 0; i < n; ++i) q.push(w[i]);
    long long wpl = 0;
    while (q.size() > 1) {
        int a = q.top(); q.pop();
        int b = q.top(); q.pop();
        wpl += a + b;                        /* 技巧：WPL = 所有合并结果之和 */
        q.push(a + b);
    }
    return wpl;
}

int main() {
    const char ch[6] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int w[6] = { 2, 3, 4, 7, 8, 9 };
    n = 6;

    int root = buildHuffman(ch, w);

    int totalW = 0;
    for (int i = 0; i < n; ++i) totalW += w[i];

    int totalBits = 0;
    for (int i = 0; i < n; ++i) {
        string code = codeOf(i);
        int bits = (int)code.size() * w[i];
        totalBits += bits;
        printf("%c  频率 %d  编码 %s  码长 %d  贡献 %d\n",
               ch[i], w[i], code.c_str(), (int)code.size(), bits);
    }

    int equalLen = 3;                                    /* ceil(log2 6) = 3 位等长编码 */
    printf("赫夫曼总位数 = %d\n", totalBits);
    printf("等长编码总位数 = %d\n", totalW * equalLen);
    printf("WPL(按叶子) = %lld   WPL(按内部结点) = %lld   WPL(小根堆直算) = %lld\n",
           wplByLeaves(), wplByInternal(root), wplByHeap(w));       /* 都是 80 */
    printf("平均码长 = %.4f\n", (double)totalBits / totalW);        /* 80/33 ≈ 2.4242 */
    return 0;
}

如果题目只要求码长而不要求具体编码，还有个经典的 O(n log n) 双数组优化写法： 先把权值排序，然后用两个队列——一个存原始叶子（已排序），一个存合并出的新结点（天然有序）—— 每次从两个队列的队头里挑出较小的两个。这样就把堆的 log 因子变成了纯线性扫描。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

/* ============================================================
   赫夫曼 WPL 的 O(n log n) 写法：排序 + 两个队列
   关键观察：合并产生的新结点权值是"单调不减"的，
   所以不需要堆，用两个队列的队头比较就能每次拿到最小值。
   （q1 存原始叶子，已排序；q2 存合并出的新结点，天然有序）
   ============================================================ */
long long huffmanWPL(vector<int> w) {
    sort(w.begin(), w.end());                        // 唯一的 O(n log n) 来自排序
    queue<long long> q1, q2;
    for (int x : w) q1.push(x);

    auto pickMin = [&]() -> long long {              // 从两个队头里取最小的
        long long v;
        if (q1.empty()) { v = q2.front(); q2.pop(); return v; }
        if (q2.empty()) { v = q1.front(); q1.pop(); return v; }
        if (q1.front() <= q2.front()) { v = q1.front(); q1.pop(); }
        else                          { v = q2.front(); q2.pop(); }
        return v;
    };

    long long wpl = 0;
    int n = w.size();
    for (int i = 0; i < n - 1; ++i) {                // 共合并 n-1 次
        long long a = pickMin();
        long long b = pickMin();
        wpl += a + b;                                // 技巧 1：WPL = 所有合并结果之和
        q2.push(a + b);
    }
    return wpl;
}

int main() {
    vector<int> w = { 2, 3, 4, 7, 8, 9 };
    cout << "WPL = " << huffmanWPL(w) << "\n";       // 80
    vector<int> w2 = { 5, 7, 2, 3, 11 };
    cout << "WPL = " << huffmanWPL(w2) << "\n";      // 见 7.13 节自测题第 4 题
    return 0;
}

7.9 并查集：用双亲表示法的森林管理集合

7.9.1 为什么树还能用来「分组」

并查集（disjoint set union, DSU）解决的是这样一类问题： 有 n 个元素，需要支持两种操作—— 合并两个集合（union）和查询两个元素是否属于同一集合（find）。 典型场景：判断无向图中的连通性、Kruskal 最小生成树（第 09 讲）、 亲戚关系、网络连通、等式约束的传递闭包。

表示方法非常巧妙：每个集合用一棵树表示，整片森林就是一个并查集； 树的根就是该集合的代表元，树中每个结点只存双亲的下标—— 这正好就是 7.2.1 节的双亲表示法！于是：

• find(x)：沿着 fa[] 一路往上走，直到根（fa[x] == x），返回根的下标。 根相同 ⇔ 属于同一集合。
• unite(a, b)：先 find 到两个根，把其中一个根的双亲改成另一个根，两棵树就合成一棵。 （C++ 里 union 是关键字，所以竞赛代码里这个操作都叫 unite，也有写 merge 的。）

下面动画演示并查集的两个关键优化。路径压缩让 find 顺路把经过的结点直接挂到根上， 按秩合并让矮树挂到高树上，两者合起来把单次操作的均摊复杂度压到 O(α(n))—— α 是反阿克曼函数，对任何现实中的 n（哪怕 n 是 10⁸⁰）都不超过 5，可以认为是常数。

7.9.2 完整实现：路径压缩 + 按秩合并

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

/* ============================================================
   并查集（Disjoint Set Union，DSU）—— 竞赛标准写法
   ------------------------------------------------------------
   用「双亲表示法」的森林表示若干个集合：fa[i] == i 说明 i 是根（集合代表元）
       find(x)   ：沿 fa 一路往上走到根；顺路把路径上所有点直接挂到根
                   → 路径压缩（递归一行搞定）
       unite(a,b)：先 find 到两个根，再把一棵树挂到另一棵下面
                   → 按大小合并（小树挂到大树上）
                     或 按秩合并（矮树挂到高树上），两者等价，任选其一
   两个优化都用上，单次操作的均摊复杂度 O(α(n))：α 是反阿克曼函数，
   对任何现实中的 n（哪怕 10^80）都不超过 5，可以认为是常数。
   ============================================================ */

const int N = 100005;              /* 元素个数上限 */
int fa[N];                         /* 双亲下标：fa[i] == i 说明 i 是根 */
int siz[N];                        /* 只对根有意义：集合的元素个数（按大小合并用） */
int rnk[N];                        /* 只对根有意义：树高的上界（按秩合并用） */
int sets;                          /* 当前集合个数 */

/* 初始化：n 个元素各自成一个集合
   易错点：别忘了 siz[i] = 1，否则按大小合并会把新集合当成空集合 */
void init(int n) {
    for (int i = 1; i <= n; ++i) { fa[i] = i; siz[i] = 1; rnk[i] = 0; }
    sets = n;
}

/* ---------- 查：路径压缩（递归版，竞赛最常用的一行写法） ----------
   把查找路径上所有结点的双亲都直接改成根，树被「压扁」，后续查找几乎 O(1) */
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);      /* ★ 递归赋值 = 路径压缩 */
}

/* ---------- 查：路径压缩（迭代版，避免深树时递归爆栈） ---------- */
int findIter(int x) {
    int root = x;
    while (fa[root] != root) root = fa[root];         /* 第一趟：先找到根 */
    while (fa[x] != root) {                           /* 第二趟：把路径上的点全挂到根 */
        int nxt = fa[x];
        fa[x] = root;
        x = nxt;
    }
    return root;
}

/* ---------- 并：按大小合并（小树挂到大树上） ---------- */
void unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;                             /* 已经在同一集合，无需合并 */
    if (siz[ra] < siz[rb]) swap(ra, rb);              /* 保证 ra 是较大的那个根 */
    fa[rb] = ra;                                      /* rb 挂到 ra 下面 */
    siz[ra] += siz[rb];
    --sets;
}

/* ---------- 并：按秩合并（矮树挂到高树上，另一种等价优化） ---------- */
void uniteByRank(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (rnk[ra] < rnk[rb]) swap(ra, rb);
    fa[rb] = ra;
    if (rnk[ra] == rnk[rb]) ++rnk[ra];                /* 秩相同时，合并后树高 +1 */
    --sets;
}

/* 判两个元素是否属于同一集合（Kruskal 判环用的就是它） */
bool same(int a, int b) { return find(a) == find(b); }

int main() {
    init(8);                                          /* 8 个元素 1..8 */
    unite(1, 2);
    unite(3, 4);
    unite(2, 4);                                      /* {1,2,3,4} 合成一个集合 */
    unite(5, 6);
    unite(7, 8);

    printf("各元素的双亲: ");
    for (int i = 1; i <= 8; ++i) printf("%d ", fa[i]);
    printf("\n");              /* 注意 4 还挂在 3 下面：合并时只把"根"挂到根上 */

    for (int i = 1; i <= 8; ++i) find(i);  /* 对全部元素做一次 find：顺路压缩 */
    printf("再次压缩后: ");
    for (int i = 1; i <= 8; ++i) printf("%d ", fa[i]);
    printf("\n");                          /* 4 的双亲也直接变成了根，树被压扁 */

    printf("1 和 4 同集合? %s\n", same(1, 4) ? "是" : "否");   /* 是 */
    printf("1 和 5 同集合? %s\n", same(1, 5) ? "是" : "否");   /* 否 */
    printf("当前集合个数 = %d\n", sets);                       /* 3 */

    /* 换成「按秩合并」做同样的事，结果完全一样：两种优化可以互换 */
    init(8);
    uniteByRank(1, 2); uniteByRank(3, 4); uniteByRank(2, 4);
    uniteByRank(5, 6); uniteByRank(7, 8);
    printf("按秩合并: 集合个数 = %d, 1 和 4 同集合? %s\n",
           sets, same(1, 4) ? "是" : "否");                   /* 3, 是 */

    printf("迭代版 findIter(4) = %d（与 find 结果相同，且不递归）\n", findIter(4));
    return 0;
}

7.9.3 它为什么在这里出现：为 Kruskal 铺路

并查集在本课程里最重要的用途，是第 09 讲的 Kruskal 最小生成树算法。 Kruskal 的做法是「把所有边按权值从小到大排序，依次尝试加入， 若这条边的两个端点已经在同一个连通块里，就跳过（否则会成环）， 否则加入」。这里「两个端点是否已在同一个连通块」正是 same(u, v)， 「加入这条边」正是 unite(u, v)。

用一个具体的片段感受一下它有多简洁（完整版在第 09 讲给出）：

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

/* 并查集（双亲表示法 + 路径压缩 + 按秩合并）：算法与 7.9.2 节完全一致，
   这里只是把 fa / rnk 装进 struct，方便当成参数在函数间传递 */
struct DSU {
    vector<int> parent, rnk;
    explicit DSU(int n) : parent(n), rnk(n, 0) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rnk[rx] < rnk[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rnk[rx] == rnk[ry]) ++rnk[rx];
        return true;
    }
};

struct Edge { int u, v, w; };

/* Kruskal 的骨架：排序 + 并查集判环，O(E log E) */
long long kruskal(int n, vector<Edge> edges, int& usedEdges) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });
    DSU d(n);
    long long mst = 0;
    usedEdges = 0;
    for (const Edge& e : edges) {
        if (d.unite(e.u, e.v)) {        // 不在同一集合 → 这条边安全，加入生成树
            mst += e.w;
            ++usedEdges;
            if (usedEdges == n - 1) break;   // n 个点的生成树恰好 n-1 条边
        }
    }
    return mst;
}

int main() {
    /* 4 个点、5 条边的最小生成树：答案 6（边 0-1 w=1、1-2 w=2、2-3 w=3） */
    vector<Edge> es = { {0,1,1}, {1,2,2}, {2,3,3}, {0,3,10}, {1,3,7} };
    int used = 0;
    cout << "最小生成树权值 = " << kruskal(4, es, used)
         << "，用了 " << used << " 条边\n";
    return 0;
}

7.10 C++ 实战：坑与写法

树这一章的代码写起来不难，但「能过编译」和「能跑对」之间隔着一堆坑。 下面这些是本讲配套实验里出现频率最高的错误，请逐条对照自己的代码检查。

#include <iostream>
using namespace std;

/* 为了让这段示例可以独立编译，先给出结点定义。
   实际工程里它来自公共头文件。 */
struct TreeNode {
    char      val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

/* ✗ 错误：先删了根，就再也找不到它的孩子了 → 后序之外的顺序都会漏删 */
void destroyWrong(TreeNode* r) {
    if (!r) return;
    delete r;                  // 灾难：子树指针随 r 一起没了，内存泄漏
}

/* ✓ 正确：后序 —— 先删左右子树，最后删自己 */
void destroy(TreeNode* r) {
    if (!r) return;
    destroy(r->left);
    destroy(r->right);
    delete r;
}

int main() {
    /* 手工搭一棵 A(B, C) 的小树，然后正确地释放它 */
    TreeNode* r = new TreeNode('A');
    r->left = new TreeNode('B');
    r->right = new TreeNode('C');

    destroy(r);                // ✓ 用后序释放，不会有任何泄漏
    // destroyWrong(r);        // ✗ 千万别这么写：B、C 两块内存会永远丢失
    cout << "released\n";
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    char      val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

/* ✗ 错误：root 为空时还会执行一次 p->val，空指针解引用 → 崩溃 */
vector<char> bad(TreeNode* root) {
    vector<char> out;
    queue<TreeNode*> q;
    q.push(root);                     // 把 nullptr 也塞进去了
    while (!q.empty()) {
        TreeNode* p = q.front(); q.pop();
        out.push_back(p->val);        // ← 空指针解引用！
        if (p->left)  q.push(p->left);
        if (p->right) q.push(p->right);
    }
    return out;
}

/* ✓ 正确：进函数先判空；也不要把 nullptr 压进队列 */
vector<char> good(TreeNode* root) {
    vector<char> out;
    if (!root) return out;            // ★ 第一行就判空
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        TreeNode* p = q.front(); q.pop();
        out.push_back(p->val);
        if (p->left)  q.push(p->left);
        if (p->right) q.push(p->right);
    }
    return out;
}

int main() {
    cout << good(nullptr).size() << "\n";   // 0：空树安全返回
    // bad(nullptr);                        // ✗ 一旦对空树调用就会崩溃
    TreeNode* r = new TreeNode('A');
    r->left = new TreeNode('B');
    r->right = new TreeNode('C');
    for (char c : good(r)) cout << c;       // ABC
    cout << "\n";
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

/* 1 基公式用在 0 基数组上 —— 编译能过，结果全错 */
int leftChild1Based(int i)  { return 2 * i; }        // 只对 tree[1..n] 成立
int parent1Based(int i)     { return i / 2; }        // 只对 tree[1..n] 成立

/* 0 基版本 */
int leftChild0Based(int i)  { return 2 * i + 1; }
int rightChild0Based(int i) { return 2 * i + 2; }
int parent0Based(int i)     { return (i - 1) / 2; }  // i=0 时得 0（根自己）

/* ★ 最稳的写法：干脆空出 tree[0]，从 1 开始存，与教材公式完全一致。
   此时双亲 = i/2，左孩子 = 2i，右孩子 = 2i+1，绝不会记混。 */
vector<int> heap(1);          // heap[0] 空着不用

int main() {
    /* 用 0 基数组存 {A,B,C,D,E,F,G} 这棵完全二叉树 */
    vector<char> tree = { 'A','B','C','D','E','F','G' };
    int n = tree.size();

    /* 用 0 基公式找 D(下标 3) 的双亲和孩子 */
    int i = 3;
    cout << "D 的双亲 = " << tree[parent0Based(i)] << "\n";        // B
    if (leftChild0Based(i) < n)  cout << "左孩子 " << tree[leftChild0Based(i)] << "\n";
    if (rightChild0Based(i) < n) cout << "右孩子 " << tree[rightChild0Based(i)] << "\n";

    /* 反例：把 1 基公式用在同一个 0 基数组上，结果就错了 */
    cout << "误用 1 基公式得到 D 的双亲 = " << tree[parent1Based(i)] << "\n";   // 错！得到 C

    /* 想要 1 基语义，就老老实实空出 heap[0] */
    heap = { 0, 'A','B','C','D','E','F','G' };       // heap[1..7] 才是数据
    cout << "1 基写法下 heap[3] = " << (char)heap[3]
         << "，其双亲 heap[3/2] = " << (char)heap[3 / 2] << "\n";       // B
    return 0;
}

7.11 工程视角：树结构在真实系统里撑起了什么

前面十节我们把树从定义一路做到了并查集。你可能会问：这些看起来像是为考试才设计出来的结构， 在真实系统里到底出现在哪？答案是几乎无处不在，只是藏在你平时看不见的地方。 这一节把本章的每种树都对号入座，并对每个落点回答三个问题： 用的是什么结构 → 为什么非它不可 → 代价是什么。

7.11.1 数据库索引：为什么是 B+ 树，而不是二叉搜索树

先记住两个数量级，它们决定了这一小节的每一个结论。

两者相差 10⁵ 倍，即 5 个数量级：内存读十万次，才抵得上磁盘读一次。 所以索引优化的从来不是比较次数，而是磁盘 I/O 次数——第 01 讲的 O(log n) 到了磁盘上， 还要再乘一个「每次读几次盘」的系数。

二叉搜索树（BST）每次比较排除一半数据，O(log₂ n)，确实漂亮。但放到磁盘上， 它的问题不是「矮」，而是「瘦」：一个结点只存 1 个键 + 2 个指针，在 4 KB 的页里 只占十几个字节却独占一页——读一个结点 = 一次磁盘 I/O，而这一次 I/O 只换来 1 个键。于是：

这 27 个结点在磁盘上东一个西一个，每次都要重新寻道。更糟的是：若插入的是有序主键又没有平衡机制， BST 会退化成斜树（7.10 的坑 1），27 层变成 1 亿层——崩溃的东西从函数栈换成了系统响应时间。

B+ 树（B-plus tree）的解法是把「瘦」改成「胖」：让一个结点就等于一个磁盘页。 这一句话解释了它的全部设计：

• 结点大小 = 页大小（常见 4 KB，InnoDB 默认 16 KB），一次 I/O 读进来的整页都是有用的键； 页内是有序数组，可以在页内二分，页内比几十次也只算 1 次 I/O。
• 一页塞几百个键，扇出（fan-out）从 2 变成几百，树高从 log₂ n 变成 log_扇出 n。几千万行数据树高只有 3～4 层，查任意一行只要 3～4 次 I/O。
• 数据全在叶子层，内部结点只存键当「路标」，一页能装更多键、树更矮， 而且每次查询都走到叶子，代价与数据落在哪无关，性能可预测。
• 叶子之间用链表串起来，这是范围查询（WHERE id BETWEEN 100 AND 200）的命门： 定位到 100 后顺着叶子链表顺序扫到 200 即可：只有第一次是随机 I/O，后面全是顺序 I/O， 比随机 I/O 快一到两个数量级。

下面这段代码不实现 B+ 树的插入删除，只按页内布局算出「一个结点能装多少个键」， 再由此推出「几层能撑多少行」——「树高 3 层撑住几千万行」就是这么几个除法的结果。

// btree_page_layout.cpp —— 一个页能装多少个键？树高为什么只有 3～4 层？
#include <iostream>
#include <cmath>
using namespace std;

/* B+ 树的结点在磁盘上就是一个「页」，即一次磁盘 I/O 读进来的单位。
   页内布局：[ 页头 ][ 键 ]…[ 键 ][ 孩子指针 ]…[ 孩子指针 ] */
struct PageLayout {
    int pageBytes;    // 页大小：4KB = 4096，InnoDB 默认 16KB
    int headerBytes;  // 页头（页号、校验和等）开销
    int keyBytes;     // 一个键占几字节（int 主键 = 4）
    int ptrBytes;     // 一个孩子指针占几字节（64 位 = 8）
    int rowBytes;     // 叶子层行指针占几字节
};

/* 内部结点：K 个键 + (K+1) 个孩子指针 + 页头 ≤ pageBytes
   → K ≤ (pageBytes − headerBytes − ptrBytes) / (keyBytes + ptrBytes)
   K 是「一页放几个键」，孩子个数 K + 1 就是扇出。 */
int internalKeys(const PageLayout& p) {
    int rest = p.pageBytes - p.headerBytes;
    return (rest - p.ptrBytes) / (p.keyBytes + p.ptrBytes);
}

/* 叶子结点：只有键 + 行指针，没有孩子指针 */
int leafRows(const PageLayout& p) {
    return (p.pageBytes - p.headerBytes) / (p.keyBytes + p.rowBytes);
}

// 按亿 / 万打印
void show(const char* name, long long rows) {
    if (rows >= 100000000)
        cout << name << " = " << rows << " 行 ≈ " << rows / 100000000
             << " 亿 " << rows % 100000000 / 10000 << " 万行\n";
    else
        cout << name << " = " << rows << " 行 ≈ " << rows / 10000 << " 万行\n";
}

int main() {
    PageLayout p4k  = { 4096,  16, 4, 8, 8 };   // 4KB 页
    PageLayout p16k = { 16384, 16, 4, 8, 8 };   // 16KB 页

    int k4 = internalKeys(p4k);
    int f4 = k4 + 1;                            // 扇出 = 孩子个数
    int rows4 = leafRows(p4k);
    cout << "【4KB 页】最多 " << k4 << " 个键、扇出 " << f4
         << "，叶子最多 " << rows4 << " 行\n";
    show("  3 层", (long long)f4 * f4 * rows4);
    show("  4 层", (long long)f4 * f4 * f4 * rows4);

    int k16 = internalKeys(p16k);
    int f16 = k16 + 1;
    int rows16 = leafRows(p16k);
    cout << "【16KB 页】最多 " << k16 << " 个键、扇出 " << f16
         << "，叶子最多 " << rows16 << " 行\n";
    show("  3 层", (long long)f16 * f16 * rows16);

    /* 二叉搜索树呢？它每个结点只有 2 个孩子，树高 ≈ log2(行数)。 */
    long long rows = (long long)f4 * f4 * rows4;
    int h = (int)ceil(log2((double)rows));
    cout << "二叉搜索树存 " << rows << " 行要 " << h
         << " 层 → 最坏 " << h << " 次 I/O\n";
    cout << "B+ 树只要 3 次。按一次随机 I/O 10ms 算："
         << h * 10 << "ms  vs  30ms\n";
    cout << "I/O 次数由树高决定，树高由扇出决定 —— 这就是 B+ 树「矮」的秘密。\n";
    return 0;
}

结论：4 KB 页 + int 主键 → 一个内部结点 339 个键、扇出 340 → 3 层索引 3930 万行； 换成 16 KB 页扇出 1364，3 层撑到 25 亿行；而同样 3930 万行，二叉搜索树要 26 层。 真实索引「只有 3～4 层」不是数据少，而是每一层都被撑得极宽——把「应该很快吧」变成 「3 次 I/O、30 毫秒」这样能对账的数字，正是工程判断力的来源。

第 02 讲留了一个问题：为什么主键索引既不用链表也不用顺序表？现在可以回答了：

7.11.2 文件系统：目录树与 inode

Linux 里没有「文件夹」这个数据结构，只有一棵树：根是 /，目录是分支结点，文件是叶子。 cd /home/user/a.txt 就是在树上从根走一条路径：/ → home → user → a.txt。7.1.1 那句「从根到结点的路径唯一」，在工程里就是绝对路径； 相对路径则是从当前结点出发的一条向下路径。

更关键的是 inode：ext4 里目录项只保存「名字 → inode 号」，真正的元数据（大小、权限、时间戳、 数据块地址）都在 inode 里。翻译成本章的术语：inode 是树的结点，目录项是指向结点的指针。 而每个目录都有的 . 和 ..，恰好就是 7.2.1 双亲表示法里的双亲指针 （. 指向自己，.. 指向双亲）。7.9 的并查集用的是同一套表示法： 「找根」就是沿双亲指针向上爬——你在 shell 里敲 cd ..， 和 find(x) 里那句 x = parent[x]，是同一个动作。 （顺带一提，硬链接就是两个目录项指向同一个 inode。）

7.11.3 并查集：不只是 Kruskal 的配角

7.9.3 说过，并查集在本课程里的主要用途是第 09 讲 Kruskal 最小生成树算法判环： 边按权值排序后依次取出，两端点已属同一集合就丢弃（会成环），否则 union 并收下这条边。 整个算法 O(e log e)，瓶颈在排序。

但它的真实工作量远不止于此：并查集擅长的始终是把元素合并成等价类，并随时回答 「这两个元素是不是同一类」。凡是能翻译成这句话的场景，它几乎都是最优解：

图像处理里的用法值得多说一句。连通区域标记（connected-component labeling） 是二值图像分析的第一步（数细胞、数零件、OCR 切字都要它）：第一趟给前景像素临时标号， 发现相邻两个标号其实属于同一块就 union 合并；第二趟把标号换成 find(标号)，得到最终编号。 几百万个前景像素能顺畅跑完，全靠并查集近似 O(1) 的均摊代价（7.9.2）。

7.11.4 赫夫曼编码：ZIP、gzip、JPEG、MP3 的共同底座

7.8 节用贪心构造了 WPL 最小的树，得到最优前缀编码；它在工程里的名字就是 赫夫曼编码（Huffman coding），今天几乎所有常见压缩格式都在用它：

• ZIP / gzip / PNG / HTTP 压缩：都用 DEFLATE：LZ77（找重复串）+ 赫夫曼编码（压符号）。
• JPEG：对量化后的 DCT 系数做游程编码，再用赫夫曼编码输出；标准表是预先统计好的码表。
• MP3 / AAC：量化后的频谱系数用赫夫曼编码压缩，配一组预定义码表。
• HTTP/2 的 HPACK：请求头字符串用静态赫夫曼表压缩（HTTP 头重复度极高）。

为什么敢用变长编码？因为赫夫曼树给出的是前缀码（prefix code）： 没有任何一个码字是另一个码字的前缀。这直接保证了解码无歧义—— 解码就是从第一个比特开始沿树从根往下走（约定左 0 右 1），走到叶子就输出一个符号、再回到根； 因为不会有码字停在内部结点上，所以不存在「读到一半不知道要不要继续」的歧义。 换个说法：前缀码把「切分比特流」变成了「在树上走到叶子」， 7.5 的遍历与 7.8.4 的编码表在这里合成了一个每秒几千万次的循环。

代价也很清楚：

1. 码表必须传给解码方，所以压缩文件头部总要存一份（或像 JPEG、MP3 那样用标准表）； 文件很小时，码表开销会盖过省下的空间。
2. 只有频率偏斜时才划算：低频符号可能被拉长到十几比特，若 256 种字节几乎均匀出现 （已加密数据），平均码长接近 8 比特，收益几乎为零。
3. 不能随机访问：第 k 个符号的位置取决于前面所有符号。DEFLATE 的对策是分块： 每 32～64 KB 一块、各自建表，牺牲一点压缩率换回「可以按块定位」。

7.11.5 堆与优先队列：调度器、定时器与最短路

二叉堆是本章内容的「特例组合」：它是完全二叉树（7.3.2），所以能用数组顺序存储（7.3.3）， 下标满足 7.4.5 的公式；同时只维护一条比 BST 弱得多的序关系——每个结点不大于它的孩子。 这条「弱序」换来的是：取最值 O(1)、插入删除 O(log n)，且常数极小、内存连续。

工程上，堆几乎就是「优先队列」：

• 操作系统任务调度：从就绪队列里挑优先级最高（或虚拟运行时间最小）的任务投入 CPU。 （Linux 的 CFS 用的是红黑树，因为它还需要「按时间顺序找下一个」——选结构要看操作集合。）
• 定时器：一台服务器可能挂着几十万个超时事件，事件循环只需知道「哪一个最先到期」， libuv（Node.js 的底座）等都用最小堆维护，看堆顶是 O(1)。代价：取消任意定时器要先找到它 （O(n)），所以工程实现常额外记下「堆内下标」，把删除压到 O(log n)。
• Dijkstra / Prim 的优化（第 09 讲）：把「选距离最小的未确定顶点」交给小根堆， Dijkstra 从 O(n²) 降到 O((n + e) log n)，稀疏图上差一个数量级。
• 堆排序与 Top-K（第 11 讲）：堆排序是原地 O(n log n)；「10 亿个数里找最大的 100 个」 只要一个大小 100 的小根堆，空间 O(k)，数据不必全读进内存。

代价要记牢：堆只保证堆顶是最值，其余元素之间没有任何有序关系。所以它不擅长按序遍历、 查找任意元素（O(n)）、求中位数。想要「有序 + 任意查找」，得回到平衡搜索树或第 10 讲的哈希表。

7.11.6 五种树的工程分工：一张表看清该选谁

把上面五个落点收拢成一张表。注意最后两列——「是否适合磁盘」和「是否支持范围查询」 才是选型的关键维度，而不是「查找复杂度」。

怎么记？一句话：约束越弱，代价越小；想要什么能力，就得付出对应的结构复杂度。 普通二叉树什么都不保证，所以什么都快不了；加「左小右大」成了 BST，却会退化成斜树； 再加「平衡」是红黑树，代价是插入删除要旋转；把结点放大成磁盘页就是 B+ 树， 用页内查找换树高骤降；堆放弃「有序」只留「最值」，于是在自己的赛道上无可替代。 没有最好的结构，只有最匹配操作集合的结构。

7.12 本章小结

树这一章的内容看起来很多，但骨架非常清楚：一套术语 + 三种存储 + 五条性质 + 四种遍历 + 三大应用。 下面把最需要记住的东西压成几张表。

7.12.1 术语与结构速查

7.12.2 二叉树性质与公式速查

7.12.3 复杂度与算法对比

7.12.4 一句话总结每一节

• 树的定义：递归定义，关键词是「唯一根」与「互不相交」，直接推出「n 个结点 n − 1 条边」。
• 三种存储：双亲表示法向上快（并查集用），孩子表示法向下快，孩子兄弟表示法把树变成二叉树。
• 二叉树：左右有序、每点至多两棵子树；斜树 / 满二叉树 / 完全二叉树是三种最重要的特例。
• 顺序存储：只有完全二叉树才配用数组，普通二叉树最坏浪费率可达 99% 以上。
• 五大性质：层上限、总量上限、n₀ = n₂ + 1、完全二叉树深度、下标公式。
• 四种遍历：前中后序是「访问根的三个时机」，层序靠队列；遍历的本质是把树线性化。
• 序列还原：先序 / 后序定位根，中序划分左右；缺了中序就不唯一。
• 线索二叉树：把 n + 1 个空指针变成前驱 / 后继线索，中序线索最实用。
• 树与森林的转换：左孩子右兄弟；树的前序 = 二叉树的前序，树的后序 = 二叉树的中序。
• 赫夫曼树：每次合并最小的两个，WPL 最小；由此得到最优前缀编码，且 n 个叶子的赫夫曼树共 2n − 1 个结点。
• 并查集：用双亲表示法的森林表示「集合的集合」，路径压缩 + 按秩合并后近似 O(1)。

7.13 考点清单与自测题

7.13.1 自测题（六道，答案折叠）

第 1 题（术语与性质）：一棵树的度为 4，其中度为 1、2、3 的结点数分别是 8、10、2， 求这棵树的叶子结点数。

第 2 题（性质计算）：判断下列数据是否可能存在，并说明理由：

1. 一棵二叉树有 10 个结点，其中度为 2 的结点有 4 个；
2. 一棵二叉树有 10 个结点，其中度为 2 的结点有 5 个；
3. 一棵完全二叉树有 100 个结点，其中叶子有 51 个。

第 3 题（遍历与还原）：已知一棵二叉树的先序序列是 ABDECF， 中序序列是 DBEACF。请还原这棵二叉树，并写出它的后序序列与层序序列。

第 4 题（赫夫曼树与编码）：字符 a~f 在文本中出现的次数依次是 2, 3, 4, 7, 8, 9。请构造赫夫曼树，求 WPL、每个字符的赫夫曼编码， 并与「3 位等长编码」比较总位数。

第 5 题（树 ↔ 二叉树转换）：已知一棵树 T 的先序遍历是 ABEFCGD， 后序遍历是 EFBGCDA。请画出这棵树，并写出它转换成的二叉树的前序与中序序列。

第 6 题（并查集）：初始有 8 个元素 0~7，依次执行下列操作： union(0,1)、union(2,3)、union(1,3)、 union(4,5)、union(6,7)。 请画出每一步之后的森林（用双亲数组表示），说明当前有几个集合， 并在最后一步执行 find(3) 后写出被路径压缩的结点。

7.13.2 上机练习建议

光看不写是学不会树的。建议按下面的顺序把本章代码亲手敲一遍（每道都在 30 分钟以内）：