Lecture 12: 二叉树、二叉搜索树与树遍历（Binary Trees, BSTs & Traversals）（对应课程真实讲座 L21–L22）

目录 · ← l11 · l13 →

Lecture 12: 二叉树、二叉搜索树与树遍历（Binary Trees, BSTs & Traversals）（对应课程真实讲座 L21–L22）

概述

本讲把”节点 + 指针”的思路从一条链升级成一棵树：每个节点至多有两个孩子指针 left/right，形成二叉树。核心数据结构是二叉搜索树（BST）——它给二叉树加上”左小右大”的排序约束，让查找/插入/删除在平衡时只需 O(log n)；本讲完整给出递归的插入、查找与三分支的删除算法，以及前序/中序/后序/层序四种遍历。树也是文件压缩（霍夫曼编码）与图论等领域中反复出现的组织形态。 对应官方讲座：L21（Wednesday, July 29 — Binary Trees, Binary Search Trees, and Tree Traversals）与 L22（Thursday, July 30 — More on Binary Trees）；官方课件另附 tree-notes.pdf（手写讲义）、traversal-puzzle.pdf（遍历谜题）与 bst-code.zip（课上代码）可自行研读。

核心概念与算法原理

1. 从链表到树：术语与 TreeNode。 链表每个节点只有一个 next，是一条”退化”的树；树的每个节点可以有多个孩子。二叉树（binary tree）约定每个节点至多两个孩子，分别叫左孩子 left、右孩子 right。沿用树形结构的通用术语：最上面的节点叫根（root），没有孩子的节点叫叶（leaf），一个节点连同它下面的所有后代叫一棵子树（subtree），从根到最深叶的”边数”叫树的高度。树的节点结构与链表节点如出一辙，只是把 next 换成两个指针：

struct TreeNode {
    int data;
    TreeNode *left;   // 左孩子（没有则为 nullptr）
    TreeNode *right;  // 右孩子（没有则为 nullptr）
};

与 head 类似，一个 root 指针保存根节点的地址，是整棵树的唯一入口。二叉堆用数组表示之所以可行，是因为堆是”完全二叉树”（逐层从左到右填满、无空洞）；而普通二叉树形状任意，必须用节点 + 指针才能真正表达。

2. 二叉搜索树（BST）的性质。 BST = 二叉树 + 一条排序规则：对任意节点，其左子树里所有值都小于它，右子树里所有值都大于它（课程通常假定键不重复；若允许重复，可约定相等的放左边或直接忽略）。这条规则是”自找的”：它让查找变成”每走一步就排除掉半棵树”。以树根 50 为例：

           50            ← 左子树 {20,30,40} < 50 < 右子树 {60,70,80}
          /  \
        30    70
        / \   / \
      20  40 60  80        ← 每一层都同样满足"左小右大"

注意规则是对”整棵子树”而言，不只是对直接孩子：例如 40 虽然大于 30，但它处在 30 的右子树，同时仍小于根 50，这完全合法。

3. 查找：顺着大小方向走。 查找 40：与根 50 比，40 < 50 → 进左子树；与 30 比，40 > 30 → 进右子树；与 40 比，命中。每比较一次就放弃一侧子树，走的高度是多少步数就是多少。递归版的三行骨架：空节点返回 false（没找到）；相等返回 true；否则把问题缩小到左或右子树继续。因为树的高度决定步数，所以”树长得越高，操作越慢”——这正是本讲复杂度讨论的核心。

4. 插入：找到空位挂上去。 插入新值的过程就是一次”失败的查找”：按大小一路下探，直到撞上一个 nullptr，就把新节点挂在那里。递归写法妙在传引用：void insertRec(TreeNode *&node, int v)——当递归到达空位时，node 引用直通”父节点的 left/right 字段（或 root）”，node = new TreeNode(v) 便自动把新节点焊回树上，不需要返回指针再手动接线。插入 21 到以 44 为根的子树，等价于把 21 插进”44 的右子树”…… 如此递归下去，直到某个节点的空孩子成为新节点的家。

5. 删除：三情形逐一击破。 删除是 BST 最精细的操作，先递归找到目标节点（值与目标相等的那一个），再按它的孩子数分三种情形：

