答案：实现二叉搜索树需定义节点结构和BST类，包含插入、查找、删除及中序遍历方法。1. 节点含值、左右子指针；2. BST类通过递归实现插入、查找、删除操作；3. 删除时处理三种情况：无子、一子、两子（用右子树最小值替换）；4. 中序遍历验证有序性；5. 示例演示插入、查找、删除流程，体现BST性质。
实现一个二叉搜索树（Binary Search Tree, BST）在 C++ 中是一个常见的数据结构练习。它支持高效的查找、插入和删除操作，前提是树保持相对平衡。下面介绍如何从零开始实现一个基础的二叉搜索树。
1. 定义二叉搜索树的节点结构
每个节点包含一个值、指向左子树的指针和指向右子树的指针。
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
<pre class='brush:php;toolbar:false;'>// 构造函数
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};
2. 定义二叉搜索树类
创建一个 BST 类，管理根节点，并提供插入、查找、删除等方法。
立即学习“C++免费学习笔记（深入）”；
class BST {
private:
TreeNode* root;
<pre class='brush:php;toolbar:false;'>// 辅助函数：递归插入
TreeNode* insert(TreeNode* node, int val) {
if (!node) {
return new TreeNode(val);
}
if (val < node->val) {
node->left = insert(node->left, val);
} else if (val > node->val) {
node->right = insert(node->right, val);
}
// 相等时不插入重复值
return node;
}
// 辅助函数：递归查找
bool search(TreeNode* node, int val) {
if (!node) return false;
if (val == node->val) return true;
if (val < node->val) {
return search(node->left, val);
} else {
return search(node->right, val);
}
}
// 辅助函数：查找最小值节点（用于删除）
TreeNode* findMin(TreeNode* node) {
while (node && node->left) {
node = node->left;
}
return node;
}
// 辅助函数：递归删除
TreeNode* remove(TreeNode* node, int val) {
if (!node) return nullptr;
if (val < node->val) {
node->left = remove(node->left, val);
} else if (val > node->val) {
node->right = remove(node->right, val);
} else {
// 找到要删除的节点
if (!node->left) {
TreeNode* temp = node->right;
delete node;
return temp;
} else if (!node->right) {
TreeNode* temp = node->left;
delete node;
return temp;
}
// 有两个子节点：用右子树的最小值替换
TreeNode* minRight = findMin(node->right);
node->val = minRight->val;
node->right = remove(node->right, minRight->val);
}
return node;
}
// 中序遍历（用于测试）
void inorder(TreeNode* node) {
if (node) {
inorder(node->left);
std::cout << node->val << " ";
inorder(node->right);
}
}public: BST() : root(nullptr) {}
void insert(int val) {
root = insert(root, val);
}
bool search(int val) {
return search(root, val);
}
void remove(int val) {
root = remove(root, val);
}
void inorder() {
inorder(root);
std::cout << std::endl;
}};
3. 使用示例
创建一个 BST 对象并进行基本操作。
#include <iostream>
using namespace std;
<p>int main() {
BST tree;
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);</p><pre class='brush:php;toolbar:false;'>cout << "中序遍历: ";
tree.inorder(); // 输出：20 30 40 50 60 70 80
cout << "查找 40: " << (tree.search(40) ? "存在" : "不存在") << endl;
tree.remove(30);
cout << "删除 30 后中序遍历: ";
tree.inorder(); // 20 40 50 60 70 80
return 0;}
4. 关键点说明
二叉搜索树的性质：对于任意节点，左子树所有值小于该节点，右子树所有值大于该节点。
- 插入和查找时间复杂度平均为 O(log n)，最坏情况（退化为链表）为 O(n)
- 删除操作需处理三种情况：无子节点、有一个子节点、有两个子节点
- 使用递归实现更直观，也可用迭代提高效率并避免栈溢出
- 实际应用中可扩展支持重复值、自平衡（如 AVL 或红黑树）
基本上就这些。掌握这个基础实现后，可以进一步学习平衡二叉搜索树来提升性能稳定性。
