Learn-Algorithms 二叉树建树实战：从有序数组建 BST 到树的序列化与恢复

• 教程

本篇技术指南聚焦算法面试中两类高频的"建树"问题——把有序数组建成二叉搜索树（BST）与将树结构持久化到文件后完整恢复。基于本仓库《算法学习笔记》中的 7.2 二叉树-建树.md 为核心骨架，并结合仓库内 二叉查找树实现 的源码细节展开。读完你将掌握：有序数组递归建树的标准写法与复杂度分析、递归改写非递归的方法论，以及用先序/层序遍历加空标记完成树序列化与反序列化的完整方案。

一、把一个有序整数数组放到二叉树中：BST 建树

原文档的第一个问题是经典面试题：给定一个有序整数数组，将其构建为一棵二叉树。这道题的本质是二叉搜索树（Binary Search Tree, BST）的建树方法，其标准解法非常简单——递归取中间元素作为根节点。

1.1 为什么取中间元素

二叉搜索树的定义在仓库文档 二叉查找树.md 中有明确总结：

1. 若任意节点的左子树不为空，则左子树上所有节点的值小于它的根节点值；
2. 若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点值；
3. 任意节点的左右子树本身也是二叉查找树；
4. 没有键值相等的节点。

由于数组已经有序，取mid = (left + right) / 2作为根，恰好满足"左半部分都比根小、右半部分都比根大"；左右子区间递归处理，自然得到一棵平衡的 BST（当数组为完全有序且长度确定时，每次二分切割保证左右子树高度差不超过 1），中序遍历结果即为原数组本身，有序性质被完整保留。

1.2 仓库中的节点结构定义

仓库 bisearchtree.h 给出了完整的二叉查找树节点定义，建树代码应与此保持一致：

typedef int ElemType; typedef struct BiSearchTree{ ElemType key; struct BiSearchTree *lChild; struct BiSearchTree *rChild; }BiSearchTree;

1.3 递归建树完整实现

依据上述节点定义，有序数组建 BST 的核心代码如下：

#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct BiSearchTree{ ElemType key; struct BiSearchTree *lChild; struct BiSearchTree *rChild; }BiSearchTree; /* 有序数组 [left, right] 闭区间建树 */ BiSearchTree *sorted_array_to_bst(int *a, int left, int right){ if (left > right) { // 递归终止条件：空区间 return NULL; } int mid = (left + right) / 2; // 取中间元素为根 BiSearchTree *root = (BiSearchTree *)malloc(sizeof(BiSearchTree)); if (root == NULL) { printf("malloc failure\n"); return NULL; } root->key = a[mid]; root->lChild = sorted_array_to_bst(a, left, mid - 1); // 左子区间递归 root->rChild = sorted_array_to_bst(a, mid + 1, right); // 右子区间递归 return root; } /* 中序遍历，验证建树结果是否有序 */ void inorder_traversal(BiSearchTree *tree){ if (tree) { inorder_traversal(tree->lChild); printf("%d ", tree->key); inorder_traversal(tree->rChild); } } int main(){ int a[] = {3, 7, 9, 15, 20, 33, 50}; int n = sizeof(a) / sizeof(int); BiSearchTree *root = sorted_array_to_bst(a, 0, n - 1); printf("inorder traversal: "); inorder_traversal(root); // 输出 3 7 9 15 20 33 50，与原数组一致 printf("\n"); return 0; }

1.4 复杂度与正确性分析

• 时间复杂度：每个数组元素恰好被创建为一个节点，递归层数等于树高，单次节点创建为 O(1)，因此总体为O(n)；
• 空间复杂度：递归调用栈深度即树高，对平衡 BST 为 O(log n)；不将辅助栈计入时为 O(1) 额外存储；
• 正确性验证：中序遍历结果应与原数组完全相同。仓库 main.c 中对插入建树后的中序遍历测试结果（3 19 55 65 122 180）印证了"BST 中序遍历必为递增序列"这一性质，可用于校验任意建树方法的正确性。

二、递归与非递归：关于栈溢出的方法论

原文档特别强调了两点工程经验：

1. 关于树的算法设计一定要联想到递归，因为树本身就是递归定义的（每个节点的子树还是一棵树）；
2. 学会把递归改成非递归是一种必要技术——递归会造成栈溢出，系统底层程序中非不得已最好不要用；而对某些数学问题（如分治、DP 状态转移），则要习惯用递归去解决。

这段论述对应到本题，有两种改写路径：

2.1 迭代方式建 BST（自顶向下逐点插入）

仓库 bisearchtree.c 中的bisearch_tree_insert就是典型的非递归插入实现，其核心是用while循环沿搜索路径找空位：

