二叉搜索树通过类封装实现插入、查找、删除操作，节点结构含值与左右指针，插入按大小规则递归构建，查找依二分逻辑遍历，删除时无子节点直接删、单子节点替换、双子节点找中序后继替代并递归删，示例验证功能正确性。
二叉搜索树（Binary Search Tree, BST）是一种重要的数据结构，它能高效地实现查找、插入和删除操作。在C++中，可以通过类和指针来构建一个完整的BST。下面是一个简洁、实用的C++ BST实现方法。
定义BST节点结构
每个节点包含一个值、指向左子树和右子树的指针。
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};
BST类的基本设计
我们创建一个BST类，封装插入、查找、删除等核心操作。
class BST {
private:
TreeNode* root;
TreeNode* 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;
}
bool searchNode(TreeNode* node, int val) {
if (!node) return false;
if (node->val == val) return true;
if (val < node->val) {
return searchNode(node->left, val);
} else {
return searchNode(node->right, val);
}
}
TreeNode* 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;
}
TreeNode* findMin(TreeNode* node) {
while (node && node->left) {
node = node->left;
}
return node;
}public:
BST() : root(nullptr) {}
void insert(int val) {
root = insertNode(root, val);
}
bool search(int val) {
return searchNode(root, val);
}
void remove(int val) {
root = deleteNode(root, val);
}};
}
// 有两个子节点：找右子树的最小值（中序后继）
TreeNode* successor = findMin(node->right);
node->val = successor->val;
node->right = deleteNode(node->right, successor->val);
}
return node;
}
TreeNode* findMin(TreeNode* node) {
while (node && node->left) {
node = node->left;
}
return node;
}使用示例
下面是一个简单的测试用法：
#includeusing namespace std; int main() { BST tree; tree.insert(5); tree.insert(3); tree.insert(7); tree.insert(2); tree.insert(4);
cout zuojiankuohaophpcnzuojiankuohaophpcn "Search 4: " zuojiankuohaophpcnzuojiankuohaophpcn (tree.search(4) ? "Found" : "Not found") zuojiankuohaophpcnzuojiankuohaophpcn endl; cout zuojiankuohaophpcnzuojiankuohaophpcn "Search 6: " zuojiankuohaophpcnzuojiankuohaophpcn (tree.search(6) ? "Found" : "Not found") zuojiankuohaophpcnzuojiankuohaophpcn endl; tree.remove(3); cout zuojiankuohaophpcnzuojiankuohaophpcn "After deleting 3, search 3: " zuojiankuohaophpcnzuojiankuohaophpcn (tree.search(3) ? "Found" : "Not found") zuojiankuohaophpcnzuojiankuohaophpcn endl; return 0;}
基本上就这些。这个实现覆盖了BST的核心功能：插入保持有序，查找利用二分逻辑，删除处理三种情况。注意递归写法清晰易懂，适合学习和实际使用。
