前四章线性表、栈、队列、串学完大多数人还能靠画图硬撑。到了第五章树和二叉树突然就懵了——不是不会写代码是根本不知道递归在脑子里怎么转起来的。我当年学严蔚敏这本《数据结构C语言版 第2版》的时候第五章课后题刷了三遍才彻底通透第一遍基本是看着答案抄抄完还是不会自己推。这篇就把第五章课后习题里最核心的题型全部过一遍概念题讲清逻辑算法题给完整可运行的C语言代码每道题都拆到不能再拆。适合正在期末复习、考研刷题、或者自学卡在二叉树这章的人。1. 别急着翻答案第五章的知识框架得先立起来课后习题看着多实际上就考三块树和二叉树的基本概念、二叉树的存储与遍历、哈夫曼树及其应用。绝大多数题目都是在这三个范围内变着花样出。做题之前把这几个底层问题想明白后面的答案就不是背出来的是推出来的。1.1 树和二叉树不是一回事这是第一道送命题教材里树的定义是n个结点的有限集n0时是空树非空树有且仅有一个根节点其余结点分成m个互不相交的有限集每个集合本身又是一棵树。注意互不相交这四个字这就是树这种结构没有回路的原因。二叉树则要求每个结点至多有两棵子树且子树有左右之分次序不能颠倒。很多同学记了二叉树就是度为2的树这是错的。度为2的树不区分左右子树而二叉树必须区分哪怕只有一个孩子也要说清楚是左孩子还是右孩子。这个区别直接决定了后面遍历序列的推导方式。课后有一道经典题画出3个结点的树和3个结点的二叉树的所有不同形态。树的形态只有两种——一种是A下面挂着B和C另一种是A下面挂着B、B下面挂着C。但二叉树的形态有五种空树不算根节点固定后左右子树分配的情况包括左子树为空右子树两个结点链式、左子树两个结点链式右子树为空、左子树一个结点右子树一个结点、左子树为空右子树两个结点呈V型、左子树两个结点呈V型右子树为空。这道题的考点就是让你理解左右有序到底改变了什么。1.2 二叉树的五个性质重点不是背而是推导性质1说第i层最多有2^(i-1)个结点这个用归纳法很容易想通。性质2说深度为k的二叉树最多有2^k - 1个结点就是把每一层最大值加起来。真正需要下功夫的是性质3对任何一棵二叉树叶子结点数n0等于度为2的结点数n2加1。证明思路是总结点数n n0 n1 n2其中n1是度为1的结点。同时从边的角度看每个结点除了根都有一条边连到父结点所以边数 n - 1。而边数又等于所有结点的度之和也就是n1 2n2。于是n - 1 n1 2n2代入n n0 n1 n2就能推出n0 n2 1。这个结论在选择题里反复考比如已知一棵二叉树有100个度为2的结点求叶子结点数直接用n0 n2 1 101。性质4和完全二叉树相关n个结点的完全二叉树深度为⌊log2 n⌋ 1。性质5给出了双亲和孩子结点的编号关系编号为i的结点左孩子是2i右孩子是2i1双亲是⌊i/2⌋。这两条性质是顺序存储结构的基础也是堆排序的前置知识现在不搞懂后面学到第八章排序再回头补就晚了。1.3 存储结构怎么选决定了你的代码怎么写二叉树的顺序存储就是用数组按下标关系存放对完全二叉树很友好但遇到普通二叉树就会浪费大量空间——比如一个深度为4只有5个结点的斜树用数组得开15个位置。所以教材里最常用的是二叉链表存储每个结点三个域数据域加左右孩子指针。如果需要找父结点就再加一个parent指针变成三叉链表。课后很多算法题都默认采用二叉链表因为递归在这种结构下写起来最自然。定义代码就这几行后面所有算法都在这个结构上展开typedef struct BiTNode { char data; // 数据域考试题一般用char struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;2. 概念复习题逐题解析把每道题的“考点”挖出来概念题在考试里占的分不高但它是算法设计题的地基。下面这几道是第五章课后题里出现频率最高的基本每一届学生都会做到。2.1 树的结点数问题最大深度和最小深度题目一般这样出含有n个结点的树最大深度是多少最小深度是多少答案分别是n和2——n个结点排成一条链就是最大深度n如果根节点下面挂着n-1个孩子深度就是2。如果限定是二叉树最小深度就是⌊log2 n⌋ 1。这类题就是考你对树形态的想象力没有别的技巧。如果是k叉树问最大和最小深度思路也一样。最大深度还是一棵链n。最小深度就是让每一层尽量满深度H满足(k^H - 1)/(k - 1) ≥ n取最小的整数H。这里要注意n和k的边界条件考试经常在深度为H的满k叉树有多少个结点这个点上设坑。2.2 满二叉树和完全二叉树的辨析满二叉树是每一层都满的二叉树深度为k时结点数是2^k - 1。完全二叉树是从上到下、从左到右连续编号结点位置和满二叉树编号一一对应。满二叉树一定是完全二叉树反过来不一定成立。课后题里常见考法给出一个完全二叉树的结点数n让你判断某个结点是不是叶子。比如n14问编号为12的结点有没有左孩子。用性质5算12的左孩子是24超出n的范围所以12没有左孩子。这类题只要把性质5的下标关系用熟基本就是秒杀。2.3 遍历序列能否唯一确定一棵二叉树这是一个高频概念题已知前序序列和中序序列可以唯一确定二叉树已知后序序列和中序序列也可以唯一确定但已知前序和后序不能唯一确定。原因是前序的第一个结点是根后序的最后一个结点是根但根之后左右子树怎么切分前序和后序提供不了足够的信息。有一个非常经典的例子前序AB、后序BA这棵树既可以是A的左孩子是B也可以是A的右孩子是B。所以看到前序后序能确定二叉树这种说法直接打叉。这个知识点在选择题里几乎每年都出现在算法题里则表现为给出前序和中序遍历序列要求输出后序遍历这类题目。2.4 线索二叉树为什么需要它线索二叉树这节内容很多同学觉得鸡肋认为考试不会考。实际上它经常以简答题或小题出现。核心问题是二叉链表里每个结点有两个指针但n个结点只有n-1条边所以有2n - (n-1) n1个指针是空的。这些空指针闲着也是闲着不如利用起来指向遍历序列的前驱和后继。教材里对每个结点增加了两个标志位ltag和rtag0表示指向孩子1表示指向前驱或后继。这样就实现了从任意结点出发快速找到它在某种遍历顺序下的前驱和后继不需要每次都从根开始重新遍历。课后题常让你画出给定二叉树的中序线索树或者在代码里实现线索化——这个本质上就是在中序遍历过程中把空指针改成线索写的时候注意记录上一个访问的结点就可以了。3. 二叉树算法设计题递归代码怎么一步步推出来第五章课后算法题最少有十几道但核心方法就是递归。很多同学的问题是递归的代码背得滚瓜烂熟换个题目就不会了。原因在于没有理解递归函数有一个返回值或者一个明确的终止条件每个递归调用都在解决一个规模更小的同类问题这个本质。下面把几道必考题目逐一拆解。3.1 统计二叉树结点个数、叶子结点数、深度这三道题是递归入门的三板斧代码结构非常相似。统计结点总数int NodeCount(BiTree T) { if (T NULL) { return 0; } return NodeCount(T-lchild) NodeCount(T-rchild) 1; }函数的逻辑只有一句话一棵树的结点总数 左子树结点数 右子树结点数 根节点自己。递归终止条件是空树返回0。这个1是根节点自己的计数千万别漏。统计叶子结点数就把根节点自己的判断改成如果左孩子右孩子都为空返回1int LeafCount(BiTree T) { if (T NULL) { return 0; } if (T-lchild NULL T-rchild NULL) { return 1; } return LeafCount(T-lchild) LeafCount(T-rchild); }求深度稍微变一点需要在左右子树深度里取较大值int Depth(BiTree T) { if (T NULL) { return 0; } int leftDepth Depth(T-lchild); int rightDepth Depth(T-rchild); return leftDepth rightDepth ? leftDepth 1 : rightDepth 1; }写这三道题的时候有个很容易犯的错在递归调用里反复计算同一个子树的结果比如Depth函数里写成return Depth(T-lchild) Depth(T-rchild) ? Depth(T-lchild) 1 : Depth(T-rchild) 1;。这个写法功能上没错但每个子树都被递归了两遍效率直接翻倍下降。在二叉树这种指数级扩展的结构里这种写法遇到稍微大一点的树就会明显卡顿。正确做法是先用变量保存左右子树深度再比较。3.2 交换二叉树每个结点的左右子树这道题考察的是在遍历过程中对结点进行操作的能力。思路是如果T为空直接返回否则交换T的左右孩子然后递归交换左子树和右子树。代码void SwapSubtree(BiTree T) { if (T NULL) { return; } BiTNode *temp T-lchild; T-lchild T-rchild; T-rchild temp; SwapSubtree(T-lchild); SwapSubtree(T-rchild); }注意这个函数的返回值是void因为它修改的是树本身的结构不需要向上一层返回任何值。这也是递归函数的一个分类标准有的递归是带返回值向上汇总比如统计类有的是原地修改后向下传递比如交换类。把这两类分清楚遇到新题就不会懵。3.3 层次遍历递归思路变成队列思路层次遍历和前中后序遍历有一个本质区别它没法直接用递归写硬要写也能写但要维护层次信息非常别扭。层次遍历的正确打开方式是借助队列。教材里标准的做法是void LevelOrder(BiTree T) { if (T NULL) { return; } InitQueue(Q); // 初始化队列队列元素类型是 BiTree EnQueue(Q, T); // 根节点入队 while (!QueueEmpty(Q)) { DeQueue(Q, p); // 出队一个结点 visit(p-data); // 访问它 if (p-lchild ! NULL) { EnQueue(Q, p-lchild); } if (p-rchild ! NULL) { EnQueue(Q, p-rchild); } } }这个算法的思想可以类比成广播扩散根节点先进入处理队列然后处理它的时候把它的孩子登记到队列末尾队列先进先出天然保证同一层的结点会比下一层的结点先被访问。很多同学第一次写的时候会忘记判断孩子是否为NULL结果把空指针入队后面访问的时候就崩了。如果考试要求手写队列的实现不需要写完整的循环队列只要把EnQueue、DeQueue、QueueEmpty这几个操作抽象出来说明它们的功能评分标准通常也认可。但如果是在机器上跑就老老实实实现一个简单的顺序队列。3.4 用先序遍历序列建树输入格式的坑教材上的建立二叉树算法用的是先序遍历输入序列中#表示空指针。比如输入ABD#G##E##C#F##就能建立起一棵二叉树。代码逻辑是void CreateBiTree(BiTree T) { char ch; scanf(%c, ch); if (ch #) { T NULL; } else { T (BiTNode *)malloc(sizeof(BiTNode)); T-data ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); } }这里有一个大坑教材用的是C的引用写法BiTree T因为函数内部需要修改指针T本身的值让它指向新分配的结点或者NULL。如果你在纯C环境下编译这种写法会报错。改成二级指针void CreateBiTree(BiTree *T) { char ch; scanf(%c, ch); if (ch #) { *T NULL; } else { *T (BiTNode *)malloc(sizeof(BiTNode)); (*T)-data ch; CreateBiTree((*T)-lchild); CreateBiTree((*T)-rchild); } }还有一个容易出问题的点是输入缓冲区的换行符。如果前面调用过scanf读入其他数据缓冲区里可能残留一个\n导致scanf(%c, ch)读到的是换行符而不是期望的字母。解法是用scanf( %c, ch)在%c前面加一个空格跳过空白字符或者在建树之前用getchar()清掉换行。这个坑我在调试的时候至少卡了半小时后面每次写都条件反射式地在%c前面加空格。3.5 非递归中序遍历用栈模拟递归过程递归遍历虽然好写但系统递归栈的深度是有限的树很深的时候容易爆栈。所以教材里专门安排了非递归遍历的算法中序是最常考的。核心思路是用显式栈模拟沿左子树一路入栈走到空然后出栈访问再转向右子树的过程void InOrderTraversal(BiTree T) { InitStack(S); BiTree p T; while (p ! NULL || !StackEmpty(S)) { if (p ! NULL) { Push(S, p); p p-lchild; } else { Pop(S, p); visit(p-data); p p-rchild; } } }理解这段代码的关键点在于第一次进入while循环p是根节点会沿着左孩子一路入栈直到p变成NULL然后进入else分支弹出栈顶结点访问再转向它的右子树。如果右子树非空又会重复入栈其左链如果右子树为空p还是NULL继续弹栈。这个过程和递归版本的中序遍历完全等价只是把系统栈换成了手动栈。前序非递归遍历可以在这个基础上改成入栈时访问但要注意出栈顺序。后序非递归遍历是最麻烦的需要额外记录结点是否已经访问过右子树教材里通常用双栈法或者加一个标志位。如果时间紧后序非递归可以适当放一放考研初试考它的概率远低于前序和中序。3.6 判断两棵二叉树是否相似相似的定义是两个树都为空或者它们的左右子树分别相似。这个递归定义本身就是天然的算法描述int Similar(BiTree T1, BiTree T2) { if (T1 NULL T2 NULL) { return 1; } if (T1 ! NULL T2 ! NULL) { return Similar(T1-lchild, T2-lchild) Similar(T1-rchild, T2-rchild); } return 0; }很多同学分不清相似和相等的区别。相等要求结点数据也一样相似只要求结构一样。所以Similar函数里不需要比较data域。这种名字差一个字代码差一行的题目特别适合用来检验自己有没有真正理解递归。类似衍生题还包括求二叉树中值为x的结点的所有祖先、删除以某个结点为根的子树、求二叉树中相距最远的两个结点之间的距离。这些题都是在基础递归上叠加额外的判断条件基础打牢了自然能推出来。4. 哈夫曼树与哈夫曼编码搞清楚构造过程比背结论有用哈夫曼树在第五章里占的篇幅不大考试却非常喜欢出。概念题常考什么叫带权路径长度大题常考手动构造哈夫曼树并写出编码。4.1 带权路径长度WPL的计算在一棵树中从根节点到某个叶子结点的路径长度就是经过的边数。带权路径长度就是叶子结点的权值乘上它的路径长度把所有叶子加起来。哈夫曼树就是使WPL最小的二叉树也叫最优二叉树。构造哈夫曼树的步骤教材上写得比较抽象我用自己的话说把所有带权结点放进一个集合每次挑出权值最小的两个结点合并成一个新结点新结点的权值是两者之和它的左右孩子就是这两个结点把新结点放回集合继续重复直到集合里只剩一个结点。这个每次挑最小的两个就是贪心策略。实际操作的时候用一个小规模例子讲最清楚。假设五个字符的权值分别是 a:2, b:3, c:6, d:8, e:10。第一步挑最小的2和3合成新结点5左右孩子是a和b。集合变成5, 6, 8, 10。 第二步挑最小的5和6合成11。集合变成8, 10, 11。 第三步挑8和10合成18。集合变成11, 18。 第四步挑11和18合成29。树构造完成。WPL计算有两种方式。第一种用定义a的路径长度是3b的路径长度是3c的路径长度是2d和e的路径长度都是2。所以WPL 2×3 3×3 6×2 8×2 10×2 6 9 12 16 20 63。第二种方式更巧妙所有非叶子结点的权值之和就是WPL。这个树的非叶子结点权值是5、11、18、29加起来5111829也是63。用第二种方式算能快很多尤其在考试时间紧张的时候。4.2 哈夫曼编码的生成规则哈夫曼编码就是在哈夫曼树的每条左分支上标0右分支上标1反过来也可以只要保持一致从根到叶子路径上经过的0和1串起来就是该字符的编码。上面这个例子按左0右1的规则d的路径是从根29走右孩子18再走左孩子8所以编码是10。 e的编码是11。 c的编码是01。 a的编码是000。 b的编码是001。哈夫曼编码是前缀编码任何一个字符的编码都不是另一个字符编码的前缀所以解码的时候不会产生歧义。这也是哈夫曼编码能无损压缩的底层原因。考试经常让你比较定长编码和哈夫曼编码的总长度定长编码5个字符每个需要3位5个字符共需(236810)×3 87位哈夫曼编码总共需要2×3 3×3 6×2 8×2 10×2 63位压缩率大概是27.6%。4.3 哈夫曼编码的C语言实现思路课后算法题如果要求实现哈夫曼编码一般会先定义静态三叉链表存储结构因为构造过程中需要不断找父结点。教材里用三个数组存放weight、parent、lchild、rchild。实现的核心是不断扫描选出权值最小且parent为0的两个结点合并后更新数组。这个代码比较长但思路不复杂——本质上就是把上面手动构造的步骤翻译成数组操作。我在写这段代码时有个体会优先用数组存树而不是指针链表因为哈夫曼树的构造过程需要频繁访问父结点和兄弟结点数组的随机访问能力比指针方便太多。如果用链式结构每次合并都要额外维护父指针代码量直接翻倍。这也是一个选择数据结构的实际案例不是所有树都用链表存得看操作需求。5. 从“看懂答案”到“会写代码”第五章最容易踩的坑课后题答案看一遍觉得都懂合上书自己写就卡壳这种情况太常见了。我在做第五章题目的时候踩过不少坑有些甚至是写完代码编译器报错才发现的。这里整理几个高发问题。5.1 递归出口丢了栈直接溢出写递归函数的第一行就应该是终止条件判断但很多同学写的时候习惯先写递归调用最后才补终止条件。比如统计叶子结点数如果忘了写空树返回0这个出口递归到空指针时还会继续往下访问T-lchild直接对空指针解引用程序崩溃。我的经验是任何二叉树递归函数先问自己三个问题——空树时返回什么当前结点是叶子时做什么当前结点不是叶子时怎么分解把这三个问题的答案写成代码函数框架就稳了。5.2 教材的引用传参C语言编译器认不了严蔚敏教材是用类C语言写的很多地方用了C的引用符号。比如建树函数CreateBiTree(BiTree T)你在纯C环境里原样抄进去编译器会报错。解决办法有两个要么用二级指针要么把文件后缀改成.cpp用C编译器编译。考研手写代码的时候建议写成二级指针形式因为有些院校的考试环境默认就是C。这个细节看起来小但考试的时候写错可能整道题都不得分。5.3 建树时输入序列理解偏了先序遍历建树要求输入序列必须是带空标记的先序序列比如ABD#G##E##C#F##。很多同学对着这个序列想当然地认为是层序结果建出来的树完全不对。判断方法很简单你依次读入字符如果当前读的不是#就先建立结点、再递归建立左子树、再递归建立右子树。也就是说序列的顺序必须是根、左子树、右子树层层展开的顺序不是一行一行从左到右的顺序。如果一个字符序列让你分不清是哪种遍历就自己模拟一下建树过程看能不能唯一还原出一棵树。5.4 层次遍历的队列忘记初始化层次遍历看起来简单代码也不长但漏掉InitQueue(Q)这一步导致程序崩溃的人不在少数。很多教材把InitQueue放在ADT定义里不单独强调初学者就以为直接声明一个队列变量就能用。在C语言里未初始化的队列rear和front是随机值入队出队直接野指针操作。这个错误特别隐蔽因为编译不会报警运行结果也是时好时坏——数组恰好初始化为0的时候就正常换个平台就崩。5.5 一个自测清单做完一道二叉树算法题我建议至少检查这几个点空树能不能正常返回只有一个根节点的树能不能正确处理左斜树和右斜树所有结点都只有左孩子或右孩子会不会出现递归过深或死循环完全二叉树能不能得到预期结果把这些边界情况在纸上走一遍比反复看答案要有效得多。很多同学做题只测正常情况遇到空树这种边界直接露馅考试就是在这些地方拉开差距的。6. 最后分享两个我刷第五章习题时的实践技巧第一个技巧是画递归展开图。刚开始想不通递归是怎么执行的就在纸上画出递归调用的完整路径比如求深度这个函数遇到叶子结点时返回什么回溯到上一层时变量值变成什么。画过两三次之后递归就不再是黑魔法了而是变成了一种可以预测的执行过程。这个习惯到现在我刷LeetCode写二叉树相关题目时还在用只是从纸上画画变成了在脑子里模拟。第二个技巧是把代码跑起来看输出。看答案和自己写代码是两回事自己写代码和跑出正确结果又是两回事。我在学第五章的时候把书上所有算法的C语言版本都实现了一遍用几个不同的二叉树作为输入把前序、中序、后序、层序的遍历结果打出来对比。这个过程帮我发现了很多自以为懂了但实际上没懂的地方。如果有同学手头有DEV-C或者VS Code配好了C环境建议也做一遍这个练习。数据结构这门课动手写和动手画永远比盯着教材看管用。