树的定义和性质：

具体的细节书上都已经有所划录，列下重点

树的性质里面概括比较少和不够全面，这些是个人认为需要掌握清楚，复习的要点

1.度M，第i层至少、至多多少个结点；M叉树，第i层至少、至多多少个结点

2.度M，高h，至少、至多多少个结点；M叉树，高h，至少、至多多少个结点

3.度M，N个结点，最低、最高的h分别是多少；M叉树，N个结点，最低、最高的h分别是多少

4.具体再加上一个性质：度和=结点数+1，这样就构成了这一节的主要内容

习题和其他补充：

对于16年统考出的森林和树的关系题，现在其实个人就有比较明确的思路

这类题如果在考场上面一时半会不太反应得过来，记住仍然有最后一个方法去破题

就是直接依靠举例归纳得出结果，不一定要按照题目的来，一个个举例归纳规律

这种方法应该要视作是考场上面最常见的手段，因为不可能都考察熟悉的东西

类似于10年的考题，当时可能都没有这种知识点的概括，怎么办？只能靠临场归纳的

6：注意下公式计算上面尽可能不要有二进制的思维惯性

3：当作一个补充即可，本节内容不多

二叉树的概念：

这一节内容基本都在书上且比较完整，就没有单独列出来提纲（没有书上的完整

二叉树的定义之类的细节已经基本划了，书上的重点在一堆性质里面，已经是最完整了

一般对于考察性质来说（统考中可能会考察一些新的情况

最好的办法就是举例，如果一时半会想不到方法或者没找到切入点就只能靠归纳理解

因为这类规律一般具有普遍性，所以考场里面的临场归纳就比较重要

如果有时候可能忘了，那么依靠举例也是能很快得到结果的，都不必刻意去记

习题补充总结：

1：重新再做一遍题目就能清楚自己之前忽略的理解点，对于度为N和N叉树的那段话上

其实一开始理解还是有些缺失的，没有看到“有序”两个字，这也就是复习的意义

后续：

大多数题目考察的都是树的性质，个人认为细节需要注意在题设到底是什么树上面

如果连二叉树、满二叉树、完全二叉树、M叉树这样一些基本题设都看错

那么根本就不可能做对，所以重点其实在于审题

5：这类题目最好的办法就是去举例，考场上面也是一样的，碰到新的题没思路就举例

12：某层给定叶结点，求最多必然是这一层是倒数第二层，求最少这就是最后一层

18：人不会两次踏进同一条河流，这道题错了两次

现在总结下这类举例的技巧：一般如果考察特例情况，必须考虑空树和只有一个根结点

只有一个根结点即为根节点又作为叶的情况，这种情况最容易考察到

20：略微注意下数组的开始位置，考察的时候不一定和树的结点序号一致的

26：满二叉树略微有一些小的总结，但一般比较容易推导，可以随意看看

28：审题，这是三叉树，不是二叉树，划清楚这是什么树再做…

二叉树的遍历和线索化（本节内容较多：

基本要点和内容：

1.由一棵二叉树写其先序、后序、中序、层序，根据出入栈得到先序、中序序列

根据中序和先序、后序、层序分别重新构造这棵二叉树，必须要保证正确率和速度

2.二叉树层序遍历的队列执行一遍

3.先序、中序、后序建立线索二叉树的代码和执行过程、初始条件、结束条件

4.中序线索二叉树求第一个结点、求最后一个结点，求前驱、后继

5.先序、后序线索二叉树分别求其后继、前驱列出情况，在三元表之上求其前驱后继

这里对书上内容稍微进行一些补充，因为本节内容较多：

递归工作栈的工作深度就是树的高度可能会作为考点，应该是比较现实的

非递归算法中个人往往忽略了出栈的条件实际上是左子树为空即出栈，之前即理解错误

后序要求不高，只需要大致知道思想即可，对最后一句话稍微重视下

线索二叉树并不能保证一定就能直接找到前驱或者后继，只能在某些情况下加速寻找

书上最后一段文字可以不用细看，因为流程适合用图描述而不是用文字描述

习题补充：

1：排除法和举例法是最常用的方法，因为只需要掌握应用而不需要掌握具体证明

根作为叶的情况就经常需要拿出来用的

5：对后序遍历的补充，这个算是一个知识点和思路类型的

7：一个重要的结论：在任何一棵二叉树的遍历序列里面，叶子结点的相对位置不改变

