企业官网建设流程全解析

很多人倒是没怕过链表，但是一翻到《数据结构（C语言）第二版》第六章就开始头皮发麻。这一章讲的是树和二叉树，我当年复习到这儿的时候，直接翻课后答案，结果发现自己连答案都看不懂——不是不会写代码，而是根本没抓住这一章的思维方式。后来我总结了一句话：第六章不是在考你写代码，而是在考你有没有建立递归思维。这一章是整本书真正的分水岭，前面的线性表、栈、队列都是“一条道走到黑”的结构，树一出来就变成了“一分为二、再一分为二”的分支结构，很多人的数据结构之旅就是在这里开始掉队的。

这篇文章我打算按我自己复习时的思路来写：先拆解这一章到底在讲什么，再讲代码里那些最核心的存储结构和遍历套路，然后把课后习题按题型拆开，逐个说清楚解题路径，最后把那些容易踩的坑和调试技巧一次讲完。不管你是在准备期末考试、考研，还是想补一补数据结构的地基，这篇文章都能让你少走不少弯路。

1. 第六章到底在讲什么

1.1 为什么无数人倒在第六章门口

我见过太多同学，前面链表、栈、队列的代码都打得挺溜，一进第六章往前五章的内容就开始“断片”。原因不复杂：前五章是线性结构，逻辑上一个接一个排成一队，你顺着指针往下走就行；但树这种结构，同一个结点可能有两个后继，第一次接触就会觉得“这还能叫线性？这我脑子里画不出来”。

其实第六章的课后答案难懂，不是因为答案本身写得晦涩，而是你缺少一棵“脑内二叉树”。很多题目，比如“已知先序序列和中序序列求二叉树”“写一个递归算法求二叉树的高度”，你看答案解析的时候，它默认你已经能够把递归过程在脑子里跑一遍。如果你没有这个能力，看答案等于看天书。

所以我的第一个建议是：别急着看答案，先对着题目把图画出来。树的所有课后题，本质上都可以还原成一张图，图对了，代码就是照着图翻译。

1.2 本章知识地图与前后章节衔接

第六章的知识点排列是有逻辑的，不是随便把一堆概念堆在一起。先讲树的定义和基本术语（树的度、结点的层次、深度、森林这些），然后马上收紧到二叉树——因为二叉树是树结构里最规整、最适合用计算机处理的形式。接着讲二叉树的存储结构和遍历方式，这是整章的绝对核心。遍历之后是线索二叉树，再往后是树与森林的转换，最后压轴的是霍夫曼树与霍夫曼编码。

这一章跟前后章节的关联也很紧。你在学后面的图的时候会发现，图的DFS和BFS跟二叉树先序、层序遍历的思路一脉相承；排序里的堆排序，直接就是用二叉树表示的；甚至第五章你学的递归栈调用过程，在这一章的遍历算法里会反过来帮你理解递归。所以我会说，第六章不是一座孤岛，它是你从“会写线性结构的程序”向“能读懂复杂递归算法”跨越的桥梁。

1.3 学习方法：先画图，再写码

我自己的学习路径是这样的：拿到一个概念，比如“中序遍历”，先找一棵小树手动走一遍，再把这个过程翻译成代码。中序遍历的输出顺序是“左子树、根、右子树”，那我在一棵树上标出访问顺序：最左下角那个结点先输出，然后它的父结点、父结点的右子树……一遍走完你自然就明白，为什么代码长得像那三行递归调用。

画图这一步省不得。看十遍别人画的图，不如自己动手画一遍，尤其是树的旋转、树的转换这类题目，不画图真的寸步难行。后面我在讲题型的时候会演示这个思路，你按我的方法来，很快就能把“脑内二叉树”装进脑子里。

2. 核心代码与存储结构解析

2.1 二叉树的存储结构为什么长这样

课本里二叉树结点的标准定义是这样的：