情形1：没有孩子（叶子）——直接摘除，父指针置空
      50               50
     /  \             /  \
    30   70   删20→  30   70
   / \   / \            / \
  20 40 60 80         40 60 80

情形2：只有一个孩子——孩子"顶上来"接替父位
      50               50
     /  \             /  \
    30   70   删30→  40   70
     \   / \            / \
     40 60 80         60 80

情形3：两个孩子——用"中序后继"的值覆盖自己，再去右子树删掉那个后继
      50               60
     /  \             /  \
    40   70   删50→  40   70
        / \              / \
       60 80           60? 80   ← 实际是把 60 的"值"搬来，节点 60 从原位移除

情形 3 的思路：目标节点两个孩子都在，直接删它会把两棵子树都弄丢。于是用右子树里的最小值（中序后继 in-order successor——中序遍历中排在它后面的那个元素）来”顶班”：先把后继的值抄进目标节点，再递归地到右子树把那个后继节点删掉。后继是右子树的最左节点，它必然没有左孩子，所以对它的删除一定落回情形 1 或 2，不会无限递归。官方课程出于考试批改的一致性，习惯采用对称方案”用左子树的最大值（中序前驱）顶班”，两种方案都产生合法的 BST，本笔记按需求采用中序后继（右子树最小）。

6. 四种遍历。 遍历 = 按某种顺序访问每个节点恰好一次。三种递归遍历只是”访问自己（根）”相对两个孩子的位置不同；层序遍历则按”从上到下、每层从左到右”逐层推进：

           50               前序(根左右): 50 30 20 40 70 60 80
          /  \              中序(左根右): 20 30 40 50 60 70 80  ← 对 BST 恒为升序！
        30    70            后序(左右根): 20 40 30 60 80 70 50
        / \   / \           层序(BFS):   50 30 70 20 40 60 80
      20  40 60 80

递归遍历的代码极短：前序是”先打印自己，再递归左，再递归右”；中序把打印挪到两次递归之间；后序把打印放到最后。层序不用递归，改用队列：根入队；每次出队一个节点就访问它，并把它的左、右孩子依次入队——队列天然保证”先来先访问”，于是同一层从左到右、层与层自上而下。中序遍历对 BST 输出升序序列这一性质，是”为什么要有 BST”的最直观回报。

7. 遍历的应用。 中序：把 BST 里的元素按序输出（如需有序遍历容器）。前序：先处理祖先再深入，适合”找到目标就停”的搜索（官方举例浏览器 DOM 的按 id 找元素）以及树的复制/序列化。后序：先孩子后自己，是释放整棵树的唯一安全顺序——删节点之前它的两个孩子子树必须已经全部释放完毕（官方把释放函数戏称为 forestFire，先烧光两片子树再烧根）；”先删自己再递归孩子”的版本会在 delete 之后解引用已释放节点的 left/right，是未定义行为。

8. 好树、坏树与复杂度三兄弟。 把 1~10000 顺序插入 BST，每个新值都比前一个大、永远走最右分支，树会退化成一条”右斜链”，高度 9999，查找退化为 O(n)——和链表一样慢。若按随机顺序插入，树大致平衡，高度约 O(log n)，查找飞快。官方给出的结论是：最好 O(1)（值恰在根附近）、平均 O(log n)（随机/平衡树）、最坏 O(n)（树退化成链）。严谨的说法可以写成 O(h)，h 为树高；但课程按惯例用 n 表达上表。结论：BST 的性能完全取决于插入顺序带来的树形。

9. 自平衡 BST：把最坏情形也按下去。 现实数据常常天然有序（如字典文件按字母序存放），直接插入必退化成链。自平衡 BST 在插入/删除后自动”整形”——通过旋转（rotation）等操作保证任何节点的左右子树高度差不超过约定限度，使整棵树永远保持 O(log n) 高度，于是查找/插入/删除的最坏情形也是 O(log n)。代价只是插入/删除多了少量平衡维护的开销，仍在 O(log n) 内。常见家族：AVL 树（每个节点记录平衡因子，严格限制高度差 ≤1）与红黑树（给节点染色、用颜色约束维持近似平衡）。标准库的 std::set 与 std::map 正是用红黑树实现的，所以它们的有序性、O(log n) 操作与”键不可重复”全都由此而来；官方指出 Stanford 的 Set/Map 同样由自平衡 BST 驱动。

