《大话数据结构》第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 在有序插入时退化为链表的问题。