typedef struct BiTNode { int data; // 数据域 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;

有人可能会问，为什么不用数组存？顺序存储确实存在，它适合完全二叉树，下标i的左孩子是2i，右孩子是2i+1。但普通二叉树用数组存会浪费大量空间，所以课本默认都用链式存储。

注意这里有个细节，结构体里自己指自己，叫“递归定义”。这个“递归”是整个第六章的底色——树是递归定义的，树的问题就天然适合递归求解。你用C语言写数据结构的代码，最大的好处就是指针操作直观，你能清清楚楚看到每一个结点的“线”是怎么连到下一个结点的。很多同学用其他语言写树写不明白，就是因为语言层面把指针藏起来了，你反而看不到结构了。

2.2 三种遍历的递归套路

二叉树的先序、中序、后序遍历，代码长得几乎一模一样，区别只有printf的位置：

void PreOrder(BiTree T) { if (T != NULL) { printf("%d ", T->data); // 先访问根 PreOrder(T->lchild); // 再遍历左子树 PreOrder(T->rchild); // 最后遍历右子树 } } void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); // 先遍历左子树 printf("%d ", T->data); // 再访问根 InOrder(T->rchild); // 最后遍历右子树 } } void PostOrder(BiTree T) { if (T != NULL) { PostOrder(T->lchild); // 先遍历左子树 PostOrder(T->rchild); // 再遍历右子树 printf("%d ", T->data); // 最后访问根 } }

我的经验是把这三种遍历放到一起背：根的输出位置决定了它是先序、中序还是后序。代码整体上就是“递归出口（NULL直接返回）+ 递归操作（访问、递归左、递归右）”，先左后右是约定，几乎不会例外。考试如果考非递归版本，那就需要借助栈来模拟递归过程，这个我建议等递归版写得滚瓜烂熟之后再去研究。

2.3 线索二叉树：多两个标记位就多了前驱后继

线索二叉树刚看的时候会觉得是个“邪门”结构，好好的指针不用，偏要把空指针利用起来。它的核心思路是：二叉树遍历完会得到一个线性序列，比如中序遍历序列，每个结点在这个序列里都有前驱和后继，但二叉链表只存了父子关系，没法直接找到“中序前驱”。那就用空闲的lchild或rchild指针，去指向这种前驱或后继。

代码上结点的定义多出两个标记：

typedef struct ThreadNode { int data; struct ThreadNode *lchild, *rchild; int ltag, rtag; // 0表示指向孩子，1表示指向前驱/后继 } ThreadNode, *ThreadTree;

判断规则很简单：ltag为0，lchild指向左孩子；ltag为1，lchild指向前驱。rtag同理，1就表示rchild指向后继。写中序线索化的过程，核心是拿一个pre指针记住“刚刚访问过的结点”，然后把当前结点左孩子为空时挂到pre上，pre右孩子为空时挂到当前结点上。这个pre指针的更新经常被漏掉，我见过太多人写线索化写到一半就把pre给丢了，输出结果完全不对。课后题里“写出中序线索二叉树”这类题，画图的时候注意把所有空指针按规则补上线，千万别漏。

2.4 霍夫曼编码的构建过程

第六章最后一个大块是霍夫曼树，这个知识点考试特别爱考，因为它跟“编码”“压缩”这种现实应用直接挂钩。构建规则不复杂：每次从集合中取出两个权值最小的结点，合并成一个新结点，权值相加，放回集合，不断重复直到只剩一个根。

这里有个小技巧，我当初一直绕不明白——WPL（带权路径长度）的计算。后来发现两个办法都行：一个是把每个叶子结点的权值乘上它的路径长度再加起来；另一个更省事——每合并一次，就把合并出的新权值累加一次，加到最后就是WPL。我自己验证过几组数据，两个方法结果完全一致。写课后题的时候用累加合并值的方法，既快又不容易错。

3. 经典课后题的拆解与通用解题路径

3.1 遇到一道树题，先走这五步

我复习的时候给自己定了一套流程，跑完五步再对答案，基本不会错：

第一步，读题，把题干里所有跟“顺序”“层次”“结点个数”“叶子”相关的词圈出来。这些词直接决定用哪个性质、哪种遍历。

第二步，画图。哪怕题目没要求画，我也在草稿纸上画一棵树来验证想法。比如让你数“深度为k的二叉树最多有多少个结点”，你就画一个深度2、深度3的满二叉树来试，公式就出来了。

第三步，套定义。树的度、高度、层次这些概念，每个对应一个计算公式，别靠感觉。

第四步，写递归三要素：递归出口、递归操作、递归调用。这一步是最容易出错的，因为出口写错了整个函数就废了。

第五步，拿一个小规模例子手算验证。比如你写了一个求叶子数的递归函数，就造一棵只有三个结点的树跑一遍，看结果是不是2。

3.2 题型一：由遍历序列还原二叉树

这类题几乎每年必考。经典问法是“已知某二叉树的先序遍历序列为ABDCEF，中序遍历序列为DBAECF，请画出这棵二叉树”。

我的解体思路是这样：先序序列的第一个字符是A，说明根是A。回到中序序列里找A，A在中间，左边DB就是A的左子树中序序列，右边ECF就是A的右子树中序序列。接着再看先序序列里DB在A后面的顺序，B是D的前面，说明A的左孩子是B；D在B的前面，说明D是B的左孩子。右边同理，C是A的右孩子，E、F分别是C的左右孩子。整个过程就是不断用“先序定根，中序分左右”来递归切分。

很多人卡在这一类题，是因为没有意识到这是一个递归过程。你只需要每次回到中序序列里找到根的位置，然后左右一劈，剩下的工作就是重复同样的事。画图时建议用彩色笔先把根标出来，再把左右子树用括号框住，层次感一下子就出来了。

3.3 题型二：递归算法的设计与填空

第六章课后题后半部分基本都是“设计递归算法实现xxx”，比如求二叉树的高度、统计叶子结点个数、交换所有左右子树。这类题目是填空题高分区，也是我推荐你优先掌握的题，因为套路极其固定。

以“统计叶子结点个数”为例，递归出口和递归操作的关系是这样的：

int CountLeaf(BiTree T) { if (T == NULL) return 0; if (T->lchild == NULL && T->rchild == NULL) return 1; return CountLeaf(T->lchild) + CountLeaf(T->rchild); }

看着简单对吧？但很容易漏第二个出口——如果不写“左右都空返回1”，程序就会继续往下递归，然后空指针直接访问崩溃。求二叉树的深度也类似，出口是空树返回0，递归操作是返回左右子树深度的较大者加1。

这类题的通用框架就是用递归出口保底、用递归调用把问题缩小、再用返回值把子问题合并。写多了你会发现，绝大多数“求xx”的树算法都长一个样，只是中间那一行的递归操作不同。

3.4 题型三：树与二叉树的转换、WPL计算

树与二叉树的转换，口诀就六个字：“左孩子，右兄弟”。把一棵普通树转换成二叉树时，每个结点的第一个孩子保留为左孩子，其他孩子变成右兄弟链。反过来，从二叉树还原树，就是把右链上的一串结点都拉回成原树的兄弟。课后答案里很多图示题，只要你记住“先画左链再画右链”这一步，基本能拿全分。

霍夫曼编码的题就更直白了，会构造霍夫曼树就会算。比如权值集合{5, 29, 7, 8, 14, 23, 3, 11}，先排出两个最小权值3和5，合并成8，注意这个8跟原来的8可能是同权的，取哪个都行，结果会略有不同但WPL不变。然后接着取7和8合并成15，再把8和11合并成19……重复下去最后得到一棵树。编码时左分支写0、右分支写1，从根到叶子的路径就是该叶子字符的编码。WPL我再强调一次，用累加合并值的方法，比对着图一层层数叶子要快得多，也不容易出错。

4. 调试技巧与常见问题排查实录

4.1 用“前序+#空标记”建树，把调试时间省下来

写二叉树代码的人，百分之八九十都经历过“程序一跑就崩”的绝望。问题往往出在建树上——你不是没有树可以遍历，而是不知道该怎么手工建一棵能用来调试的树。我自己常用的办法是按扩展的先序序列建树，用#表示空指针。比如输入ABD##E##C##，就能得到一棵确定的二叉树。

BiTree CreateTree() { BiTree T; char ch; scanf(" %c", &ch); if (ch == '#') T = NULL; else { T = (BiTNode *)malloc(sizeof(BiTNode)); T->data = ch; T->lchild = CreateTree(); T->rchild = CreateTree(); } return T; }

这个函数写一次，整个第六章的调试都能用。每次写完遍历或者递归函数，就用这棵树跑，输出序列一看，立刻知道代码对不对。比你在那凭空脑补一个树然后猜程序行为要靠谱一万倍。

4.2 排查实录：那些让我卡壳半天的典型问题

第一个高频故障是段错误。十次里有八次是因为没有判空就直接访问结点成员。比如递归求高度时，你写了return TreeDepth(T->lchild) + 1，但没判断T本身是不是NULL，递归到叶子下面就直接崩。解决办法就是所有指针操作之前，先想想这一层可能传进来的值。

第二个高频故障是遍历输出和预期不符。我印象最深的一次是交换左右子树的递归题，我写完一跑，输出结果跟答案相反，排查了半天才发现是递归里没有用临时变量存左孩子，直接把左孩子先改了，右孩子再赋值时拿到的已经是改过的结点。交换操作一定要先把T->lchild存到temp里，再做后续操作。

第三个坑是递归里的返回值位置。像“求第k层结点个数”这种题，经常有人把递归调用写在if外面，导致空树也继续递归，栈溢出。想要避开这些坑，没有捷径，只能靠多写、多跑、多对比输出。

4.3 常考易错点速查表

这张表我建议你贴在手边。考试之前扫一遍，比临时抱佛脚看整章书效率高很多。

5. 课后答案的正确打开方式

5.1 看答案前，先给自己写个“解题说明”

以前我也犯过这个毛病：题目不会做，直接翻答案，看完觉得自己会了，合上书再碰到同类型的题还是不会。后来我改了一个习惯——看答案之前，先拿张纸写下“我卡在哪儿了”，比如“我不知道怎么从遍历序列里确定根的位置”，然后带着这个问题去看答案。这样你会发现答案里那几步正好解决你的卡壳点，印象会深得多。

课后答案的正确用法是“对答案”，不是“抄答案”。每道题先自己写一遍，再对照答案看思路是否一致。如果不一样，看一看答案的思路是不是更简洁，并想想为什么。这个过程花的时间比直接抄答案多，但收获也是成倍的。

5.2 一题多解与考研题对照

第六章的很多题，解的路径不止一条。比如“求二叉树的高度”，你可以用递归，也可以用层次遍历数层数；比如“判断一棵树是不是平衡二叉树”，你可以自顶向下递归，也可以自底向上一次性判断。不是让你每道题都写出五种解法，而是做课后题时留个心眼：这道题除了我的做法，课本或答案有没有更简洁的思路？如果有，把它记在题旁边。

另外，我强烈建议把这一章的课后题跟考研真题对照着看。很多学校的期末题、考研题，就是把课后题改个数字、改个问法重新端上来。你做课后题时掌握的方法，到考场上就是你的武器库。

5.3 不懂的知识点怎么巩固

如果这一章里某个概念实在想不通，比如线索二叉树，光看书没用，我建议找几篇带动态演示的教学视频看，或者自己用卡片模拟一遍线索化过程：把中序遍历序列写出来，再一个个去连线索，连完再对照课本图，很快就会豁然开朗。数据结构这东西，抽象看永远晦涩，可视化之后瞬间就明白了。

还有一个小技巧：把你写过的代码用不同的输入样例多跑几次。比如写好了二叉树遍历，就多建几棵不同的树，把先序、中序、后序输出全部打印出来，看看它们之间的规律。自己在实验中发现的规律，比看十遍书都记得牢。

我个人复习第六章的最大体会，就是别怕递归。很多同学一看到递归就觉得“这函数调用自己，怎么可能会停”，其实你只要牢牢抓住两件事：出口和递归式。出口防止死循环，递归式负责把大问题变小问题。树的天然递归结构，让这个问题比线性结构还清晰。把第六章的课后题一道道亲手做完、亲手调试通过，你的递归思维就基本建立起来了，后面学图、学查找、学排序都会顺畅得多。

最后再分享一个我每次带新人都会强调的习惯：拿到题目先画一棵小树，哪怕只是三层，用它在纸上把过程走一遍。这个习惯帮我解决了好多“看似会做、一写就错”的难题。你把这个习惯带进第六章，课后答案里的每个字都会变得好懂很多。