个人主页: 起名字真南的CSDN博客

个人专栏:

• 【数据结构初阶】 📘 基础数据结构
• 【C语言】 💻 C语言编程技巧
• 【C++】 🚀 进阶C++
• 【OJ题解】 📝 题解精讲

---

📌 前言

二叉搜索树（Binary Search Tree, BST）是数据结构领域的基础知识，也是算法学习和技术面试中经常出现的主题。本文将通过 C++ 实现二叉搜索树，逐步讲解其插入、查找、删除等核心操作，并分析其设计细节与应用场景。

---

📌 1 二叉搜索树的概念

二叉搜索树是一种特殊的二叉树，其特点是：

• 每个节点的左子树中的所有节点值小于该节点的值。
• 每个节点的右子树中的所有节点值大于该节点的值。
• 左右子树也都是二叉搜索树。

这种结构使得查找、插入和删除操作可以高效完成，平均时间复杂度为 (O(\log n))。

---

📌 2 二叉搜索树的基本操作

我们通过以下功能模块来实现一个二叉搜索树：

• 插入（Insert）：将新节点插入树中。
• 查找（Find）：查找特定键是否存在。
• 删除（Erase）：删除某个键对应的节点。
• 中序遍历（InOrder）：按顺序输出节点值。

---

📌 3 二叉搜索树的代码实现（k命名空间）

✨ 3.1. 节点结构

首先定义节点的结构 BSTNode：

template<class K>
struct BSTNode {K _key;  // 节点值BSTNode<K>* _left;  // 左子节点BSTNode<K>* _right; // 右子节点// 构造函数BSTNode(const K& key): _key(key), _left(nullptr), _right(nullptr) {}
};

• 每个节点存储一个键 _key。
• 使用 _left 和 _right 指针链接到左右子树。

✨ 3.2 插入操作

插入的逻辑是从根节点开始，根据键的大小找到空位置插入新节点。

bool Insert(const K& key) {if (_root == nullptr) {  // 如果根节点为空_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_key < key) {  // 移动到右子树parent = cur;cur = cur->_right;} else if (cur->_key > key) {  // 移动到左子树parent = cur;cur = cur->_left;} else {  // 已存在相同的键return false;}}cur = new Node(key);  // 创建新节点if (parent->_key < key) parent->_right = cur;  // 插入右子树else parent->_left = cur;  // 插入左子树return true;
}

关键点：

• 从根节点递归比较键值。
• 处理空树和插入到左右子树的情况。
• 如果键已存在，不插入并返回 false。

✨ 3.3 查找操作

查找过程与插入类似，按键值大小遍历树：

bool find(const K& key) {Node* cur = _root;while (cur) {if (key > cur->_key) cur = cur->_right;  // 右子树查找else if (key < cur->_key) cur = cur->_left;  // 左子树查找else return true;  // 找到目标值}return false;  // 未找到
}

✨ 3.4 删除操作

删除节点需要考虑三种情况：

1. 目标节点无子节点：直接删除。
2. 目标节点有一个子节点：用子节点替代。
3. 目标节点有两个子节点：用右子树中最小的节点替换。

实现代码如下：

bool erase(const K& key) {Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;} else if (cur->_key > key) {parent = cur;cur = cur->_left;} else {  // 找到目标节点if (cur->_left == nullptr) {  // 左子树为空if (_root == cur) _root = cur->_right;else if (parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;} else if (cur->_right == nullptr) {  // 右子树为空if (_root == cur) _root = cur->_left;else if (parent->_left == cur) parent->_left = cur->_left;else parent->_right = cur->_left;} else {  // 左右子树均不为空Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left) {  // 找右子树的最左节点replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;  // 替换目标节点的值if (replaceParent->_left == replace) replaceParent->_left = replace->_right;else replaceParent->_right = replace->_right;delete replace;}return true;}}return false;  // 未找到目标值
}

关键点：

• 找到目标节点后，分类讨论处理不同情况。
• 当左右子树均存在时，右子树的最左节点（中序后继）是最佳替代节点。

✨ 3.5 中序遍历

中序遍历输出节点值的顺序为从小到大：

void InOrder() {_InOrder(_root);cout << endl;
}void _InOrder(Node* root) {if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << " ";  // 访问节点_InOrder(root->_right);
}

---

📌 4 代码的实际运行效果

插入和删除节点的效果如下：

BSTree<int> tree;
tree.Insert(10);
tree.Insert(5);
tree.Insert(15);tree.InOrder();  // 输出: 5 10 15tree.erase(10);
tree.InOrder();  // 输出: 5 15

---

📌 5 二叉搜索树的优化与应用

1. 优化方案：

   • 使用自平衡树（如 AVL 树、红黑树）解决普通二叉搜索树可能退化为链表的问题。
   • 在实现中加入异常处理，提升代码鲁棒性。

2. 实际应用：

   • 数据库索引（如 B 树）。
   • 实现 C++ 标准库中的 std::map 和 std::set。
   • 动态维护有序数据。

---

📌 6 总结

本文通过代码详细实现了二叉搜索树的插入、查找、删除和遍历等操作，并逐步分析了其设计细节。二叉搜索树是一种高效且基础的数据结构，理解其实现与应用可以为算法学习和编程实践打下坚实基础。

扩展阅读：

• 《算法导论》—— 二叉搜索树章节。
• 在线可视化工具：BST 动态演示（可以帮助理解树的结构和操作过程）。

---