《大话数据结构》第8章精读：二叉排序树（BST）完整 C++ 实现（插入、查找、删除、遍历）
1. 二叉排序树的定义
进入《大话数据结构》第8章「查找」，本章第一个重点就是二叉排序树（Binary Sort Tree / Binary Search Tree，简称 BST）。它把“排序”和“查找”结合在一起，是后续平衡二叉树、B 树等内容的基础。
二叉排序树可以是一棵空树；如果不是空树，它必须满足以下性质：
- 若左子树不为空，则左子树上所有节点的值均小于根节点的值；
- 若右子树不为空，则右子树上所有节点的值均大于根节点的值；
- 左右子树本身也都是二叉排序树。
关键结论：对二叉排序树进行中序遍历，会得到一个递增的有序序列。这也是它能够把“查找”和“排序”结合起来的重要原因。
2. 节点定义与基本结构
下面使用 C++ 定义 BST 节点。每个节点保存一个整型关键字，以及指向左右孩子的两个指针。
#include <iostream> #include <queue> using namespace std; struct BSTNode { int data; // 节点关键字 BSTNode *lchild; // 左孩子指针 BSTNode *rchild; // 右孩子指针 BSTNode(int d) : data(d), lchild(nullptr), rchild(nullptr) {} };说明：
data：当前节点保存的值。lchild：左孩子指针，指向一棵更小的二叉排序树。rchild：右孩子指针，指向一棵更大的二叉排序树。- 构造函数使用初始化列表一次性完成成员初始化，避免指针成为未初始化的野指针。
3. BSTree 类与递归插入
插入操作按“比较、递归、挂接”的思路进行：如果当前节点为空，就新建节点；如果插入值小于当前节点，则递归插入左子树；如果大于当前节点，则递归插入右子树；如果相等，通常不重复插入，也可以根据业务需求进行更新。
class BSTree { private: BSTNode* root; // 递归插入 BSTNode* insert(BSTNode* node, int key) { if (node == nullptr) { return new BSTNode(key); } if (key < node->data) { node->lchild = insert(node->lchild, key); } else if (key > node->data) { node->rchild = insert(node->rchild, key); } // 相等则不插入，或根据实际需求更新节点 return node; }插入元素{50, 30, 70, 20, 40, 60, 80}后，会形成如下结构：
50 / \ 30 70 / \ / \ 20 40 60 80可以看到，根节点 50 的左子树全部小于 50，右子树全部大于 50，每一棵子树也满足同样的性质。
4. 递归查找
查找操作与二分查找思想类似：每次比较当前节点与目标值，如果相等则查找成功；如果目标值小于当前节点，则进入左子树继续查找；否则进入右子树继续查找。走到空指针仍未找到，说明树中不存在该值。
// 递归查找 BSTNode* search(BSTNode* node, int key) { if (node == nullptr || node->data == key) { return node; } if (key < node->data) { return search(node->lchild, key); } else { return search(node->rchild, key); } }查找路径总是沿着“小于走左，大于走右”的方向向下延伸。树的形态越接近完全二叉树，查找效率越接近O(log n)。
5. 查找最小节点
在一棵二叉排序树中，沿左孩子不断前进，最后一个非空节点就是当前子树中的最小节点。这个操作在删除有两个孩子的节点时会反复用到。
// 找到以 node 为根的子树中的最小节点 BSTNode* findMin(BSTNode* node) { while (node && node->lchild) { node = node->lchild; } return node; }也可以使用递归方式实现，但这里使用循环更直观：只要左孩子还存在，就继续向左走。
6. 递归删除
删除是 BST 中最容易写错的操作，核心在于处理目标节点的三种情况：叶子节点、只有一个孩子的节点、有两个孩子的节点。
// 递归删除 BSTNode* remove(BSTNode* node, int key) { if (node == nullptr) return nullptr; if (key < node->data) { node->lchild = remove(node->lchild, key); } else if (key > node->data) { node->rchild = remove(node->rchild, key); } else { // 找到了要删除的节点 if (node->lchild == nullptr) { // 只有右孩子或没有孩子 BSTNode* temp = node->rchild; delete node; return temp; } else if (node->rchild == nullptr) { // 只有左孩子 BSTNode* temp = node->lchild; delete node; return temp; } else { // 有两个孩子：用右子树最小节点替代 BSTNode* temp = findMin(node->rchild); node->data = temp->data; node->rchild = remove(node->rchild, temp->data); } } return node; }三种情况可以总结为：
- 叶子节点：直接删除。
- 只有一个孩子：用孩子顶替自己的位置。
- 有两个孩子：找到右子树中最小节点，或左子树中最大节点，用它的值覆盖当前节点，再递归删除那个替身节点。
建议：删除有两个孩子的节点时，一定要在草稿纸上画图模拟。比如删除根节点 50，可以取右子树的最小节点 60 替换 50，再把原来的 60 删除。
7. 中序遍历与销毁
中序遍历用于验证二叉排序树的有序性；析构函数中需要递归释放整棵树，避免内存泄漏。
// 中序遍历：验证有序性 void inOrder(BSTNode* node) { if (node) { inOrder(node->lchild); cout << node->data << " "; inOrder(node->rchild); } } // 销毁整棵树 void destroy(BSTNode* node) { if (node) { destroy(node->lchild); destroy(node->rchild); delete node; } }后序遍历的思想也可以用于统计节点数量或计算树的高度。它们都属于“先处理子树，再处理根节点”的典型递归结构。
8. 对外接口
类内部用递归实现具体逻辑，对外提供简洁的公共接口。调用者不需要关心根指针和递归细节。
public: BSTree() : root(nullptr) {} ~BSTree() { destroy(root); } void insert(int key) { root = insert(root, key); } bool search(int key) { return search(root, key) != nullptr; } void remove(int key) { root = remove(root, key); } void inOrderTraverse() { cout << "中序遍历："; inOrder(root); cout << endl; } };这样设计的好处是：二叉排序树的递归逻辑集中在私有函数中，公共接口只负责传入用户数据并更新根节点，代码结构清晰，也便于后续扩展为 AVL 树等平衡结构。
9. 核心操作复杂度分析
| 操作 | 平均时间复杂度 | 最坏时间复杂度 | 说明 |
|---|---|---|---|
| 查找 | O(log n) | O(n) | 最坏情况下退化为链表 |
| 插入 | O(log n) | O(n) | 插入路径与查找路径一致 |
| 删除 | O(log n) | O(n) | 删除有两个孩子的节点时较复杂 |
| 中序遍历 | O(n) | O(n) | 一定能得到递增有序序列 |
最坏情况通常发生在输入序列本身有序时。例如依次插入{10, 20, 30, 40, 50}，二叉排序树会退化成一条链：
10 \ 20 \ 30 \ 40 \ 50此时查找、插入、删除的时间复杂度都会退化为 O(n)，性能与普通链表相同。这也是后续必须学习 AVL 树、红黑树等平衡二叉树的根本原因。
10. 完整测试代码
下面给出完整的可运行程序，覆盖插入、查找、删除和中序遍历。
#include <iostream> #include <queue> using namespace std; struct BSTNode { int data; BSTNode *lchild, *rchild; BSTNode(int d) : data(d), lchild(nullptr), rchild(nullptr) {} }; class BSTree { private: BSTNode* root; BSTNode* insert(BSTNode* node, int key) { if (node == nullptr) { return new BSTNode(key); } if (key < node->data) { node->lchild = insert(node->lchild, key); } else if (key > node->data) { node->rchild = insert(node->rchild, key); } return node; } BSTNode* search(BSTNode* node, int key) { if (node == nullptr || node->data == key) { return node; } if (key < node->data) { return search(node->lchild, key); } else { return search(node->rchild, key); } } BSTNode* findMin(BSTNode* node) { while (node && node->lchild) { node = node->lchild; } return node; } BSTNode* remove(BSTNode* node, int key) { if (node == nullptr) return nullptr; if (key < node->data) { node->lchild = remove(node->lchild, key); } else if (key > node->data) { node->rchild = remove(node->rchild, key); } else { if (node->lchild == nullptr) { BSTNode* temp = node->rchild; delete node; return temp; } else if (node->rchild == nullptr) { BSTNode* temp = node->lchild; delete node; return temp; } else { BSTNode* temp = findMin(node->rchild); node->data = temp->data; node->rchild = remove(node->rchild, temp->data); } } return node; } void inOrder(BSTNode* node) { if (node) { inOrder(node->lchild); cout << node->data << " "; inOrder(node->rchild); } } void destroy(BSTNode* node) { if (node) { destroy(node->lchild); destroy(node->rchild); delete node; } } public: BSTree() : root(nullptr) {} ~BSTree() { destroy(root); } void insert(int key) { root = insert(root, key); } bool search(int key) { return search(root, key) != nullptr; } void remove(int key) { root = remove(root, key); } void inOrderTraverse() { cout << "中序遍历："; inOrder(root); cout << endl; } }; int main() { BSTree tree; // 插入 int arr[] = {50, 30, 70, 20, 40, 60, 80}; for (int x : arr) { tree.insert(x); } tree.inOrderTraverse(); // 应输出：20 30 40 50 60 70 80 // 查找 cout << "查找 40：" << (tree.search(40) ? "找到" : "未找到") << endl; cout << "查找 90：" << (tree.search(90) ? "找到" : "未找到") << endl; // 删除 tree.remove(30); // 删除有两个孩子的节点 tree.inOrderTraverse(); // 20 40 50 60 70 80 tree.remove(50); // 删除根节点 tree.inOrderTraverse(); return 0; }程序运行结果如下：
中序遍历：20 30 40 50 60 70 80 查找 40：找到 查找 90：未找到 中序遍历：20 40 50 60 70 80 中序遍历：20 40 60 70 80删除节点 30 后，节点 40 顶替原 30 的位置；删除根节点 50 后，右子树中的最小节点 60 顶替根节点位置。最终中序遍历结果仍然保持递增有序。
11. 删除操作的三种情况图解
删除操作可以拆成三种典型情况，建议对照代码逐一画图。
11.1 删除叶子节点
例如删除节点 20：
删除前： 删除后： 30 30 / \ / 20 40 40叶子节点没有孩子，直接释放该节点，并让父节点的对应指针置空。
11.2 删除只有一个孩子的节点
例如删除节点 30，它只有一个右孩子 40：
删除前： 删除后： 30 40 \ 40此时只需用它的孩子顶替它自己的位置。
11.3 删除有两个孩子的节点
例如删除根节点 50：
删除前： 删除后： 50 60 / \ / \ 30 70 30 70 / \ / \ / \ \ 20 40 60 80 20 40 80找到右子树中的最小节点 60，用 60 覆盖 50，然后递归删除原 60。这样既能保持二叉排序树的有序性，也避免直接调整大量节点的指针。
12. 总结与思考
二叉排序树把“查找”和“动态有序”很好地结合在一起，平均性能优秀，是实现动态查找表的经典结构。但它存在退化风险，因此在工程实践中很少直接使用朴素 BST，而是使用它的平衡版本，如 AVL 树、红黑树、B 树等。
结合《C++ Primer Plus》的思考：
- 递归实现插入、查找和删除，充分练习了书中关于递归、指针和函数返回值传递的内容。
- 删除时对节点三种情况的处理，体现了细致的内存管理和指针维护能力。
- 通过图例模拟树的形态变化，有助于理解指针的挂接关系，而不是只背代码。
下一篇将按顺序继续第8章内容：平衡二叉树（AVL 树）的旋转与实现，重点解决朴素 BST 在有序插入时退化为链表的问题。