二叉搜索树（BST）是一种特殊的二叉树结构，核心规则是对于任意节点，其左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值，这个特性让它在数据检索、排序等场景中有很高的实用价值。要实现完整的二叉搜索树，需要先从节点结构入手，再逐步实现插入、查找、删除三个核心操作。
二叉搜索树节点结构设计
二叉搜索树的每个节点需要存储自身的值，同时关联左子节点和右子节点，在C++中可以用结构体来定义节点，具体代码如下：
#include <iostream>
using namespace std;
// 二叉搜索树节点结构体
struct BSTNode {
int val; // 节点存储的值
BSTNode* left; // 左子节点指针
BSTNode* right; // 右子节点指针
// 构造函数，初始化节点值和左右子节点
BSTNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
二叉搜索树插入操作实现
插入操作的思路是从根节点开始比较，待插入值小于当前节点值就往左子树走，大于就往右子树走，直到找到空位置插入新节点，递归实现代码如下：
// 递归插入节点
BSTNode* insert(BSTNode* root, int val) {
// 如果根节点为空，直接创建新节点作为根
if (root == nullptr) {
return new BSTNode(val);
}
// 待插入值小于当前节点值，插入左子树
if (val < root->val) {
root->left = insert(root->left, val);
}
// 待插入值大于当前节点值，插入右子树
else if (val > root->val) {
root->right = insert(root->right, val);
}
// 相等的情况可根据需求处理，这里默认不插入重复值
return root;
}
二叉搜索树查找操作实现
查找操作和插入的逻辑类似，从根节点开始比较，根据值的大小关系向左或向右遍历，直到找到目标节点或者遍历到空节点，递归实现代码如下：
// 递归查找节点
BSTNode* search(BSTNode* root, int val) {
// 根节点为空或者找到目标值，直接返回
if (root == nullptr || root->val == val) {
return root;
}
// 目标值小于当前节点值，去左子树查找
if (val < root->val) {
return search(root->left, val);
}
// 目标值大于当前节点值，去右子树查找
else {
return search(root->right, val);
}
}
二叉搜索树删除操作实现
删除操作是三个操作中最复杂的部分，需要分三种情况处理：要删除的节点是叶子节点、只有一个子节点、有两个子节点。其中有两个子节点的情况需要找到右子树的最小节点来替换当前节点的值，再删除那个最小节点。实现代码如下：
// 找到以root为根的子树中的最小节点
BSTNode* findMin(BSTNode* root) {
while (root->left != nullptr) {
root = root->left;
}
return root;
}
// 递归删除节点
BSTNode* remove(BSTNode* root, int val) {
if (root == nullptr) {
return nullptr;
}
// 目标值小于当前节点值，去左子树删除
if (val < root->val) {
root->left = remove(root->left, val);
}
// 目标值大于当前节点值，去右子树删除
else if (val > root->val) {
root->right = remove(root->right, val);
}
// 找到要删除的节点
else {
// 情况1：节点是叶子节点或者只有一个子节点
if (root->left == nullptr) {
BSTNode* temp = root->right;
delete root;
return temp;
}
else if (root->right == nullptr) {
BSTNode* temp = root->left;
delete root;
return temp;
}
// 情况2：节点有两个子节点
else {
// 找到右子树的最小节点
BSTNode* minNode = findMin(root->right);
// 用最小节点的值替换当前节点的值
root->val = minNode->val;
// 删除右子树中的最小节点
root->right = remove(root->right, minNode->val);
}
}
return root;
}
完整测试示例
下面是一个完整的测试代码，演示二叉搜索树的插入、查找、删除操作的运行效果：
// 中序遍历二叉搜索树，输出有序结果
void inorderTraversal(BSTNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
BSTNode* root = nullptr;
// 插入节点
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
cout << "插入后中序遍历结果：";
inorderTraversal(root);
cout << endl;
// 查找节点
BSTNode* searchResult = search(root, 40);
if (searchResult != nullptr) {
cout << "找到值为40的节点" << endl;
} else {
cout << "未找到值为40的节点" << endl;
}
// 删除节点
root = remove(root, 70);
cout << "删除70后中序遍历结果：";
inorderTraversal(root);
cout << endl;
return 0;
}
注意事项
在实际使用二叉搜索树时，需要注意重复值的处理，上述代码默认不插入重复值，如果需要支持重复值可以调整插入逻辑，将重复值放到左子树或者右子树。另外，如果插入的数据是有序的，二叉搜索树会退化成链表，此时可以引入平衡二叉搜索树（如AVL树、红黑树）来优化性能。上述代码中的节点没有做内存释放处理，实际项目中如果长期运行需要添加对应的内存回收逻辑，避免内存泄漏。