数据结构 5-0 树与二叉树总结

前言

数据结构复习过程中最先遭遇的磕碰，这一章内容及其多，而且可以考得很难，不仅是代码题，填空题有些也很有难度。主要是四部分内容：树的基本概念、二叉树、树与森林、树的应用。题目以选择题为主，因为代码题确实手写比较有难度，选择题时画出树的结构是最好的工具。

树的基本概念

许多没什么意思的概念就直接上截图了：

这里说的是树的定义，里面主要是两个点：除了树根其余所有节点都只有一个前驱，所有节点可以有零个或者多个后继。这个规律在后面计算节点个数的规律时很有用。


书上对于概念的叙述很罗嗦，对概念简化一下：图上从A出发走到K，中间经过的点全是K的祖先，反过来称K是A的子孙，K相当于是E产生的，所以E称为K的双亲节点，反过来K是E的孩子结点，K和L都是来自一个双亲节点，所以称为兄弟节点。一个节点有的孩子树就是这个点的度，可以看成下面有几个分支。树里面所有节点最大的度就是树的度。没有孩子节点的节点称为叶节点，不是叶节点就称为分支节点（在树中间部分）。深度和高度注意好方向即可。森林是许多棵树的集合，比较极端的情况是整个森林是由许多个节点组成的森林，但仍然符合定义，因为只有根节点也可以算作一棵树。

在概念部分，最重要的是树的性质，树具有如下的基本性质：
①节点数等于所有节点的度数加一。所有节点只要有向下的分支，一定产生了一个孩子，反过来理解，除了根节点，所有节点都是由一个节点产生的，所以加一补上根节点。
②度为m的树中第i层上最多有m^(i-1)个节点。节点最多的时候，每层的节点数构成了一个公比为m的等比数列，数列的初值为1，所以根据等比数列的通项公式，第i项即为第i层的节点数。
③高度为h的m叉树至多有（m^h-1）/(m-1)个节点。这条规律也是用等比数列来理解，节点最多的时候，每一层都是满的，所以求此时的节点数相当于求等比数列的前h项和，利用公式直接写出这条规律。
④具有n个节点的m叉树最小高度为
这条规律解释起来稍微有点麻烦，规律说的是最小高度，所以说树的上面部分一定是排满的，如果树有h层，那么前h-1层一定是排满的，此时就可以逆用规律③，得到下面的等式，而此时的h不一定是整数，采用向上取整的方法来让其变为整数，向上取整也是结合了树的层数的计数规律，这一点不难发现。

二叉树

二叉树是树里面比较有代表性的，分支数太多会让树的结构太臃肿，两个分支不仅保证了树在简洁的同时还存储了足够的数据，而且还可以与01二进制结合，所以是最常用的树。二叉树本质上还是一棵树，所以树的概念在这里依然适用。

在二叉树的概念这里出现了第一个比较容易混的点：二叉树与度为2的有序树的区别。首先二叉树是有序树，其交换左右子树一定会导致二叉树变成另一棵树。但是二叉树的节点的度不一定都是2，二叉树可以只有一个子树甚至没有都可以，但度为2的有序树却不能，后者至少要有三个节点，而且这三个节点必须能让树的度为2才行，此外度为2的有序树的左右次序是相对于另一个孩子而言的，如果只有一个孩子那也就没有顺序可言了。

在二叉树中，又给一些常见形态的二叉树起了别名：
①满二叉树：高度为h且含有2^h-1个节点的树称为满二叉树。就是在上一部分中说到的排满的树。满二叉树中每一层都是满的，即除了叶子节点每个节点都有两个孩子。如果按照从上到下从左到右的顺序给树中的每个节点编号，那么编号为i的节点，除以二就是其双亲节点，乘以二和乘以二加一就是其两个孩子结点。
②完全二叉树：对于满二叉树的要求过于严苛，每一层必须排满，而多数的二叉树不会排满，所以延伸出完全二叉树，即其每个节点的编号都与满二叉树中的编号一一对应时的二叉树。可以把完全二叉树看做是满二叉树扣去了最下面一层的一部分而形成的树。完全二叉树也是最常考的树之一。其具有如下规律：

其中需要解释一下，第二条叶子节点出现在两层，是因为完全二叉树不一定排满，所以在倒数第二层上可能出现叶子节点，而且只能是出现在右边，相对的最下面一层的叶子节点只能出现在左边。
③二叉排序树：根据输入数据的大小进行动态调整的树，这种树会在树的应用上总结。
④平衡二叉树：最麻烦的一种树，是指任一节点的左右子树的深度之差不超过1的二叉排序树，这种树也会在树的应用中总结。

二叉树的性质常在选择题里面考察，考得很灵活，主要有下面的性质：

其中，第一条的性质的推导过程一定要灵活使用，这条规律不仅会用在二叉树，在计算节点数目的题中也会经常用到。其余规律都是树的规律在二叉树中的具体化。

二叉树的代码实现可以参考之前第二节的总结
https://blog.****.net/weixin_43849505/article/details/107323532
总的来说，一般二叉树用链式存储而不用顺序存储，因为顺序存储必须要解决空间的浪费问题，链式存储灵活分配的特点刚好适合二叉树的需求。

二叉树的遍历与线索化

