1. 第六章到底在考什么——先把这章的底牌摸清1.1 从线性到非线性这一步到底难在哪很多朋友学到第六章就卡住了原因很简单前五章你接触的全是线性结构——顺序表、链表、栈、队列、串、数组逻辑关系是“一个接一个”脑子里画出来是一条线。到了第六章树和二叉树结构一下子变成了“一对多”一个节点下面挂着好几个孩子你不能再靠简单的“前驱后继”来理解数据之间的关系了。严蔚敏这本书的第六章标题叫“树和二叉树”是整本书真正的分水岭。这章学得扎不扎实直接决定你后面第七章“图”能不能听懂。因为图本质上就是“多对多”的关系而树就是图的特例。从树的遍历到图的遍历从二叉树的性质到图的连通性判断很多思路都是平移过去的。所以我建议你把第六章当成本书第一重点来对待不要抱着“先混过去后面再看”的心态。这章的核心考点其实就几块二叉树的性质与存储结构、二叉树的遍历先序中序后序层次、线索二叉树、树与森林的转换、哈夫曼树与哈夫曼编码。课后习题基本就围绕这些展开。你做题的时候会发现一个规律绝大多数算法题都离不开“递归”两个字。只要递归思维过关这章的大题你基本能拿下一半。1.2 章节主线二叉树的存储、遍历、线索化、树与森林、哈夫曼树我们先把这章的路线图理清楚。二叉树为什么单独拎出来讲因为树里面最规范、最好处理的就是二叉树每个节点最多俩孩子左子树右子树存储和遍历都好设计。普通的多叉树反而用得少做题时也经常“转成二叉树”再处理。书本先是给了二叉树的性质第i层最多有2的i-1次方个节点、深度为k的二叉树最多有2的k次方减1个节点、叶子节点数等于度为2的节点数加一等等。这些性质不是让你背的是用来做题的。比如有一类题给你前序序列和中序序列让你求后序序列你要是没吃透“前序第一个是根、中序根的左边是左子树”这个性质光靠背题是背不出来的。然后就是存储结构。顺序存储用数组适合完全二叉树下标从1开始的话左孩子是2i右孩子是2i1父节点是i/2取整这套关系后面线索化也用得上。链式存储就是最经典的二叉链表每个节点一个数据域两个指针域。考试和作业里90%的代码题都是基于二叉链表来写的所以这个结构体定义你得倒着都能敲出来typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;再往后是遍历。先序、中序、后序其实就是“根、左、右”三个元素的排列组合区别只是根什么时候访问。三种递归遍历代码长得几乎一样就一行printf的位置不同。麻烦的是非递归遍历要手动用栈模拟递归过程这个确实是新手重灾区。线索二叉树是这一章的进阶内容核心思想就是利用空指针域存前驱后继让遍历不用栈也能做。树与森林的转换讲的是孩子兄弟表示法把多叉树变成二叉树来处理。哈夫曼树则是贪心思想的第一次正式登场构建方法就一句话每次选权值最小的两个节点合并。很多同学在这块容易犯的错是——建树没问题但真让你写哈夫曼编码的代码就懵了这个后面我们会细讲。2. 做题之前必须建立的两个思维习惯2.1 递归思维把大问题拆成小问题第六章的算法题如果不用递归能做的题目少一半。递归这东西很多同学觉得难其实是没转过弯来。我给你打个比方递归就像你让一个班的人排队报数你问第一排的同学“你后面有几个人”他不知道但他可以问第二排的同学第二排也不知道就问第三排一直到最后一排他说“我后面0个人”然后这个答案一层一层传回来第一排就知道答案了。写递归函数就三步第一明确这个函数能干什么第二找到递归出口——也就是最简单的情况直接返回第三把大问题拆成小问题调用函数本身去解决。比如求二叉树深度你不需要想整棵树有多深你只需要想以当前节点为根的深度等于左子树深度和右子树深度中更大的那个再加一。如果当前节点是空的深度就是0。这就够了。很多同学写递归写不对其实不是因为不会递归而是函数设计没想清楚就开始写代码。我建议你每道递归题动手之前先在心里默念三遍这个函数的功能是什么输入是什么返回什么想清楚了再写框架。后面我们讲具体题目的时候你会看到这个流程有多重要。2.2 指针与结构体二叉树的“物理基础”第六章的代码题全是指针操作。很多同学前面学链表的时候指针就没吃透到二叉树这里就直接崩了。其实二叉树比链表“仁慈”的地方在于链表有时候还得处理头指针为空、循环链表的复杂情况二叉树的操作基本上就用两个指针——lchild和rchild翻来覆去就这俩。但有一个区别必须明确链表里你经常需要新增节点、删除节点所以会用到二重指针比如头指针本身要变。二叉树这里如果只是遍历、求深度、统计节点数这种只读操作直接传一级指针就行但如果是要在二叉树中做插入、删除、构建这样的修改操作往往就需要二级指针或者用一个返回指针的函数。举个例子很多同学喜欢这样写void createTree(BiTree T) { T (BiTree)malloc(sizeof(BiTNode)); }这个代码有问题传入的一级指针T是值传递函数内部给T赋了新地址但这个新地址传不回外部外部那个T还是NULL。这就是典型的“只改了副本没改原件”。正确做法是传二级指针或者写成返回值的形式BiTree createNode(int data) { BiTree p (BiTree)malloc(sizeof(BiTNode)); p-data data; p-lchild p-rchild NULL; return p; }这个坑在课后习题的建树题里经常出现。你要是发现运行的时候树总是空的不用怀疑八成就是这个问题。3. 按题型拆解课后习题的解题套路3.1 基础概念题背诵不是目的理解才是第六章课后习题的简答题部分一般会考你二叉树性质、完全二叉树的概念、二叉树的遍历序列推导、树转二叉树等。这一类题看着简单但特别容易丢分就是因为你以为自己背下来了其实没理解透换个角度问你就不会了。举个例子课后有一道很经典的题已知一棵二叉树的中序序列和后序序列要求画出这棵二叉树。解题思路不复杂——后序序列的最后一个元素是根节点用这个根节点去中序序列里切分左边是左子树中序序列右边是右子树中序序列然后按照序列长度在后序序列里也能切出左子树后序和右子树后序接着递归下去每次取后序子序列的最后一个作为子树的根。这里面最忌讳的就是凭空想象、一上来就在草稿纸上瞎填。我建议你画一个表格每次递归的根、左子树序列、右子树序列都列出来保证不会乱。平时练习养成这个习惯考试的时候就算紧张也能按流程推出来。类似的还有根据前序中序推二叉树、根据层序中序推二叉树套路都是同一个先找到根再用中序分左右。3.2 遍历类题目递归、非递归、层次遍历一网打尽遍历是第六章的核心中的核心课后习题里既有写遍历序列的题也有让你写遍历算法的题还有要求把非递归改写成递归、把递归改写成非递归的题。递归遍历代码只要你记住了那三行框架问题不大。真正拉开差距的是非递归遍历。很多同学背非递归先序的代码背完了转眼就忘。我推荐你用“模拟栈”的方式去理解而不是背。不管先序还是中序核心思路都是沿着左子树往下走把沿途经过的节点压栈走到左下角空了就弹栈输出然后往右子树走。区别在于什么时候输出。先序是“入栈前输出”中序是“弹栈后输出”。后序麻烦一点需要记录上一个访问的节点判断“右子树有没有访问过”才能决定当前节点能不能输出。你要是能把这三套非递归遍历代码自己推导出来而不是抄一遍这一章的理解就非常扎实了。层次遍历用的是队列思路更简单根入队出队一个节点就输出同时把它的左右孩子入队直到队列为空。课后习题里有一道“用层次遍历统计二叉树叶子节点个数”的题其实就是在出队的时候检查节点有没有孩子没有孩子就计数加一非常简单。3.3 算法设计题先把框架写出来再补细节第六章的算法设计题比如统计叶子节点数、求树的深度、交换左右子树、判断两棵树是否相等看起来各不相同但骨架都非常像——都是递归函数都是判断是否为空节点然后递归调用左右子树最后根据左右子树的结果决定返回值。很多同学拿到题目直接写代码写到一半发现不对又全部涂掉重来。我建议你换个策略动手前先把思路用伪代码写出来。伪代码不需要检查语法只需要你自己能看懂。比如“统计叶子节点”的思路是如果节点为空返回0 如果节点没有左孩子且没有右孩子返回1 否则返回 左子树的叶子数 右子树的叶子数这三行想清楚了C语言代码三分钟就能写出来。但如果你直接写代码很容易出现“忘记检查叶子节点”、“递归到NULL时报段错误”这类问题。这个做题习惯说实话比你多做二十道题都管用。考研的同学尤其注意阅卷老师看的是你的算法思路是否清晰代码是给思路服务的。4. 经典习题的代码实现与思路详解4.1 统计叶子节点、求高度这类“递归三板斧”我先挑几道课后高频习题把完整代码和思路走一遍你照着思路自己推一遍比干背十遍都有效。统计叶子节点数int countLeaves(BiTree T) { if (T NULL) { return 0; } if (T-lchild NULL T-rchild NULL) { return 1; } return countLeaves(T-lchild) countLeaves(T-rchild); }注意那个“空节点返回0”和“叶子节点返回1”两个出口顺序不能交换。你想想如果先判断叶子节点你传一个NULL进去访问T-lchild就段错误了。所以第一个判断必须是“如果是空节点就返回0”这是递归的兜底出口。求二叉树深度int getDepth(BiTree T) { if (T NULL) { return 0; } int leftDepth getDepth(T-lchild); int rightDepth getDepth(T-rchild); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }这个代码几乎是“背多分”题但你要理解为什么是取最大值加一。深度是根到最远叶子的路径长度当前节点深度等于它左右子树深度更大的那个再加上当前节点自己这一层。交换左右子树void swapChildren(BiTree T) { if (T NULL) { return; } BiTree temp T-lchild; T-lchild T-rchild; T-rchild temp; swapChildren(T-lchild); swapChildren(T-rchild); }这个考的是“先处理当前节点再递归处理子树”的执行顺序。你要是把swap放到递归后面问题也不大因为交换操作是幂等的多做一次也没事。但如果你先递归进去再交换逻辑上也成立只是要明白这个顺序差异。4.2 判断两棵树是否相似/相等判断两棵树是否“相似”意思是结构一致不管节点数据是什么。判断“相等”则要求结构和数据都一致。这两个题在课后习题里都有代码相似度很高。int isSimilar(BiTree A, BiTree B) { if (A NULL B NULL) { return 1; } if (A NULL || B NULL) { return 0; } return isSimilar(A-lchild, B-lchild) isSimilar(A-rchild, B-rchild); }判断相等的话在递归调用之前先比较数据int isEqual(BiTree A, BiTree B) { if (A NULL B NULL) { return 1; } if (A NULL || B NULL) { return 0; } if (A-data ! B-data) { return 0; } return isEqual(A-lchild, B-lchild) isEqual(A-rchild, B-rchild); }这类题目的关键就一个把所有“返回0”的情况提前判断掉剩下能走到最后递归的就是“两边都还有节点并且数据相等”的情况。我用逻辑短路来理解会快很多——只要有一个孩子子树不相似整个函数就返回0后面的递归就都不会执行了。4.3 线索二叉树的建立与遍历线索二叉树是第六章节里最“劝退”的题很多同学看到线索化代码就头大。我讲一个最容易记住的理解方式线索化是在中序遍历的过程中把空指针域改造成前驱和后继指针。代码长这样void inThreading(BiThrTree p, BiThrTree *pre) { if (p NULL) { return; } inThreading(p-lchild, pre); if (p-lchild NULL) { p-LTag Thread; p-lchild *pre; } if (*pre ! NULL (*pre)-rchild NULL) { (*pre)-RTag Thread; (*pre)-rchild p; } *pre p; inThreading(p-rchild, pre); }这里有两个细节你要注意。第一pre是指向指针的指针因为pre的值在递归过程中要不断更新你只传一级指针的话修改传不回去。第二线索化不能把左孩子是NULL但右孩子不是NULL的情况弄混LTag和RTag要区分清楚0表示孩子指针1表示线索。线索二叉树的课后习题一般不会让你从头写一个完整的线索化过程往往是给你一棵已经画好的二叉树让你画出它的中序线索二叉树。这种题有个取巧的办法先写出这棵树的中序遍历序列然后序列中每个节点的前驱和后继就一目了然了你只需要把指向空的左孩子改成指向前驱右孩子改成指向后继。先算中序序列再画线索基本不会错。5. 常见错误与调试经验——这些问题不踩一遍真不长记性5.1 递归出口写错导致的“段错误”递归代码最常见的崩溃就是段错误原因基本都是递归没有出口或者出口写错导致无限递归把栈空间耗尽了。比如统计叶子节点那个函数如果你先写“if (T-lchild NULL T-rchild NULL) return 1;”然后再写“if (T NULL) return 0;”那么你调用countLeaves(NULL)的时候程序会在第一行就去访问T-lchild而T是NULL直接就崩了。我自己的调试经验是递归函数第一行必须是空指针判断。这个习惯非常重要无论你写什么二叉树递归算法第一行写“if (T NULL) ...”几乎能躲过80%的段错误。还有一种情况段错误发生在“建树”阶段。很多课后的建树题要求你根据输入序列递归创建二叉树如果你在create函数里忘了为节点分配内存或者scanf取地址符写错了建出来的树本身就有问题后面遍历自然一碰就崩。所以出问题的时候先别急着检查遍历代码先确认树建得对不对。5.2 指针传参与值传递的经典陷阱我前面提过传二级指针的问题这里再拿一道典型习题展开说。课后有一道题要求“在二叉树中插入一个节点作为某个节点的左孩子”很多同学的错误版本是这样的void insertLeft(BiTree T, int data) { BiTree newNode (BiTree)malloc(sizeof(BiTNode)); newNode-data data; newNode-lchild NULL; newNode-rchild NULL; T-lchild newNode; }这个代码看起来没问题T不为空给T的左孩子赋一个新节点外部用的时候也正常。但如果你要插入的节点本身是NULL或者你想让整棵树的根节点变成新节点那这个函数就无能为力了。更深层的问题是C语言的传值特性你传给函数的是指针的拷贝。你可以在函数里修改“指针指向的内容”但不能修改“指针本身”。所以所有“需要改变指针本身”的操作都一定要用二级指针。在写二叉树插入删除类代码的时候我建议你先问自己一句这个操作要不要改变外部指针的值要的话就上二级指针不要犹豫。5.3 读入数据时的缓冲区问题第六章的课后习题里经常要手动输入二叉树节点数据很多时候用“输入一个整数0表示空节点”这样的格式。很多同学在这边踩坑输入多个值的时候scanf的换行符处理不对导致读进来的数据永远是错的代码逻辑再对也跑不出正确结果。这里我分享一个实用的处理方式如果你用的是scanf(%d, x)每次读取前不需要手动清除缓冲区因为%d会自动跳过空白字符包括空格、换行、Tab。真正坑的是scanf(%c, ch)这个不会跳过空白符你上一个scanf按完回车后缓冲区里残留的\n就会被%c当作有效字符读走。如果你在做“输入字符数据建树”的题我建议在%c前面加一个空格写成scanf( %c, ch)前面这个空格会让scanf先吞掉所有空白字符。这个写法看着奇怪但特别好用。另外如果你用getchar()读字符要注意在循环开头吃掉上一次的回车。6. 这套题做完之后怎么确认自己真的掌握了6.1 把“会做”变成“熟”的几个自查方法课后习题做完不等于这章就过了。我自己复习的时候会给自己做三件事你也可以参考第一合上书默写二叉树的链式存储结构体定义以及三种递归遍历的函数。这三个函数一天不写就手生考研前我保持每周至少写一遍的频率。第二列出第六章所有的算法题的“解法关键词”。比如“统计叶子节点”对应“递归加叶子判断”“求深度”对应“递归求左右最大值加一”“线索化”对应“中序遍历加空指针改造”。这个方法特别适合考前快速拉一遍重点。第三把前序中序推后序、后序中序推前序这种题至少做三遍。每一遍都不看答案独立画树独立写出遍历序列。第一遍可能花十分钟第三遍你大概两分钟就能搞定。能做对不等于理解了能自己讲清楚每一步为什么要这样做才是真的掌握了。你试试能不能给同学讲明白“为什么后序序列的最后一个元素一定是根节点”如果你讲的时候脑子里没有任何模糊的地方那这章就是真过关了。6.2 顺着第六章往后看这些思路后面全是考点第六章学扎实了你再往后翻第七章图的时候会发现到处都是熟人。图的深度优先搜索DFS本质上就是树的先序遍历的推广图的广度优先搜索BFS就是树的层次遍历换了一张脸。只不过图多了“visited数组防止重复访问”的问题树的递归骨架完全可以迁移过去。然后是第九章查找的二叉排序树、AVL树还有第十章排序里的堆排序——堆本质上就是一个完全二叉树。你要是第六章基础不牢后面学这些会非常痛苦。反过来第六章学得扎实堆排序的“下沉”操作、二叉排序树的插入删除也就剩下“照葫芦画瓢”的功夫了。所以我的建议是第六章的课后习题不要只做一遍就扔。隔一周回来把算法设计题再独立写一遍看看第一次踩过的坑第二次还会不会再踩。数据结构这门课没有捷径唯一的捷径就是多写、多画、多讲给别人听。你坚持把这个习惯保持到学期结束期末复习的时候会发现轻松非常多。最后再分享一个小经验做第六章的题草稿纸一定要舍得用。每一道遍历推导题、每一棵树的构建过程都老老实实在纸上画出来不要只在脑子里空想。我见过很多同学代码能写出来但问他这棵二叉树长什么样却画不出来那说明他只是背了代码并不是真的理解了结构。画图这个动作能帮你把抽象的递归过程变成具象的树结构这个过程省不得。