二叉排序树（BST）

二叉排序树（Binary Search Tree, BST） 是一种特殊的二叉树，它具有以下性质：

对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值。

对于树中的每个节点，其右子树中的所有节点的值都大于该节点的值。

左右子树也分别是二叉排序树。

二叉排序树的主要用途是实现动态集合操作，如插入、删除和查找。

---

1. 二叉排序树的基本操作 1.1 查找

在二叉排序树中查找一个值：

如果当前节点为空，返回 nullptr。

如果目标值等于当前节点的值，返回当前节点。

如果目标值小于当前节点的值，递归查找左子树。

如果目标值大于当前节点的值，递归查找右子树。

代码实现： TreeNode* search(TreeNode* root, int key) { if (root == nullptr || root->val == key) { return root; } if (key < root->val) { return search(root->left, key); } else { return search(root->right, key); } }

---

1.2 插入

在二叉排序树中插入一个新值：

如果当前节点为空，创建一个新节点并返回。

如果目标值小于当前节点的值，递归插入到左子树。

如果目标值大于当前节点的值，递归插入到右子树。

代码实现： TreeNode* insert(TreeNode* root, int key) { if (root == nullptr) { return new TreeNode(key); } if (key < root->val) { root->left = insert(root->left, key); } else if (key > root->val) { root->right = insert(root->right, key); } return root; }

---

1.3 删除

在二叉排序树中删除一个值：

如果当前节点为空，返回 nullptr。

如果目标值小于当前节点的值，递归删除左子树中的节点。

如果目标值大于当前节点的值，递归删除右子树中的节点。

如果目标值等于当前节点的值：

如果节点是叶子节点，直接删除。

如果节点只有一个子节点，用子节点替换当前节点。

如果节点有两个子节点，用右子树的最小值（或左子树的最大值）替换当前节点的值，然后删除右子树的最小值。

代码实现： TreeNode* deleteNode(TreeNode* root, int key) { if (root == nullptr) { return nullptr; } if (key < root->val) { root->left = deleteNode(root->left, key); } else if (key > root->val) { root->right = deleteNode(root->right, key); } else { // 节点是叶子节点或只有一个子节点 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; } // 节点有两个子节点 TreeNode* temp = findMin(root->right); // 找到右子树的最小值 root->val = temp->val; // 用最小值替换当前节点的值 root->right = deleteNode(root->right, temp->val); // 删除右子树的最小值 } return root; } TreeNode* findMin(TreeNode* root) { while (root->left != nullptr) { root = root->left; } return root; }

---

2. 二叉排序树的遍历

二叉排序树的中序遍历结果是一个有序序列。

2.1 中序遍历 void inorder(TreeNode* root) { if (root == nullptr) return; inorder(root->left); cout << root->val << " "; inorder(root->right); } 2.2 前序遍历 void preorder(TreeNode* root) { if (root == nullptr) return; cout << root->val << " "; preorder(root->left); preorder(root->right); } 2.3 后序遍历 void postorder(TreeNode* root) { if (root == nullptr) return; postorder(root->left); postorder(root->right); cout << root->val << " "; }

---

3. 二叉排序树的性质

有序性：中序遍历结果是一个有序序列。

动态操作：支持高效的插入、删除和查找操作。

最坏情况：如果树退化为链表，时间复杂度会退化为 O(n)O(n)。

---

4. 平衡二叉排序树（BBST）

为了避免二叉排序树退化为链表，可以使用平衡二叉排序树（如 AVL 树、红黑树），它们通过旋转操作保持树的平衡，确保操作的时间复杂度为 O(log⁡n)O(logn)。

---

5. 代码示例：完整的二叉排序树实现 #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* insert(TreeNode* root, int key) { if (root == nullptr) { return new TreeNode(key); } if (key < root->val) { root->left = insert(root->left, key); } else if (key > root->val) { root->right = insert(root->right, key); } return root; } TreeNode* deleteNode(TreeNode* root, int key) { if (root == nullptr) { return nullptr; } if (key < root->val) { root->left = deleteNode(root->left, key); } else if (key > root->val) { root->right = deleteNode(root->right, key); } else { 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; } TreeNode* temp = findMin(root->right); root->val = temp->val; root->right = deleteNode(root->right, temp->val); } return root; } TreeNode* findMin(TreeNode* root) { while (root->left != nullptr) { root = root->left; } return root; } void inorder(TreeNode* root) { if (root == nullptr) return; inorder(root->left); cout << root->val << " "; inorder(root->right); } public: BST() : root(nullptr) {} void insert(int key) { root = insert(root, key); } void deleteNode(int key) { root = deleteNode(root, key); } void inorder() { inorder(root); cout << endl; } }; int main() { BST tree; tree.insert(50); tree.insert(30); tree.insert(20); tree.insert(40); tree.insert(70); tree.insert(60); tree.insert(80); cout << "Inorder traversal: "; tree.inorder(); cout << "Delete 20\n"; tree.deleteNode(20); tree.inorder(); cout << "Delete 30\n"; tree.deleteNode(30); tree.inorder(); cout << "Delete 50\n"; tree.deleteNode(50); tree.inorder(); return 0; }

---

6. 总结

二叉排序树是一种高效的数据结构，支持动态集合操作。

通过中序遍历可以得到有序序列。

为了避免退化为链表，可以使用平衡二叉排序树。

掌握二叉排序树的基本操作和性质，是学习更高级数据结构（如 AVL 树、红黑树）的基础！