二叉搜索树：从无序到有序的蜕变
树结构里最实用的，我觉得就是二叉搜索树了。说白了，它就是给二叉树加了个规则：左小右大。这个规则看似简单，但威力巨大。
BST 的核心定义：
- 左子树所有节点的值 < 根节点的值
- 右子树所有节点的值 > 根节点的值
- 左右子树也分别是 BST
我刚开始学的时候，总觉得这不就是排序吗？后来在项目中做字典查找，才发现 BST 的妙处——查找效率从 O(n) 直接降到 O(log n)。
查找操作：二分思想的树形实现
BST 的查找，其实就是二分查找的树形版本。你想想看，每次比较都能排除一半的节点。
// 递归查找
TreeNode* bst_search(TreeNode* root, int key) {
if (root == NULL || root->val == key)
return root;
if (key < root->val)
return bst_search(root->left, key);
else
return bst_search(root->right, key);
}
// 迭代查找（我更喜欢这个，省栈空间）
TreeNode* bst_search_iter(TreeNode* root, int key) {
while (root != NULL && root->val != key) {
if (key < root->val)
root = root->left;
else
root = root->right;
}
return root;
}我的经验：递归代码看着优雅，但深度大了容易爆栈。我在嵌入式项目里一律用迭代版本，内存占用可控。
插入操作：找到位置，挂上去
插入的逻辑很简单：先查找，找到空位就挂上去。但有个坑——重复值怎么处理？
我一般有两种策略：要么直接忽略（当作查找成功），要么在节点里加个 count 字段。看业务需求吧。
TreeNode* bst_insert(TreeNode* root, int key) {
if (root == NULL) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = key;
node->left = node->right = NULL;
return node;
}
if (key < root->val)
root->left = bst_insert(root->left, key);
else if (key > root->val)
root->right = bst_insert(root->right, key);
// 相等时，我选择不处理，或者加 count++
return root;
}注意：插入顺序会影响树的结构。如果按 1,2,3,4,5 的顺序插入，BST 会退化成链表！查找效率直接掉到 O(n)。
删除操作：三种情况，逐个击破
删除是 BST 里最麻烦的操作。我当年面试时就被问过，手写删除代码写错了三次……
其实就三种情况：
- 叶子节点：直接删，父节点指针置 NULL
- 只有一个孩子：让孩子顶上来
- 有两个孩子：找右子树的最小节点（或左子树的最大节点）替换
TreeNode* bst_delete(TreeNode* root, int key) {
if (root == NULL) return NULL;
if (key < root->val)
root->left = bst_delete(root->left, key);
else if (key > root->val)
root->right = bst_delete(root->right, key);
else {
// 情况1和2
if (root->left == NULL) {
TreeNode* temp = root->right;
free(root);
return temp;
}
if (root->right == NULL) {
TreeNode* temp = root->left;
free(root);
return temp;
}
// 情况3：找右子树最小节点
TreeNode* temp = find_min(root->right);
root->val = temp->val;
root->right = bst_delete(root->right, temp->val);
}
return root;
}
TreeNode* find_min(TreeNode* root) {
while (root->left != NULL)
root = root->left;
return root;
}避坑指南：我曾经在删除有两个孩子的节点时，直接 free 了替换节点，结果把整个树搞崩了。记住：替换的是值，不是节点本身。
平衡二叉树：让树不再歪脖子
BST 有个致命问题——不平衡。你想想看，如果数据是递增的，BST 就变成了一条线。查找效率还不如数组呢。
平衡二叉树（AVL）就是来解决这个问题的。它要求每个节点的左右子树高度差不超过 1。
AVL 的平衡因子：左子树高度 - 右子树高度，取值只能是 -1、0、1。
插入或删除后，如果平衡因子超出范围，就需要旋转调整。四种旋转情况：
| 失衡情况 | 旋转方式 | 场景 |
|---|---|---|
| LL（左左） | 右旋 | 插入到左子树的左孩子 |
| RR（右右） | 左旋 | 插入到右子树的右孩子 |
| LR（左右） | 先左旋后右旋 | 插入到左子树的右孩子 |
| RL（右左） | 先右旋后左旋 | 插入到右子树的左孩子 |
说实话，AVL 的旋转代码我每次写都要画图。我的建议是：先画图，再写代码。别硬记。
哈夫曼树与哈夫曼编码：数据压缩的基石
哈夫曼树，也叫最优二叉树。它的核心思想很简单：出现频率高的字符，用短编码；频率低的，用长编码。
我记得第一次用哈夫曼编码做文件压缩，压缩率能达到 40% 以上。当时觉得这玩意儿太神奇了。
构建哈夫曼树
步骤其实就三步：
- 把所有节点按权值排成最小堆
- 每次取两个最小的，合并成一个新节点
- 重复直到只剩一个节点
// 哈夫曼树节点
typedef struct HuffmanNode {
char ch;
int freq;
struct HuffmanNode *left, *right;
} HuffmanNode;
// 构建哈夫曼树（伪代码）
HuffmanNode* build_huffman_tree(char chars[], int freqs[], int n) {
// 1. 创建 n 个叶子节点
// 2. 放入最小堆
// 3. 循环 n-1 次：
// a. 取出两个最小节点
// b. 合并为新节点，权值相加
// c. 新节点入堆
// 4. 返回堆中最后一个节点
}哈夫曼编码
树建好了，编码就简单了。从根到叶子，左走是 0，右走是 1。
重要特性：哈夫曼编码是前缀编码——任何一个编码都不是另一个编码的前缀。这意味着解码时不会产生歧义。
举个例子：假设字符 A、B、C、D 的频率分别是 5、4、3、2。
构建的哈夫曼树可能是这样的：
(14)
/ \
(9) (5:A)
/ \
(5) (4:B)
/ \
(2:D) (3:C)
编码结果：
A: 1
B: 01
C: 001
D: 000我的经验：实际项目中，哈夫曼编码通常配合文件头一起使用。文件头里存着频率表或树结构，解码时先读文件头重建树，再解码数据。
注意：哈夫曼编码不是万能的。如果字符频率分布均匀，压缩效果就很差。我遇到过用哈夫曼压缩后文件反而变大的情况——因为文件头开销太大了。
本章知识体系
下面这张图总结了本章的核心内容，我建议你保存下来，复习时看一眼就全想起来了。
这三种树结构，从简单到复杂，从无序到有序，从平衡到压缩，层层递进。我个人觉得，掌握了它们，你对树的理解就上了一个大台阶。
学习建议：别光看代码。拿张纸，画一棵树，手动模拟插入、删除、旋转的过程。我当年就是这么练的，效果比看十遍代码都好。