二叉排序树（BST）

💡 打个比方

想象一本会自己归位的电话簿：新名字进来时，比大小——比当前页码小就翻到左页、大就翻到右页，一直翻到空位坐下。久而久之，整本簿子自动变得"左页全比右页小"。想找某人？每次比一下当前页，直接砍掉一半的页——这正是 GESP5 里二分查找的思想，只不过它长在了一棵树上。

这棵"左小右大"的树叫二叉排序树（Binary Search Tree，BST）。它天生自带三件超能力：查找快（砍半）、插入有序（自动归位）、中序遍历就是升序名单。

🖼️ 大图看明白

把 5、3、8、1、4、7、9 按"比大小走左/右"的规则插入，得到这棵 BST。右边演示查找 7 的全过程——只比了 2 次！

💻 完整代码

插入（递归归位）+ 中序遍历（输出升序）+ 查找（数比较次数），一个文件三件超能力。

// BST：插入 / 中序输出 / 查找（计比较次数）
#include <bits/stdc++.h>
using namespace std;

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

void insert(Node *&p, int x) {      // 注意：参数是"引用的引用"
    if (!p) { p = new Node(x); return; }
    if (x < p->val)      insert(p->l, x);   // 小走左
    else if (x > p->val) insert(p->r, x);   // 大走右；相等忽略
}

int search(Node *p, int x) {          // 返回比较次数（找到或走到头）
    int cnt = 0;
    while (p) {
        cnt++;
        if (x == p->val) return cnt;
        p = (x < p->val) ? p->l : p->r;
    }
    return cnt;
}

void inorder(Node *p) {               // BST 中序 = 升序
    if (!p) return;
    inorder(p->l);
    cout << p->val << " ";
    inorder(p->r);
}

int main() {
    Node *root = nullptr;
    int nums[] = {5, 3, 8, 1, 4, 7, 9};
    for (int x : nums) insert(root, x);

    cout << "inorder: ";
    inorder(root);   // 输出：1 3 4 5 7 8 9
    cout << endl;
    cout << "search 7: " << search(root, 7) << " 次比较" << endl;  // 3
    cout << "search 2: " << search(root, 2) << " 次比较" << endl;  // 3（未找到）
    return 0;
}

✋ 你来试试