一、树形结构综合实战：实现一个通用的二叉树库
树形结构，说白了就是数据之间的“父子关系”。你想想看，文件系统、HTML的DOM树、甚至你家里的族谱，都是树。而在所有树里，二叉树是最基础、最常用的一种。今天我们就来手写一个通用的二叉树库，涵盖创建、遍历、销毁、序列化与反序列化。
我个人习惯把二叉树库做成“通用”的——不绑定具体数据类型，用 void* 存数据，用函数指针处理比较和打印。这样以后不管你是存整数、字符串还是结构体，都能复用同一套代码。
1.1 二叉树的结构定义
先定义节点和树的结构。我建议把数据域和指针域分开，方便扩展。
// 二叉树节点
typedef struct BTNode {
void *data; // 数据域，通用指针
struct BTNode *left; // 左孩子
struct BTNode *right; // 右孩子
} BTNode;
// 二叉树本体
typedef struct BinaryTree {
BTNode *root; // 根节点
size_t data_size; // 数据元素大小
void (*print)(void *); // 打印函数指针
int (*compare)(void *, void *); // 比较函数指针
} BinaryTree;
核心要点：
- 用 void* 存储数据，实现“通用”
- data_size 用于深拷贝数据，避免浅拷贝问题
- print 和 compare 是函数指针，让树“知道”怎么处理你的数据
1.2 创建二叉树
创建一棵树，我习惯分两步：先初始化树结构，再插入节点。这里我们用一个辅助函数来创建节点。
// 创建节点（内部使用）
static BTNode* create_node(void *data, size_t data_size) {
BTNode *node = (BTNode*)malloc(sizeof(BTNode));
if (!node) return NULL;
node->data = malloc(data_size);
if (!node->data) {
free(node);
return NULL;
}
memcpy(node->data, data, data_size);
node->left = node->right = NULL;
return node;
}
// 初始化树
BinaryTree* tree_init(size_t data_size,
void (*print)(void*),
int (*compare)(void*, void*)) {
BinaryTree *tree = (BinaryTree*)malloc(sizeof(BinaryTree));
if (!tree) return NULL;
tree->root = NULL;
tree->data_size = data_size;
tree->print = print;
tree->compare = compare;
return tree;
}
避坑指南：我曾经在项目中直接用赋值操作（node->data = data）来存数据，结果外部数据一释放，树里的指针就变成野指针了。所以一定要用 memcpy 做深拷贝，树自己管自己的内存。
1.3 遍历二叉树
遍历是二叉树最核心的操作。我把它分成三类：深度优先（前序、中序、后序）和广度优先（层序）。
为什么要有三种深度优先？说白了就是“什么时候访问根节点”的问题。
| 遍历方式 | 访问顺序 | 典型应用 |
|---|---|---|
| 前序遍历 | 根 → 左 → 右 | 复制一棵树 |
| 中序遍历 | 左 → 根 → 右 | 二叉搜索树排序输出 |
| 后序遍历 | 左 → 右 → 根 | 销毁一棵树 |
| 层序遍历 | 从上到下，从左到右 | 求树的高度、宽度 |
// 前序遍历（递归版）
void preorder(BTNode *node, void (*visit)(void*)) {
if (!node) return;
visit(node->data); // 先访问根
preorder(node->left, visit); // 再左
preorder(node->right, visit); // 最后右
}
// 中序遍历（递归版）
void inorder(BTNode *node, void (*visit)(void*)) {
if (!node) return;
inorder(node->left, visit);
visit(node->data);
inorder(node->right, visit);
}
// 后序遍历（递归版）
void postorder(BTNode *node, void (*visit)(void*)) {
if (!node) return;
postorder(node->left, visit);
postorder(node->right, visit);
visit(node->data);
}
// 层序遍历（借助队列）
void levelorder(BTNode *root, void (*visit)(void*)) {
if (!root) return;
// 简单队列实现（这里用数组模拟）
BTNode *queue[1000];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
BTNode *cur = queue[front++];
visit(cur->data);
if (cur->left) queue[rear++] = cur->left;
if (cur->right) queue[rear++] = cur->right;
}
}
注意：递归遍历虽然代码简洁，但树很深时（比如几万层）会导致栈溢出。我建议生产环境中用迭代版（自己维护栈）来替代递归。不过教学场景下，递归更容易理解。
1.4 销毁二叉树
销毁树一定要用后序遍历。为什么？因为你要先删孩子，再删父亲。如果先删父亲，孩子就找不到了——内存泄漏就来了。
// 递归销毁节点
void destroy_node(BTNode *node) {
if (!node) return;
destroy_node(node->left); // 先销毁左子树
destroy_node(node->right); // 再销毁右子树
free(node->data); // 释放数据
free(node); // 释放节点
}
// 销毁整棵树
void tree_destroy(BinaryTree *tree) {
if (!tree) return;
destroy_node(tree->root);
free(tree);
}
个人经验：我曾经在销毁树时忘了 free(node->data)，结果 valgrind 报了一堆内存泄漏。后来我养成了一个习惯：谁分配，谁释放。既然 create_node 里 malloc 了 data，那 destroy_node 里就必须 free 它。
1.5 序列化与反序列化
序列化就是把树“拍平”成字符串或数组，方便存储或网络传输。反序列化就是反过来，从字符串重建树。
我常用的序列化格式是前序遍历 + 特殊标记。空节点用 '#' 表示，每个节点数据后面加一个分隔符（比如 ','）。
// 序列化（前序遍历）
void serialize_helper(BTNode *node, char *buf, int *idx) {
if (!node) {
buf[(*idx)++] = '#';
buf[(*idx)++] = ',';
return;
}
// 假设数据是 int 类型，用 sprintf 转换
char temp[32];
sprintf(temp, "%d,", *(int*)(node->data));
int len = strlen(temp);
memcpy(buf + *idx, temp, len);
*idx += len;
serialize_helper(node->left, buf, idx);
serialize_helper(node->right, buf, idx);
}
char* tree_serialize(BinaryTree *tree) {
char *buf = (char*)malloc(1024);
int idx = 0;
serialize_helper(tree->root, buf, &idx);
buf[idx] = '\0';
return buf;
}
反序列化时，我习惯用一个全局索引来遍历字符串。
// 反序列化
BTNode* deserialize_helper(char *buf, int *idx) {
if (buf[*idx] == '#') {
*idx += 2; // 跳过 '#,'
return NULL;
}
// 读取数字（假设是 int）
int val = 0;
while (buf[*idx] != ',') {
val = val * 10 + (buf[*idx] - '0');
(*idx)++;
}
(*idx)++; // 跳过 ','
BTNode *node = create_node(&val, sizeof(int));
node->left = deserialize_helper(buf, idx);
node->right = deserialize_helper(buf, idx);
return node;
}
BinaryTree* tree_deserialize(char *buf, size_t data_size,
void (*print)(void*),
int (*compare)(void*, void*)) {
BinaryTree *tree = tree_init(data_size, print, compare);
int idx = 0;
tree->root = deserialize_helper(buf, &idx);
return tree;
}
小技巧：序列化时我建议用前序遍历，因为根节点在前，反序列化时可以先创建根，再递归创建左右子树，逻辑很顺。如果用中序或后序，反序列化会麻烦很多。
1.6 知识体系总览
下面这张图总结了二叉树库的核心模块和它们之间的关系：
1.7 完整使用示例
最后，我们把这些模块串起来，看看怎么用：
// 打印整数的函数
void print_int(void *data) {
printf("%d ", *(int*)data);
}
// 比较整数的函数
int compare_int(void *a, void *b) {
return *(int*)a - *(int*)b;
}
int main() {
// 1. 初始化树
BinaryTree *tree = tree_init(sizeof(int), print_int, compare_int);
// 2. 手动构建一棵树
int vals[] = {1, 2, 3, 4, 5};
tree->root = create_node(&vals[0], sizeof(int));
tree->root->left = create_node(&vals[1], sizeof(int));
tree->root->right = create_node(&vals[2], sizeof(int));
tree->root->left->left = create_node(&vals[3], sizeof(int));
tree->root->left->right = create_node(&vals[4], sizeof(int));
// 3. 遍历
printf("前序: "); preorder(tree->root, print_int); printf("\n");
printf("中序: "); inorder(tree->root, print_int); printf("\n");
printf("后序: "); postorder(tree->root, print_int); printf("\n");
printf("层序: "); levelorder(tree->root, print_int); printf("\n");
// 4. 序列化
char *serial = tree_serialize(tree);
printf("序列化: %s\n", serial);
// 5. 反序列化
BinaryTree *tree2 = tree_deserialize(serial, sizeof(int), print_int, compare_int);
printf("反序列化后前序: "); preorder(tree2->root, print_int); printf("\n");
// 6. 销毁
free(serial);
tree_destroy(tree);
tree_destroy(tree2);
return 0;
}
输出结果：
前序: 1 2 4 5 3
中序: 4 2 5 1 3
后序: 4 5 2 3 1
层序: 1 2 3 4 5
序列化: 1,2,4,#,#,5,#,#,3,#,#,
反序列化后前序: 1 2 4 5 3
嗯，到这里，一个通用的二叉树库就完成了。你想想看，这套代码稍加改造就能用在很多地方——比如表达式树、哈夫曼树、甚至数据库的索引结构。核心就是那四个模块：创建、遍历、销毁、序列化。把这四个吃透了，树这块你就拿下了。
公众号:蓝海资料掘金营，微信deep3321