10. 为什么用 BST 存数据？ 相比有序数组/vector：插入新元素到头部要整体挪窝 O(n)，BST 平衡时只需 O(log n)；数组还要面对扩容 O(n) 与”固定容量浪费/不够”的两难，BST 按需 new 节点。相比链表：链表即使有序也只能线性查找 O(n)，BST 平衡时 O(log n)。代价：每个节点 20 字节（int 4B + 两个指针 16B），约为等量 int 数组的 5 倍；且指针解引用有轻微额外开销（对本课程规模可忽略）。一句话：BST 用空间和一点指针开销，换来”插入/删除/查找三样都对数级”的均衡能力。

代码示例与实现详解

示例 1：完整的 BST 类——递归 insert/search/remove、四种遍历、析构（后序释放）

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

struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int d) : data(d), left(nullptr), right(nullptr) {}
};

// 二叉搜索树（BST）：左子树所有值 < 根 < 右子树所有值；约定键不重复
class BST {
public:
    BST() : root(nullptr) {}
    ~BST() { clear(root); }

    void insert(int v)   { insertRec(root, v); }
    bool search(int v) const { return searchRec(root, v); }
    void remove(int v)   { removeRec(root, v); }

    void preorder()  const { preorderRec(root);  cout << endl; }
    void inorder()   const { inorderRec(root);   cout << endl; }
    void postorder() const { postorderRec(root); cout << endl; }
    void levelorder() const;   // 层序：需要队列，单独实现

private:
    TreeNode *root;
    void insertRec(TreeNode *&node, int v);
    bool searchRec(TreeNode *node, int v) const;
    void removeRec(TreeNode *&node, int v);
    TreeNode *findMin(TreeNode *node) const;  // 右子树最小 = 中序后继
    void preorderRec(TreeNode *node) const;
    void inorderRec(TreeNode *node) const;
    void postorderRec(TreeNode *node) const;
    void clear(TreeNode *&node);
};

void BST::insertRec(TreeNode *&node, int v) {
    if (node == nullptr) { node = new TreeNode(v); return; } // 空位！在此挂上新节点
    if (v < node->data)
        insertRec(node->left, v);    // 比根小 → 去左子树
    else if (v > node->data)
        insertRec(node->right, v);   // 比根大 → 去右子树
    // 相等：约定不存重复值，直接忽略
}

bool BST::searchRec(TreeNode *node, int v) const {
    if (node == nullptr) return false;        // 走到空：没找到
    if (v == node->data) return true;         // 命中
    return (v < node->data) ? searchRec(node->left, v)
                            : searchRec(node->right, v);
}

void BST::removeRec(TreeNode *&node, int v) {
    if (node == nullptr) return;              // 树里没有这个值
    if (v < node->data) { removeRec(node->left, v); return; }
    if (v > node->data) { removeRec(node->right, v); return; }

    // 找到了要删的节点 node：
    if (node->left == nullptr && node->right == nullptr) {
        delete node;                          // 情形1：叶子 → 直接摘除
        node = nullptr;                       // 让父指针（或 root）归零
    } else if (node->left == nullptr) {
        TreeNode *tmp = node->right;          // 情形2a：只有右孩子
        delete node;
        node = tmp;                           // 右孩子顶上来
    } else if (node->right == nullptr) {
        TreeNode *tmp = node->left;           // 情形2b：只有左孩子
        delete node;
        node = tmp;                           // 左孩子顶上来
    } else {
        // 情形3：两个孩子 → 用"中序后继"（右子树最小）的值覆盖本节点，
        //        再去右子树里把那个最小节点删掉（它必然没有左孩子）。
        TreeNode *succ = findMin(node->right);
        node->data = succ->data;
        removeRec(node->right, succ->data);
    }
}

TreeNode *BST::findMin(TreeNode *node) const {
    while (node->left != nullptr) node = node->left; // 一路向左到底
    return node;
}

