教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载本篇技术指南聚焦算法面试中两类高频的建树问题——把有序数组建成二叉搜索树BST与将树结构持久化到文件后完整恢复。基于本仓库《算法学习笔记》中的 7.2 二叉树-建树.md 为核心骨架并结合仓库内 二叉查找树实现 的源码细节展开。读完你将掌握有序数组递归建树的标准写法与复杂度分析、递归改写非递归的方法论以及用先序/层序遍历加空标记完成树序列化与反序列化的完整方案。一、把一个有序整数数组放到二叉树中BST 建树原文档的第一个问题是经典面试题给定一个有序整数数组将其构建为一棵二叉树。这道题的本质是二叉搜索树Binary Search Tree, BST的建树方法其标准解法非常简单——递归取中间元素作为根节点。1.1 为什么取中间元素二叉搜索树的定义在仓库文档 二叉查找树.md 中有明确总结若任意节点的左子树不为空则左子树上所有节点的值小于它的根节点值若任意节点的右子树不为空则右子树上所有节点的值均大于它的根节点值任意节点的左右子树本身也是二叉查找树没有键值相等的节点。由于数组已经有序取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 中序遍历必为递增序列这一性质可用于校验任意建树方法的正确性。二、递归与非递归关于栈溢出的方法论原文档特别强调了两点工程经验关于树的算法设计一定要联想到递归因为树本身就是递归定义的每个节点的子树还是一棵树学会把递归改成非递归是一种必要技术——递归会造成栈溢出系统底层程序中非不得已最好不要用而对某些数学问题如分治、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 核心难点与方案选择难点在于仅存节点值无法还原父子关系必须把空指针也编码进文件。业界最常用的两套方案方案编码方式恢复方式特点先序遍历 空标记值 值 # # 值 # # ...#表示 NULL 孩子按先序顺序递归重建实现最简洁一行递归即恢复层序遍历 空标记按层输出#表示缺失节点借助队列逐层重建天然适配按层打印场景文件更紧凑前序/后序 中序两段序列本身蕴含结构信息递归切分中序序列需两段序列常用于 LeetCode 系列重建题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 中判断整数序列是不是二元查找树的后序遍历结果互为逆运算是二叉树的另一大类建树考题可作为本节内容的延伸练习。四、建树相关核心考点小结结合原文档与仓库源码整理二叉树建树类问题的答题清单有序数组建 BST递归取中点O(n) 时间、O(log n) 栈深中序遍历验证有序性递归与非递归树的定义天然递归优先递归表达深树场景改用显式栈或迭代插入仓库 bisearchtree.c 提供了完整的迭代插入、查找、删除参考实现序列化与反序列化先序/层序 空标记#是最普适的编码先序编码递归恢复最简洁层序编码按队列恢复最直观验证手段无论用什么方法建树最终都要用中序遍历递增这一 BST 不变量做正确性检验参考 main.c 的测试输出延伸关联树节点结构、递归框架与遍历细节见 7 二叉树.mdBST 插入、删除的完整工程实现见 二叉查找树.mdBST 验证、搜索、插入、删除的面试变体见 7.5 二叉搜索树.md。掌握上述方法后面对建树类题目即可快速定位属于哪种模式是有序数据 → 平衡 BST还是遍历序列 → 恢复树抑或文件存储 → 反序列化然后套用对应框架在十分钟内写出可运行代码。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐Learn-Algorithms 树专题二叉树、BST、AVL、红黑树、B 树、Trie、堆与 Huffman 全解析Learn Algorithms 树专题二叉树、BST、AVL、红黑树、B 树、Trie、堆与 Huffman 全解析 本文以 Learn Algorithm教程Arnis 完整指南把真实地理数据 1:1 转换成 Minecraft 世界Arnis 完整指南把真实地理数据 1:1 转换成 Minecraft 世界 Arnis 是一款免费开源的地理数据转 Minecraft 工具读取 Open桌面应用游戏开发GISTalkGo 算法之美有序数组转二叉搜索树与不同的二叉搜索树 II——树的构造专题实战TalkGo 算法之美有序数组转二叉搜索树与不同的二叉搜索树 II——树的构造专题实战 本文基于 TalkGoGo 夜读开源社区 content/algo文档教程上一篇鸣潮自动化工具终极指南5分钟解放双手的完整解决方案下一篇FastAPI 混合接收文件与表单字段在同一请求中使用 File 和 Form创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Learn-Algorithms 二叉树建树实战：从有序数组建 BST 到树的序列化与恢复
教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载本篇技术指南聚焦算法面试中两类高频的建树问题——把有序数组建成二叉搜索树BST与将树结构持久化到文件后完整恢复。基于本仓库《算法学习笔记》中的 7.2 二叉树-建树.md 为核心骨架并结合仓库内 二叉查找树实现 的源码细节展开。读完你将掌握有序数组递归建树的标准写法与复杂度分析、递归改写非递归的方法论以及用先序/层序遍历加空标记完成树序列化与反序列化的完整方案。一、把一个有序整数数组放到二叉树中BST 建树原文档的第一个问题是经典面试题给定一个有序整数数组将其构建为一棵二叉树。这道题的本质是二叉搜索树Binary Search Tree, BST的建树方法其标准解法非常简单——递归取中间元素作为根节点。1.1 为什么取中间元素二叉搜索树的定义在仓库文档 二叉查找树.md 中有明确总结若任意节点的左子树不为空则左子树上所有节点的值小于它的根节点值若任意节点的右子树不为空则右子树上所有节点的值均大于它的根节点值任意节点的左右子树本身也是二叉查找树没有键值相等的节点。由于数组已经有序取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 中序遍历必为递增序列这一性质可用于校验任意建树方法的正确性。二、递归与非递归关于栈溢出的方法论原文档特别强调了两点工程经验关于树的算法设计一定要联想到递归因为树本身就是递归定义的每个节点的子树还是一棵树学会把递归改成非递归是一种必要技术——递归会造成栈溢出系统底层程序中非不得已最好不要用而对某些数学问题如分治、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 核心难点与方案选择难点在于仅存节点值无法还原父子关系必须把空指针也编码进文件。业界最常用的两套方案方案编码方式恢复方式特点先序遍历 空标记值 值 # # 值 # # ...#表示 NULL 孩子按先序顺序递归重建实现最简洁一行递归即恢复层序遍历 空标记按层输出#表示缺失节点借助队列逐层重建天然适配按层打印场景文件更紧凑前序/后序 中序两段序列本身蕴含结构信息递归切分中序序列需两段序列常用于 LeetCode 系列重建题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 中判断整数序列是不是二元查找树的后序遍历结果互为逆运算是二叉树的另一大类建树考题可作为本节内容的延伸练习。四、建树相关核心考点小结结合原文档与仓库源码整理二叉树建树类问题的答题清单有序数组建 BST递归取中点O(n) 时间、O(log n) 栈深中序遍历验证有序性递归与非递归树的定义天然递归优先递归表达深树场景改用显式栈或迭代插入仓库 bisearchtree.c 提供了完整的迭代插入、查找、删除参考实现序列化与反序列化先序/层序 空标记#是最普适的编码先序编码递归恢复最简洁层序编码按队列恢复最直观验证手段无论用什么方法建树最终都要用中序遍历递增这一 BST 不变量做正确性检验参考 main.c 的测试输出延伸关联树节点结构、递归框架与遍历细节见 7 二叉树.mdBST 插入、删除的完整工程实现见 二叉查找树.mdBST 验证、搜索、插入、删除的面试变体见 7.5 二叉搜索树.md。掌握上述方法后面对建树类题目即可快速定位属于哪种模式是有序数据 → 平衡 BST还是遍历序列 → 恢复树抑或文件存储 → 反序列化然后套用对应框架在十分钟内写出可运行代码。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐Learn-Algorithms 树专题二叉树、BST、AVL、红黑树、B 树、Trie、堆与 Huffman 全解析Learn Algorithms 树专题二叉树、BST、AVL、红黑树、B 树、Trie、堆与 Huffman 全解析 本文以 Learn Algorithm教程Arnis 完整指南把真实地理数据 1:1 转换成 Minecraft 世界Arnis 完整指南把真实地理数据 1:1 转换成 Minecraft 世界 Arnis 是一款免费开源的地理数据转 Minecraft 工具读取 Open桌面应用游戏开发GISTalkGo 算法之美有序数组转二叉搜索树与不同的二叉搜索树 II——树的构造专题实战TalkGo 算法之美有序数组转二叉搜索树与不同的二叉搜索树 II——树的构造专题实战 本文基于 TalkGoGo 夜读开源社区 content/algo文档教程上一篇鸣潮自动化工具终极指南5分钟解放双手的完整解决方案下一篇FastAPI 混合接收文件与表单字段在同一请求中使用 File 和 Form创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考