二叉搜索树通过类和指针实现，包含插入、删除、查找和中序遍历操作，其中插入和查找基于值的比较递归进行，删除需处理三种情况，中序遍历验证有序性，整体平均时间复杂度为O(log n)，但性能依赖树的平衡性。
二叉搜索树（Binary Search Tree，简称 BST）是一种重要的数据结构，它能高效地实现插入、删除和查找操作，平均时间复杂度为 O(log n)。在 C++ 中，我们可以用类和指针来构建一个完整的 BST。下面详细介绍其实现方式。
BST 的基本结构
每个节点包含一个值、指向左子树和右子树的指针。我们定义一个 TreeNode 结构体来表示节点：
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};
接着定义一个 BST 类，管理整棵树：
立即学习“C++免费学习笔记（深入）”；
class BST {
private:
TreeNode* root;
// 辅助函数
TreeNode* insertNode(TreeNode* node, int val);
TreeNode* deleteNode(TreeNode* node, int val);
TreeNode* findMin(TreeNode* node);
TreeNode* searchNode(TreeNode* node, int val);
public:
BST() : root(nullptr) {}
void insert(int val);
void remove(int val);
bool search(int val);
void inorder(); // 中序遍历用于验证 BST 性质
};
插入操作
插入时从根开始比较，小于当前节点值则进入左子树，大于则进入右子树，直到找到空位置。
递归实现：
TreeNode* BST::insertNode(TreeNode* node, int val) {
if (!node) {
return new TreeNode(val);
}
if (val < node->val) {
node->left = insertNode(node->left, val);
} else if (val > node->val) {
node->right = insertNode(node->right, val);
}
// 相等时不插入重复值
return node;
}
void BST::insert(int val) {
root = insertNode(root, val);
}
查找操作
查找过程类似插入，根据大小关系决定向左或向右查找。
TreeNode* BST::searchNode(TreeNode* node, int val) {
if (!node || node->val == val) {
return node;
}
if (val < node->val) {
return searchNode(node->left, val);
}
return searchNode(node->right, val);
}
bool BST::search(int val) {
return searchNode(root, val) != nullptr;
}
删除操作（关键难点）
删除节点有三种情况：
- 叶子节点：直接删除。
- 只有一个子节点：让父节点指向其子节点。
- 有两个子节点：用右子树中的最小值（中序后继）替换该节点，然后删除那个最小节点。
TreeNode* BST::findMin(TreeNode* node) {
while (node && node->left) {
node = node->left;
}
return node;
}
TreeNode BST::deleteNode(TreeNode node, int val) {
if (!node) return nullptr;
if (val < node->val) {
node->left = deleteNode(node->left, val);
} else if (val > node->val) {
node->right = deleteNode(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* successor = findMin(node->right);
node->val = successor->val;
node->right = deleteNode(node->right, successor->val);
}
return node;}
void BST::remove(int val) {
root = deleteNode(root, val);
}
中序遍历验证结构
中序遍历 BST 应输出有序序列，可用于调试。
void inorderHelper(TreeNode* node) {
if (node) {
inorderHelper(node->left);
std::cout << node->val << " ";
inorderHelper(node->right);
}
}
void BST::inorder() {
inorderHelper(root);
std::cout << std::endl;
}
基本上就这些。这个实现涵盖了 BST 的核心操作，适合学习和实际应用。注意内存管理，在更高级的版本中可使用智能指针避免泄漏。BST 的性能依赖于树的平衡性，极端情况下会退化为链表，后续可学习 AVL 树或红黑树来解决这个问题。