这一部分是代码题的集中部分，在这里考代码题，代码手写有难度但不至于彻底写不出来。
遍历递归：https://blog.****.net/weixin_43849505/article/details/107371412
遍历非递归：https://blog.****.net/weixin_43849505/article/details/107371757
线索化：https://blog.****.net/weixin_43849505/article/details/107396769
遍历分为四种：前序、中序、后序和层序，前三者区别在于访问节点顺序和子树顺序的先后，层序算是一种例外，一层一层借助队列来访问。具体的代码在之前的小节里面都有，这里就不再赘述了。

遍历这里常考的题就是根据遍历序列构建二叉树。由先序和中序时可以唯一确定一棵二叉树的，后序序列和中序序列也可以唯一确定，其余组合是确定不出来的。对于选择填空题，只要按照两个序列画就完事了，先序遍历的第一个节点和后序遍历的最后一个节点一定是二叉树的根节点，根据这个，将中序遍历划分为两部分，再对两部分做同样的操作，理解了这个过程并不难做。

线索化的知识在前面的小节里面也有。总的来说，线索二叉树是普通二叉树的一种改进，优化了普通二叉树只能表示父子关系而在前驱后继的方面上比较麻烦的特点，通过人为规定前驱后继指针，来加快查找前驱后继节点的速度。选择题最好将树的指向情况都在树里面标注下，这样更方便去找前驱后继。

树与森林

二叉树是树中的一个特例，对于一般的树，还有别的考察点。
不同于一般的二叉树，树具有三种表示方法:双亲表示法、孩子表示法、孩子兄弟表示法。
双亲表示法最好理解，把二叉树里面的指针方向反过来就行了，让指针从孩子指向双亲，这样的好处是方便找双亲，但是缺点也很明显-不方便找孩子。一般使用这种表示法多用顺序存储，最好的实例就是并查集：https://blog.****.net/weixin_43849505/article/details/107499141。

孩子表示法是将每个节点的孩子节点都用单链表连接起来形成一个线性结构，用孩子链表来表示，叶节点的孩子链表为空，这种操作方式方便找孩子，但是找双亲节点却又麻烦的要死。从图不难看出，一个孩子链表中的节点在树中实际都是兄弟节点。
孩子兄弟表示法，也称二叉树表示法，是综合了上面两种方法得到的表示方法，它规定让左指针指向第一个孩子，右指针指向下一个兄弟，以此来构建二叉树，这样可以把一颗树转换为与之对应的二叉树。易于查找孩子，但是找双亲节点依然有困难，可以补一个指针指向其双亲节点来弥补这个问题。

这三类表示方法之后，就可以让一颗树转换为二叉树，转换规则为：让每个节点左指针指向第一个孩子，右指针指向下一个兄弟。由于根节点没有兄弟，所以转换后一定没有右子树。具体操作时，先在所有兄弟之间加一条横向连线，之后对每个节点，只保留与第一个孩子的连线，之后以树根为轴，调整整棵树的方向，让其符合二叉树的方向习惯。

如果要把森林转换为二叉树，其操作与树转二叉树类似。先把森林中的每棵树都转换为二叉树，之后从第一棵树开始，把下一棵树看做当前树的兄弟节点，以此再把所有转换好的二叉树连接起来。如果需要将二叉树再转换为森林，只需要从根节点开始，把根节点和其左子树摘出来，一直重复直到整棵二叉树完全拆完，得到的就是森林里面所有树的二叉树状态。

二叉树中的三种遍历方式，对应到树和森林中，换为先根遍历、后根遍历、层次遍历，思路与二叉树遍历一致，这里就不做赘述了。森林转换为二叉树时，第一棵子树森林转换为左子树，剩余树的森林转换为了右子树，所以森林的先序和中序遍历即为对应二叉树的先序和中序遍历。

树与二叉树的应用

应用这里涉及的知识点很多而且很难，陈越版本的数据结构和严蔚敏版的提到的知识也不一样。

一、二叉排序树
二叉排序树可以看作是动态生成的一颗二叉树，一般来说二叉树只有节点上的限制，而对存放在其内部的数据没有限制，二叉排序树则是规定，左子树的值要小于节点的值，右子树的值要大于节点的值，做了如此规定，不难发现对二叉排序树做中序遍历得到的一定是一个递增的有序序列。

二叉排序树的查找，通过比较节点值和要插入数据的值，如果要查找的值小于节点值，就遍历左子树，否则遍历右子树一直寻找直到节点值就是要找的值。代码模板如下：

二叉排序树的插入是比较重要的点，排序树是一个动态树，树的结构不是一次生成的，而是在查找过程中动态生成的，根据查找的顺序的不同，产生的二叉排序树也是不同的。插入规则为：若原二叉排序树为空，则直接将值作为根节点的值，之后根据目标值与节点值的大小关系，为目标值找到合适的位置再插入树中。代码模板如下：

构造二叉排序树的过程实际上就是不断给二叉排序树插入节点的过程，插入节点实际上又是对查找节点的扩展。

对于二叉排序树的删除操作，由于二叉排序树的特殊性，删除节点后不能直接连接，而是应该删除后调整树中节点的关系，保证大小关系不能变。前面两种删除方式还比较好理解，主要是第三种，需要把右子树中序第一孩子结点给提到上面来。


二叉排序树的查找效率，主要是取决于树的高度，当二叉排序树为平衡二叉树时，平均查找长度为O(log2n)，而当排序树中所有节点都只有左孩子或者只有右孩子时，平均查找长度就成了O(n)，平均查找长度的计算方法为节点数乘以高度求和再除以总结点数，查找失败的长度只需要再一般的树上添加一层即可。

二、平衡二叉树