C++二叉搜索树实现详解

以下是一个简单的二叉搜索树（Binary Search Tree, BST）的 C++ 实现，包含插入、删除、查找和遍历等基本操作：

#include <iostream>
using namespace std;

// 树节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BST {
private:
TreeNode* root;

// 插入节点（递归辅助函数）
TreeNode* insertHelper(TreeNode* node, int val) {
if (!node) return new TreeNode(val);
if (val < node->val) node->left = insertHelper(node->left, val);
else node->right = insertHelper(node->right, val);
return node;
}

// 查找最小节点（用于删除操作）
TreeNode* findMin(TreeNode* node) {
while (node->left) node = node->left;
return node;
}

// 删除节点（递归辅助函数）
TreeNode* deleteHelper(TreeNode* node, int val) {
if (!node) return nullptr;
if (val < node->val) node->left = deleteHelper(node->left, val);
else if (val > node->val) node->right = deleteHelper(node->right, val);
else {
// 情况1：叶子节点或仅有一个子节点
if (!node->left) return node->right;
if (!node->right) return node->left;
// 情况2：有两个子节点
TreeNode* successor = findMin(node->right);
node->val = successor->val;
node->right = deleteHelper(node->right, successor->val);
}
return node;
}

// 中序遍历（递归）
void inorderHelper(TreeNode* node) {
if (!node) return;
inorderHelper(node->left);
cout << node->val << " ";
inorderHelper(node->right);
}

public:
BST() : root(nullptr) {}

// 插入操作
void insert(int val) {
root = insertHelper(root, val);
}

// 删除操作
void remove(int val) {
root = deleteHelper(root, val);
}

// 查找操作
bool search(int val) {
TreeNode* cur = root;
while (cur) {
if (val == cur->val) return true;
cur = (val < cur->val) ? cur->left : cur->right;
}
return false;
}

// 中序遍历
void inorder() {
inorderHelper(root);
cout << endl;
}
};

int main() {
BST tree;
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);

cout << "中序遍历: ";
tree.inorder(); // 输出: 20 30 40 50 70

cout << "查找40: " << (tree.search(40) ? "存在" : "不存在") << endl;
cout << "删除30后: ";
tree.remove(30);
tree.inorder(); // 输出: 20 40 50 70
}

核心操作说明

注意：二叉搜索树的性能取决于树的高度$h$。理想情况下$h = \\log_2 n$（平衡树），最坏情况下$h = n$（退化为链表）。如需优化可研究平衡二叉搜索树（如 AVL 树、红黑树）。