二叉搜索树通过类与指针实现，支持插入、查找、删除操作；插入与查找利用递归比较节点值，删除需处理三种情况，平均时间复杂度为O(log n)，最坏O(n)。
二叉搜索树（Binary Search Tree，简称 BST）是一种重要的数据结构，它具有左子树节点值小于根节点、右子树节点值大于根节点的特性。C++ 中可以通过类和指针来实现 BST，支持插入、查找、删除等基本操作。
BST 的基本结构定义
每个节点包含一个值、指向左子树和右子树的指针。使用 C++ 类封装整个树结构。
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};
定义一个管理树操作的类：
立即学习“C++免费学习笔记（深入）”；
class BST {
private:
TreeNode* root;
// 辅助函数
TreeNode* insertNode(TreeNode* node, int val);
TreeNode* searchNode(TreeNode* node, int val);
TreeNode* deleteNode(TreeNode* node, int val);
TreeNode* findMin(TreeNode* node);
public:
BST() : root(nullptr) {}
void insert(int val);
bool search(int val);
void remove(int val);
};
插入操作
从根开始比较，小于当前节点进入左子树，大于则进入右子树，直到找到空位置插入新节点。
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);
}
查找操作
根据 BST 性质递归查找目标值。
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 实现的关键是利用递归保持结构有序，插入、查找、删除平均时间复杂度为 O(log n)，最坏情况下退化为 O(n)。可以在此基础上扩展中序遍历、求高度、验证是否为 BST 等功能。不复杂但容易忽略边界条件，比如重复值处理（当前实现忽略重复插入）和内存释放。