void BST::preorderRec(TreeNode *node) const {
    if (node == nullptr) return;
    cout << node->data << " ";   // ① 先处理自己（根）
    preorderRec(node->left);     // ② 再左子树
    preorderRec(node->right);    // ③ 最后右子树
}

void BST::inorderRec(TreeNode *node) const {
    if (node == nullptr) return;
    inorderRec(node->left);      // ① 先左子树
    cout << node->data << " ";   // ② 再自己（对 BST 而言即有序输出）
    inorderRec(node->right);     // ③ 最后右子树
}

void BST::postorderRec(TreeNode *node) const {
    if (node == nullptr) return;
    postorderRec(node->left);    // ① 先左子树
    postorderRec(node->right);   // ② 再右子树
    cout << node->data << " ";   // ③ 最后自己
}

void BST::levelorder() const {
    if (root == nullptr) return;
    queue<TreeNode *> q;         // 用 std::queue 按层推进
    q.push(root);
    while (!q.empty()) {
        TreeNode *cur = q.front();
        q.pop();
        cout << cur->data << " ";
        if (cur->left)  q.push(cur->left);   // 下一层的左孩子排队
        if (cur->right) q.push(cur->right);  // 下一层的右孩子排队
    }
    cout << endl;
}

void BST::clear(TreeNode *&node) {
    if (node == nullptr) return;
    clear(node->left);     // 先释放左子树（后序！）
    clear(node->right);    // 再释放右子树
    delete node;           // 最后才删除自己
    node = nullptr;
}

int main() {
    BST t;
    for (int v : {50, 30, 70, 20, 40, 60, 80})
        t.insert(v);

    cout << "preorder : ";  t.preorder();   // 50 30 20 40 70 60 80
    cout << "inorder  : ";  t.inorder();    // 20 30 40 50 60 70 80（有序！）
    cout << "postorder: ";  t.postorder();  // 20 40 30 60 80 70 50
    cout << "level    : ";  t.levelorder(); // 50 30 70 20 40 60 80

    cout << "search(40)? " << t.search(40) << ", search(55)? "
         << t.search(55) << endl;

    t.remove(20);  // 叶子：直接摘除
    cout << "after remove(20) : ";  t.inorder(); // 30 40 50 60 70 80

    t.remove(30);  // 一个孩子（右孩子 40 顶上来）
    cout << "after remove(30) : ";  t.inorder(); // 40 50 60 70 80

    t.remove(50);  // 两个孩子：中序后继 60 顶替
    cout << "after remove(50) : ";  t.inorder(); // 40 60 70 80
    return 0;
}

【代码做什么】 main() 先按 50、30、70、20、40、60、80 的顺序建出一棵完全平衡的小 BST，四种遍历分别打印（结果见注释，中序恰好升序）；search 分别测试命中 40 与未命中 55。随后连续演示删除三情形：remove(20) 是叶子直接摘除；remove(30) 时 30 只剩右孩子 40，由 40 顶上来；remove(50) 时根 50 有两个孩子，右子树最小值 60（中序后继）的值被搬进根节点，60 原节点被递归删除，中序输出 40 60 70 80 验证树仍是合法 BST。程序结束时析构函数 clear(root) 以后序顺序释放全部节点。

【实现机制解说】 递归函数全部接受 TreeNode *&（指针引用）或 const 值拷贝，分工不同：insertRec 与 removeRec 会改写”指针变量里存的地址”（空位挂新节点、删空后把父指针置空、孩子顶班），所以必须传引用，否则改动留在栈帧副本上、树根本没变；searchRec 与遍历只读，传普通指针即可。递归的栈变化值得细想：insertRec 一路下探时，每一层栈帧都持有一个对”父节点某个孩子字段”的引用；最深一层撞上 nullptr，node = new TreeNode(v) 写穿引用链，直接改到树上——返回过程不需要任何额外动作，这是”引用 + 递归”组合的优雅之处。removeRec 的情形 2 用 tmp 先保存唯一孩子，再 delete node、再 node = tmp，顺序不可颠倒（delete 后不能再访问 node 的孩子）；情形 3 不重接指针，只抄值再递归删除后继，逻辑上最省心。clear 的后序顺序是安全释放的前提：先递归释放左右子树，回来时 node 的孩子字段已经不再指向有效内存，随后 delete node 正好收官，最后 node = nullptr 防止调用方持有悬垂地址（与链表 destroy 同理）。levelorder 用 std::queue 而非递归：每次出队即访问，左右孩子入队，队列的 FIFO 属性保证严格逐层从左到右。