所以一般可以依靠这个来判断哪些可能的叶子（为什么说可能？不一定只有这一种情况

例如后面的36题内，既可以是b、d作叶子，也可是b、c作叶子，没有“一定”这句话

但一般情况下都是可以省事很多的

8、9：举例即可

12、13、16、20、27、29、30、33、37、40、41、42均是抽象型，抽象概括遍历解题

中序是“左根右”，先序是“根左右”，后序是“左右根”，以此做题

先序和中序的考察一般都是结合栈来考察的，这个具体就不再赘述，比较简单

21：后序是一种“摘”叶子的方式来遍历，每次摘下来的一定是一个当前的“叶子”

23：一般碰到比较古怪的题目就默认选物理结构或者说是存储结构

这类题目很难描述，因为本身定义就不太清晰，也只能说具体看情况去选择

26、27：严格而言线索二叉树仍然还是有空指针域的，但一般可以依靠头结点来利用的

所以如果考察的话多少还是要注意这样一个细节问题

28、31：一个简单的道理，中序可以求其前驱、后继，但先序只能后继，后序只能前驱

因此如果要向前遍历那么只能是中序、后序线索化才能得到

如果是向后遍历，那么只有中序、先序线索化才能得到，遍历一般默认都是正向的

当然如果添加了三元表自然就都可以实现前驱、后继的搜索，但考察上面还是要注意下

严格而言各种遍历都是利用了栈的，要么是递归工作栈，要么是非递归栈

但这里的含义就是哪种情况下不需要主动设置一个非递归栈，理解或许会有偏差

35：一般考场上面就直接举例即可，不要在这种题目上面花费过多时间

36：题目是很好的，而且依旧是触及到了个人的知识盲点或者说不太理解的点上面

个人对遍历序列的理解上面还是差了那么一点，没有能够从整体上面去观察

先前曾经说的，要么d、b作叶子，要么b、c作叶子，这个确实是可以帮助解题的

42：我也不知道怎么错的

树、森林：

书上内容概括与补充复习（想讲的比较多，很难写完整

三种表示方法各自的优点和缺点，以及对应的数据结构形状（很难回忆起来）

一般说的二叉树的顺序存储结构就是以“满二叉”类型顺序存储的情况，一般很少使用

树的顺序存储结构里面数组一定是满的，而二叉树的顺序存储结构数组不一定满

一般用得比较多的是孩子兄弟表示法，主要是其增加三元链表后访问双亲和孩子都方便

树转为二叉树、森林转为二叉树、二叉树转森林是最基本的方法，不多说了

最后的遍历，谈一些理解：

在当初出题的时候王道书上肯定是没有这样一个重点的，那么考试得面对全新的知识点

怎么办？难道碰到不会的就束手无策？并不是如此，依旧可以依靠先前的经验拓展

数据结构的题目碰到新的完全是可以依靠归纳总结出结果的，就像这边的遍历的结论

考场里面碰到肯定是没见过这个知识点，又一时半会想不出来

那么直接考虑举例、暴力解决，列一个树、森林然后求出对应二叉树，直接开始遍历

遍历出来的结果符合的就是一定对的，这种也是最常用、最可靠的方法

虽然可能会略微耗时，但在做不出来的情况下，这种一定是最为有效的策略

习题归纳整理：

2-6：最重要的依旧是审题，看清楚题目要求的是什么东西，否则就别谈做题了

这种地方最容易看错和审题出错，做题的时候先划好关键词再回去做

6：这种画的时候稍微画清楚一点，用黑笔标注出连接关系，否则会比较难数清楚

因为后面的结点如果不标注清楚可能连是哪棵树的都不知道

8、15：两道题是很不错的题，联系了二叉树和原来的树或者森林，考察较为灵活的

怎么破题？主要就是从二叉树的基本性质出发，分别列举出不同度的结点情况

然后只需要各自列出方程就能求解，建议多加思索，很容易再度考察，出现新题型的

出现新题型怎么办？其实还有一条路，看看能不能凑、归纳出结果

12：猜下是怎么个错法，想一下右边在哪，哪边是右边，居然半天没发现问题在哪

见鬼了

13、14：一般建议就是举例，这样最快也最不费脑子

18：稍微注意下后序遍历的练习，因为后序默认是从左子树开始的，这一点要记住清楚

还是建议单独多练几遍的，这种属于基本功，不能出现闪失

哈夫曼树、并查集：