BiSearchTree *bisearch_tree_insert(BiSearchTree *tree, ElemType node){ BiSearchTree *t = tree; BiSearchTree *parent = NULL; BiSearchTree *newNode = (BiSearchTree *)malloc(sizeof(BiSearchTree)); if (NULL == newNode) { printf("malloc failure\n"); return tree; } newNode->key = node; newNode->lChild = NULL; newNode->rChild = NULL; if (NULL == t) { // 空树，新节点直接作为根 tree = newNode; return tree; } // 迭代查找合适的插入位置，同时记录 parent while (t != NULL) { if (node < t->key) { parent = t; t = t->lChild; } else if (node == t->key) { printf("insert ignore:the bi search tree has the node with %d\n", node); break; // BST 不允许重复键，直接忽略 } else { parent = t; t = t->rChild; } } if (parent != NULL) { if (node > parent->key) { parent->rChild = newNode; } else { parent->lChild = newNode; } } return tree; }

用该函数将有序数组逐个插入，即可得到一棵 BST。需要注意：迭代逐个插入得到的树高度依赖插入顺序——有序数组顺序插入会退化成链表（树高 O(n)），这正是"有序数组建树要取中点分治"的原因；而 main.c 中的插入顺序（19、3、122、55、65、180）是打散的，因此树保持平衡。

2.2 显式栈将递归转非递归

更通用的改写手段是"显式栈"：把递归调用栈搬到堆上，用自定义栈模拟系统栈帧。例如非递归中序遍历：

typedef struct StackNode { BiSearchTree *node; struct StackNode *next; } StackNode; void inorder_traversal_iterative(BiSearchTree *root){ // 用链表栈模拟系统调用栈 StackNode *stack = NULL; BiSearchTree *cur = root; while (cur != NULL || stack != NULL) { while (cur != NULL) { // 一路向左，模拟递归压栈 StackNode *s = (StackNode *)malloc(sizeof(StackNode)); s->node = cur; s->next = stack; stack = s; cur = cur->lChild; } if (stack != NULL) { // 出栈，模拟递归返回 StackNode *top = stack; stack = stack->next; printf("%d ", top->node->key); cur = top->node->rChild; free(top); } } }

何时必须用非递归：树高接近甚至超过系统栈上限（如接近 10 万层的极端退化树）时，递归必然栈溢出；而显式栈在堆上分配，容量由内存决定，稳健得多。何时优先用递归：代码可读性、正确性论证（尤其涉及分治、后序合并场景，如归并排序式的自底向上问题）递归表达力远超循环。

三、恢复树结构：序列化与反序列化

原文档的第二个问题是：有一棵树（节点为字符串或整数），请写代码将树的结构和数据写到一个文件中，并能通过读取该文件恢复树结构。这本质是树的**序列化（Serialize）与反序列化（Deserialize）**问题，也是 Redis、文件系统、分布式存储中持久化树结构的通用模型。

3.1 核心难点与方案选择

难点在于：仅存节点值无法还原父子关系，必须把"空指针"也编码进文件。业界最常用的两套方案：

3.2 先序遍历 + 空标记（推荐实现）

序列化时做一次先序遍历（根 → 左 → 右），遇到 NULL 输出#占位；反序列化时按同样顺序读入，遇到#返回 NULL，恰好与先序递归结构一一对应。

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef int ElemType; typedef struct BiSearchTree{ ElemType key; struct BiSearchTree *lChild; struct BiSearchTree *rChild; }BiSearchTree; /* ---------- 序列化：先序遍历写入文件，NULL 用 "#" 标记 ---------- */ void serialize(BiSearchTree *root, FILE *fp){ if (root == NULL) { fprintf(fp, "# "); return; } fprintf(fp, "%d ", root->key); serialize(root->lChild, fp); serialize(root->rChild, fp); } /* ---------- 反序列化：按先序顺序读回 ---------- */ BiSearchTree *deserialize(FILE *fp){ char token[32]; if (fscanf(fp, "%s", token) != 1) { // 文件读尽，正常结束 return NULL; } if (strcmp(token, "#") == 0) { // 空标记，表示该位置无节点 return NULL; } BiSearchTree *root = (BiSearchTree *)malloc(sizeof(BiSearchTree)); root->key = atoi(token); root->lChild = deserialize(fp); // 先序：先恢复左子树 root->rChild = deserialize(fp); // 再恢复右子树 return root; } /* 用中序遍历验证恢复出的树 */ void inorder_traversal(BiSearchTree *tree){ if (tree) { inorder_traversal(tree->lChild); printf("%d ", tree->key); inorder_traversal(tree->rChild); } }

例如对下面的树：

10 / \ 6 14 / \ / \ 4 8 12 16

先序遍历序列化为：10 6 4 # # 8 # # 14 12 # # 16 # #。整个文件只有 15 个 token，其中#精确记录了两个叶子节点的四个 NULL 孩子位置，读取时递归即可 1:1 重建原树。对字符串节点同样成立，只需把%d/atoi换成字符串读写即可。

int main(){ // 构建一棵测试树（复用有序数组建树） int a[] = {4, 6, 8, 10, 12, 14, 16}; BiSearchTree *root = sorted_array_to_bst(a, 0, 6); FILE *fp = fopen("tree.dat", "w"); serialize(root, fp); fclose(fp); // 从文件恢复 FILE *rf = fopen("tree.dat", "r"); BiSearchTree *restored = deserialize(rf); fclose(rf); printf("restored inorder: "); inorder_traversal(restored); // 输出 4 6 8 10 12 14 16，结构完整恢复 printf("\n"); return 0; }

3.3 层序遍历 + 空标记（扩展方案）

若题目限定"按层打印"（仓库 7.1 二叉树-遍历.md 中的按层打印题）或要求文件更紧凑，可改用层序编码：

/* 序列化：层序输出，NULL 输出 "#" */ void serialize_level(BiSearchTree *root, FILE *fp){ /* 用一个简易队列保存待输出节点 */ BiSearchTree *queue[1024]; int head = 0, tail = 0; queue[tail++] = root; while (head < tail) { BiSearchTree *cur = queue[head++]; if (cur == NULL) { fprintf(fp, "# "); } else { fprintf(fp, "%d ", cur->key); queue[tail++] = cur->lChild; // NULL 也入队，统一编码 queue[tail++] = cur->rChild; } } } /* 反序列化：同样借助队列逐层重建 */ BiSearchTree *deserialize_level(FILE *fp){ char token[32]; if (fscanf(fp, "%s", token) != 1) return NULL; if (strcmp(token, "#") == 0) return NULL; // 空树 BiSearchTree *root = (BiSearchTree *)malloc(sizeof(BiSearchTree)); root->key = atoi(token); BiSearchTree *queue[1024]; int head = 0, tail = 0; queue[tail++] = root; while (head < tail && fscanf(fp, "%s", token) == 1) { BiSearchTree *cur = queue[head++]; /* 读左孩子 */ if (strcmp(token, "#") == 0) { cur->lChild = NULL; } else { BiSearchTree *l = (BiSearchTree *)malloc(sizeof(BiSearchTree)); l->key = atoi(token); cur->lChild = l; queue[tail++] = l; } /* 读右孩子 */ if (fscanf(fp, "%s", token) == 1 && strcmp(token, "#") != 0) { BiSearchTree *r = (BiSearchTree *)malloc(sizeof(BiSearchTree)); r->key = atoi(token); cur->rChild = r; queue[tail++] = r; } } return root; }

层序方案的编码结果是：10 6 14 4 8 12 16 # # # # # # # #，与 7.1 二叉树-遍历.md 中"按层从左到右打印"的输出顺序8 6 10 5 7 9 11完全同构——层序遍历天然适合序列化，且能保留树的层级语义。

3.4 进阶：由两种遍历序列重建二叉树

当题目不给空标记，而是给出"前序 + 中序"（或"后序 + 中序"）两组序列时，可用切分法重建：前序序列的第一个元素必为根，在对应中序序列中定位根的位置，左侧即左子树中序、右侧即右子树中序；前序剩余部分按左右子树长度切分后递归。这与仓库 7.1 二叉树-遍历.md 中"判断整数序列是不是二元查找树的后序遍历结果"互为逆运算，是二叉树的另一大类建树考题，可作为本节内容的延伸练习。

四、建树相关核心考点小结

结合原文档与仓库源码，整理二叉树建树类问题的答题清单：

1. 有序数组建 BST：递归取中点，O(n) 时间、O(log n) 栈深，中序遍历验证有序性；
2. 递归与非递归：树的定义天然递归，优先递归表达；深树场景改用显式栈或迭代插入，仓库 bisearchtree.c 提供了完整的迭代插入、查找、删除参考实现；
3. 序列化与反序列化：先序/层序 + 空标记#是最普适的编码；先序编码递归恢复最简洁，层序编码按队列恢复最直观；
4. 验证手段：无论用什么方法建树，最终都要用中序遍历递增这一 BST 不变量做正确性检验（参考 main.c 的测试输出）；
5. 延伸关联：树节点结构、递归框架与遍历细节见 7 二叉树.md；BST 插入、删除的完整工程实现见 二叉查找树.md；BST 验证、搜索、插入、删除的面试变体见 7.5 二叉搜索树.md。

掌握上述方法后，面对"建树"类题目即可快速定位属于哪种模式：是"有序数据 → 平衡 BST"，还是"遍历序列 → 恢复树"，抑或"文件存储 → 反序列化"，然后套用对应框架在十分钟内写出可运行代码。

• 教程