好的，我们来学习二叉搜索树（Binary Search Tree, BST）在 C++ 中的基础实现。这是一种高效的数据结构，用于存储和检索数据。
二叉搜索树概述
二叉搜索树是一种特殊的二叉树，它满足以下性质：
- 每个节点都有一个关键值。
- 左子树中所有节点的关键值都小于其父节点的关键值。
- 右子树中所有节点的关键值都大于其父节点的关键值。
- 左右子树本身也必须是二叉搜索树。
这种结构使得查找、插入和删除操作的平均时间复杂度可以达到 $$O(\log n)$$。
C++ 实现要点
1. 节点结构定义
使用结构体TreeNode表示树中的节点，包含数据、指向左子树的指针和指向右子树的指针。
struct TreeNode { int val; // 节点存储的值 TreeNode *left; // 指向左子树的指针 TreeNode *right; // 指向右子树的指针 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数 };2. 基本操作
查找（Search）
从根节点开始，根据目标值与当前节点值的大小关系决定向左或向右子树搜索。
TreeNode* search(TreeNode* root, int target) { if (root == nullptr || root->val == target) return root; // 找到或树为空 if (target < root->val) return search(root->left, target); // 目标值小，搜索左子树 else return search(root->right, target); // 目标值大，搜索右子树 }插入（Insert）
找到合适的空位置（遵循 BST 规则）插入新节点。
TreeNode* insert(TreeNode* root, int val) { if (root == nullptr) return new TreeNode(val); // 创建新节点 if (val < root->val) root->left = insert(root->left, val); // 插入左子树 else if (val > root->val) root->right = insert(root->right, val); // 插入右子树 return root; // 返回当前节点指针 }删除（Delete）
删除操作需考虑三种情况：
- 无子节点：直接删除。
- 只有一个子节点：用子节点替代。
- 有两个子节点：找到右子树的最小节点（或左子树的最大节点）替代被删节点，再删除该节点。
TreeNode* deleteNode(TreeNode* root, int key) { if (root == nullptr) return root; // 树为空 if (key < root->val) root->left = deleteNode(root->left, key); // 在左子树删除 else if (key > root->val) root->right = deleteNode(root->right, key); // 在右子树删除 else { // 找到要删除的节点 // 情况1：无子节点或只有一个子节点 if (root->left == nullptr) { TreeNode* temp = root->right; delete root; return temp; } else if (root->right == nullptr) { TreeNode* temp = root->left; delete root; return temp; } // 情况3：有两个子节点 TreeNode* temp = root->right; while (temp->left != nullptr) temp = temp->left; // 找到右子树的最小节点 root->val = temp->val; // 用最小节点的值覆盖 root->right = deleteNode(root->right, temp->val); // 删除那个最小节点 } return root; }时间复杂度分析
- 查找、插入、删除：平均时间复杂度 $$O(\log n)$$，最坏情况（树退化成链表）$$O(n)$$。
- 遍历：中序遍历（Inorder Traversal）可以得到有序序列，时间复杂度 $$O(n)$$。
总结
二叉搜索树是 C++ 数据结构学习中的重要内容，理解其原理并掌握基本操作是实现更高级树结构（如 AVL 树、红黑树）的基础。请务必动手实践上述代码，加深理解。
