二叉搜索树（BST）：定义、性质与基本操作
二叉搜索树，英文叫 Binary Search Tree，简称 BST。说实话，这是我在实际项目中用得最多的树结构之一。没有它，很多查找问题会变得非常棘手。
先问大家一个问题：给你一堆数字，怎么存才能最快找到某个数？
数组？查找 O(n)，太慢。有序数组？二分查找 O(log n)，但插入删除要移动元素，麻烦。哈希表？查找 O(1)，但没法做范围查询。
BST 就是来解决这个矛盾的。它既有链表的灵活性，又有接近二分查找的效率。
BST 的定义
BST 是一棵二叉树，每个节点最多有两个孩子。它有两个核心约束：
- 左子树上所有节点的值，都小于根节点的值
- 右子树上所有节点的值，都大于根节点的值
而且，左右子树本身也必须是 BST。这个定义是递归的，你想想看，是不是很像二分查找的树形版本？
重要性质：对 BST 进行中序遍历，得到的是一个递增的有序序列。这是 BST 最优雅的地方——树本身无序，但遍历结果有序。
BST 的节点结构
我习惯用这样的结构体来定义 BST 节点：
typedef struct BSTNode {
int data; // 节点存储的数据
struct BSTNode *left; // 左孩子指针
struct BSTNode *right; // 右孩子指针
} BSTNode, *BSTree;嗯，这里要注意：left 和 right 都是指针，指向子节点。如果某个方向没有子节点，就置为 NULL。
BST 的查找操作
查找是 BST 最基础的操作。说白了，就是利用树的有序性，每次比较后缩小一半的搜索范围。
算法思路很简单：
- 从根节点开始，如果根为空，查找失败
- 如果目标值等于当前节点值，查找成功
- 如果目标值小于当前节点值，递归查找左子树
- 如果目标值大于当前节点值，递归查找右子树
代码实现如下：
// 递归版本
BSTNode* search_recursive(BSTree root, int key) {
if (root == NULL || root->data == key) {
return root;
}
if (key < root->data) {
return search_recursive(root->left, key);
} else {
return search_recursive(root->right, key);
}
}
// 非递归版本（我更喜欢这个，性能更好）
BSTNode* search_iterative(BSTree root, int key) {
BSTNode *p = root;
while (p != NULL && p->data != key) {
if (key < p->data) {
p = p->left;
} else {
p = p->right;
}
}
return p;
}我的经验：非递归版本避免了函数调用栈的开销，在深度较大的树上性能优势明显。我曾经在一个嵌入式项目中，递归查找导致栈溢出，改成非递归后问题就解决了。
查找的时间复杂度是多少？
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况（平衡树） | O(log n) | 树的高度接近 log₂n |
| 最坏情况（退化为链表） | O(n) | 插入有序序列时发生 |
| 平均情况 | O(log n) | 随机插入时表现良好 |
避坑指南：我曾经在项目中直接按升序插入数据，结果 BST 退化成了一条链表，查找效率从 O(log n) 降到了 O(n)。后来我改用随机顺序插入，或者使用平衡树（如 AVL、红黑树）来解决这个问题。
BST 的插入操作
插入操作和查找很像。先找到合适的位置，然后把新节点挂上去。
算法步骤：
- 如果树为空，直接创建根节点
- 否则，从根开始比较：
- 如果值小于当前节点，往左走
- 如果值大于当前节点，往右走
- 如果值相等，根据需求处理（通常不插入重复值）
- 直到找到空位置，插入新节点
// 递归插入
BSTree insert_recursive(BSTree root, int key) {
if (root == NULL) {
BSTNode *newNode = (BSTNode*)malloc(sizeof(BSTNode));
newNode->data = key;
newNode->left = newNode->right = NULL;
return newNode;
}
if (key < root->data) {
root->left = insert_recursive(root->left, key);
} else if (key > root->data) {
root->right = insert_recursive(root->right, key);
}
// 如果相等，什么也不做（不插入重复值）
return root;
}
// 非递归插入
BSTree insert_iterative(BSTree root, int key) {
BSTNode *newNode = (BSTNode*)malloc(sizeof(BSTNode));
newNode->data = key;
newNode->left = newNode->right = NULL;
if (root == NULL) {
return newNode;
}
BSTNode *p = root;
BSTNode *parent = NULL;
while (p != NULL) {
parent = p;
if (key < p->data) {
p = p->left;
} else if (key > p->data) {
p = p->right;
} else {
// 重复值，释放新节点并返回
free(newNode);
return root;
}
}
// 找到插入位置，挂在父节点上
if (key < parent->data) {
parent->left = newNode;
} else {
parent->right = newNode;
}
return root;
}我的习惯：非递归插入需要额外维护一个 parent 指针，代码稍长但更可控。递归版本代码简洁，但要注意递归深度。我个人在工程中偏向非递归版本，调试起来更方便。
知识体系总览
下面这张图总结了 BST 的核心知识点，我把它画成了流程图，方便你理解整体脉络：
总结一下
BST 的核心就三件事：定义、查找、插入。定义保证了树的有序性，查找和插入都利用这个有序性来缩小范围。
我个人觉得，BST 是理解更复杂树结构（AVL、红黑树、B树）的基石。你把这个搞懂了，后面那些都是锦上添花。
最后提醒一句：BST 的性能高度依赖树的平衡性。如果数据是随机插入的，BST 表现很好。但如果数据有序或接近有序，BST 会退化。这时候就需要平衡树登场了——不过那是后面章节的内容。