概述
二叉搜索树（Binary Search Tree，简称 BST）是计算机科学中一种重要的树形数据结构。它利用键值的有序性，高效支持数据的插入、删除和查找操作，是许多复杂算法的基础组件。
核心性质在于：若左子树不为空，则所有节点值小于根节点；若右子树不为空，则所有节点值大于根节点。左右子树也均为二叉搜索树。这意味着中序遍历的结果必然是升序序列。
核心实现
下面展示基于 C++ 的迭代式实现。相比递归，迭代法在处理深层树时能避免栈溢出风险，更适合生产环境。
template <class K>
struct BSTreeNode {
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key) : _left(nullptr), _right(nullptr), _key(key) {}
};
template <class K>
class BSTree {
typedef BSTreeNode<K> Node;
public:
BSTree() : _root(nullptr) {}
~BSTree() { Destroy(_root); }
bool Insert(const K& key) {
if (_root == nullptr) {
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (key > cur->_key) {
parent = cur;
cur = cur->_right;
} else if (key < cur->_key) {
parent = cur;
cur = cur->_left;
} else {
return false; // 不允许重复
}
}
cur = new Node(key);
if (key > parent->_key)
parent->_right = cur;
else
parent->_left = cur;
return true;
}
bool Find(const K& key) {
Node* cur = _root;
while (cur) {
if (key > cur->_key) cur = cur->_right;
else if (key < cur->_key) cur = cur->_left;
else return true;
}
return false;
}
bool Erase(const K& key) {
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (key > cur->_key) {
parent = cur;
cur = cur->_right;
} else if (key < cur->_key) {
parent = cur;
cur = cur->_left;
} else {
// 找到目标节点，分情况处理
if (cur->_left == nullptr) {
if (cur == _root) _root = cur->_right;
else if (parent->_right == cur) parent->_right = cur->_right;
else parent->_left = cur->_right;
} else if (cur->_right == nullptr) {
if (cur == _root) _root = cur->_left;
else if (parent->_right == cur) parent->_right = cur->_left;
else parent->_left = cur->_left;
} else {
// 左右都不为空，找左子树最大值替换
Node* leftMaxParent = cur;
Node* leftMax = cur->_left;
while (leftMax->_right) {
leftMaxParent = leftMax;
leftMax = leftMax->_right;
}
swap(cur->_key, leftMax->_key);
if (leftMaxParent->_left == leftMax)
leftMaxParent->_left = leftMax->_left;
else
leftMaxParent->_right = leftMax->_left;
delete leftMax;
return true;
}
delete cur;
return true;
}
}
return false;
}
private:
void Destroy(Node*& root) {
if (!root) return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
Node* _root;
};
注意删除操作是难点。当节点有两个子节点时，通常用左子树的最大值或右子树的最小值替换当前节点的值，然后删除那个替代节点。这样既保持了 BST 性质，又避免了复杂的指针重连逻辑。swap 对于指针交换的是地址内容，对于基本类型交换的是值，这里我们交换的是 key 值。
性能对比
与有序数组的二分查找相比，BST 在插入和删除上更具优势（O(log N)），而数组需要移动元素（O(N)）。但 BST 的劣势在于最坏情况下可能退化为链表，导致查询效率降至 O(N)。因此，在实际工程中常需配合平衡策略（如 AVL 树、红黑树）使用。
搜索模型
- Key 搜索：快速判断存在性。例如门禁系统验证车辆权限。
- Key-Value 搜索：通过键查找对应值。例如高铁实名制车票系统。
注意 key 一般是不允许重复的信息。如果是 k-v 模型，成员变量需增加 value，Insert 和 Erase 操作的形参也要相应调整。
实战演练
1. 二叉搜索树转双向链表
利用中序遍历的特性，将节点的 left 指向前驱，right 指向后继。遍历时维护一个 prev 引用即可。
易错点：最后返回的头结点通常是整棵树的最左侧节点，而非传入的根节点。且叶子节点也需要更新 prev->right。
void Inorder(TreeNode* cur, TreeNode*& prev) {
if (!cur) return;
Inorder(cur->left, prev);
cur->left = prev;
if (prev) prev->right = cur;
prev = cur;
Inorder(cur->right, prev);
}
2. 根据遍历序列构造二叉树
给定前序和中序遍历，可以唯一确定一棵二叉树。前序确定根，中序分割左右子树区间。后序与中序同理，只是根的位置不同。
关键点：递归时需要传递索引引用，确保全局索引状态同步更新。创建空间时记得用 new，且参数要带引用。
3. 非递归遍历
使用栈模拟递归过程。前序遍历在入栈时访问节点；中序遍历在出栈时访问节点；后序遍历较复杂，需记录上一个访问节点，判断是否满足'右子树为空'或'右子树已访问'的条件。
这些题目涵盖了树结构的核心操作，掌握它们对理解递归、栈以及指针操作至关重要。实际编码时，注意区分 while 和 if 的使用场景，避免死循环或漏判。