示例 2：插入顺序决定树形——按序插入退化成链 vs 乱序插入近似平衡

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

// 极简 BST：只保留插入、求高、销毁三个函数，用于演示"插入顺序决定树形"
struct Node {
    int data;
    Node *left, *right;
    Node(int d) : data(d), left(nullptr), right(nullptr) {}
};

void insert(Node *&root, int v) {
    if (root == nullptr) { root = new Node(v); return; }
    if (v < root->data) insert(root->left, v);
    else                insert(root->right, v);
}

// 树高：约定空树为 -1，单节点树为 0
int height(Node *root) {
    if (root == nullptr) return -1;
    return 1 + max(height(root->left), height(root->right));
}

void destroy(Node *&root) {
    if (root == nullptr) return;
    destroy(root->left);
    destroy(root->right);
    delete root;
    root = nullptr;
}

int main() {
    const int N = 10000;
    vector<int> keys(N);
    for (int i = 0; i < N; ++i) keys[i] = i + 1; // 1..10000 已有序

    // ① 按升序插入 → 每次新值都比根大，一路向右，树退化成"右斜链"
    Node *r1 = nullptr;
    for (int v : keys) insert(r1, v);
    cout << "升序插入 10000 个键的树高 = " << height(r1) << endl; // N-1

    // ② 打乱顺序再插入 → 近似平衡的"灌木状"树
    mt19937 g(20260727);
    shuffle(keys.begin(), keys.end(), g);
    Node *r2 = nullptr;
    for (int v : keys) insert(r2, v);
    cout << "乱序插入 10000 个键的树高 = " << height(r2) << endl; // ~O(log n)

    destroy(r1);
    destroy(r2);
    return 0;
}

【代码做什么】 生成 1 到 10000 的键。第一棵 BST 按升序逐个插入：每个新键都大于当前所有键，递归永远走向右分支，树长成一条 9999 层高的右斜链。第二棵先把同样的键用 mt19937（固定种子 20260727）洗牌，再逐个插入，树形接近随机平衡。程序打印两棵树的高度，直观对比”同样 10000 个键、同样的插入代码”，仅仅插入顺序不同，树高就从 9999 掉到几十层。

【实现机制解说】 这个示例剥掉类的包装，只剩裸函数，凸显树形只由插入顺序决定这一事实。升序情形中每次 insert 都在树的最右端触底，新增节点永远成为最右叶，于是链长 = 键数 − 1，查找/插入退化为与链表相同的 O(n)。乱序情形下新键落在左右两侧的概率大致均等，树向”灌木状”生长，其高度约为对数级别乘一个常数（本机固定种子实测约 27 层，因标准库实现略有差异，但都在几十层的量级，与 9999 判若云泥）。height() 递归返回 1 + max(左高, 右高)，空树返回 −1 使单节点树高度恰为 0，这是后序式递归（先孩子后自己）的又一应用。若对真实系统接入有序数据（如按字母序的词典），升序情形就是必然发生的灾难——这正是下一节自平衡 BST 存在的理由。

复杂度分析

说明。 精确写法是 O(h)、h 为树高：对任意 BST 都成立，但没有传达”h 的上限”。课程采用上表的传统写法：只要树是平衡的（高度 O(log n)），三种核心操作就都是 O(log n)；树退化成链则全部 O(n)。这也是为什么生产环境一律使用自平衡 BST——std::map/std::set 内部的红黑树保证最坏情形也是 O(log n)。

关键要点

