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 }

核心操作说明

1. 插入

   • 递归找到合适位置创建新节点
   • 时间复杂度：$O(h)$（$h$为树高度）

2. 删除

   • 分三种情况处理：
     • 叶子节点：直接删除
     • 单子节点：用子节点替换
     • 双子节点：用后继节点（右子树最小节点）替换
   • 时间复杂度：$O(h)$

3. 查找

   • 从根节点开始逐层比较
   • 时间复杂度：$O(h)$

4. 遍历

   • 中序遍历可输出有序序列
   • 时间复杂度：$O(n)$（$n$为节点数）

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