• BST 的核心是”左小右大”这条递归规则：对任意节点，左子树全小、右子树全大，查找即”每步排除半棵树”。
• 插入 = 失败的查找：递归下探到空位，靠 TreeNode *& 引用把新节点焊回父指针，返回时无需额外接线。
• 删除三分支：无子直接摘、单子孩子顶班、双子用中序后继（右子树最小，或课程惯例的左子树最大）抄值再递归删后继；删任何节点后 BST 性质必须保持。
• 中序遍历 BST = 升序输出；释放整棵树必须用后序（先孩子后自己），否则 delete 后解引用是未定义行为。
• 树形决定命运：按序插入退化成链（O(n)），随机/自平衡才是 O(log n)——自平衡 BST（AVL、红黑，如 std::map/set）把最坏情形也压到对数。

常见陷阱与注意事项

• 把”整棵子树都小”误写成”只跟直接孩子比”：插入 40 时只检查根 50 的孩子 30 会漏掉 BST 性质。规避：始终递归比较并整棵下探。
• 插入/删除函数忘了传引用：insertRec(TreeNode *node, ...) 内部改的是拷贝，树毫无变化。规避：凡可能改写指针变量的函数一律 TreeNode *&。
• 删除两子情形只删值不删后继：把后继值抄进来却不递归删除原后继节点，会留下重复值。规避：抄值后必须 removeRec(node->right, succ->data)。
• 删除单子情形顺序颠倒：delete node; node = node->left; 在 delete 后解引用。规避：先用 tmp 保存唯一孩子，再 delete，再顶班。
• 树退化成链还不自知：把有序数据直接灌进普通 BST。规避：理解最坏 O(n) 的来源；需要稳定性能就用自平衡结构（std::map/set）。
• 遍历顺序混淆：前=根左右、中=左根右、后=左右根。规避：背口诀”看根的位置”，并用”中序必升序”自检 BST 遍历实现。
• 前序/中序释放树：delete node; 再递归删孩子 是未定义行为。规避：释放只能用后序（forestFire 模式）。
• 层序用递归实现：递归天然是深度优先，实现不了”逐层”语义。规避：层序用 std::queue 迭代；递归留给前/中/后序。
• 对空树解引用：findMin、height 等函数若假定 root 非空，传入空树会段错误。规避：约定并注明前置条件，或先判空。
• 节点内存泄漏：只 new 不 delete，或析构用错遍历顺序。规避：析构统一后序 clear，空树与单节点都测一遍。

思考题（带答案）

问题 1：为什么 insertRec 必须传 TreeNode *&，而 searchRec 传普通 TreeNode * 即可？如果 insertRec 改成传值，会发生什么？ 答案：insertRec 需要在找到空位时把新节点挂到”父节点的孩子字段（或 root）”上——这是改写指针变量的值，必须用引用才能写穿到树里；searchRec 只沿着指针读值、从不改写任何指针，传值（一份拷贝）足够，还能防止误改。若 insertRec 传值，递归最深一层 node = new TreeNode(v) 只改了栈帧里的拷贝，返回后新节点失去所有引用（泄漏），而树纹丝不动——查找时永远找不到新插入的值。

问题 2：删除”有两个孩子”的节点时，为什么方案是”抄后继的值 + 递归删后继”，而不是把后继节点整个搬上来重接指针？为什么后继一定没有左孩子？ 答案：直接重接指针需要同时处理目标节点与后继节点的左右子树共四个连接，极易出错；抄值方案不动树的骨架，只改一个 int 再递归删一个”结构简单”的节点，正确性容易论证。后继 = 右子树的最左节点，按 BST 性质”最左”意味着它没有左孩子（若有左孩子，那个更小的节点才是后继），所以对它的递归删除必然落入情形 1（叶子）或情形 2（只有右孩子），递归必然终止。

问题 3：给定一棵 BST 的中序序列 [20, 30, 40, 50, 60, 70, 80]，能否唯一还原这棵树？为什么课程说”中序对 BST 恒为升序”是重要性质？ 答案：不能唯一还原——同一中序序列可对应多棵不同形状的 BST（例如以 50 为根的平衡树和以 20 为根的右斜链，中序都是升序）。仅当附加前序或后序（或树的形状信息）时才能唯一重建。中序恒升序的价值在于：它是 BST 正确性的免费自检（遍历结果不是升序，树一定被破坏了），也让”有序遍历容器”成为 BST 的天然卖点。