数据结构——树
数据结构——树
一、树、二叉树性质
一般这种题会问你结点数、高度、空指针域等问题
需牢记：
1.二叉树：n0 + n1 + n2 = n1 + 2*n2 + 1 = n
这个方程最重要！！！可以解决度、边、结点数直接关系的问题。题中出现度、结点直接用此公式就对了
2.二叉树：0 = 2 + 1，即叶节点数 = 度为2的结点数 + 1（由1的前两个组成方程推导出来）
3.二叉树：2n个孩子指针，只有n-1个结点可以作为孩子被指，故有2n-(n-1)=n+1个空指针（空链域）
4.完全/满二叉树：一行的起始结点号 = 该行可容纳的结点数 = 2^(n-1)；一行的末尾结点号 = 整棵树的结点数 = 2^n-1
5.完全二叉树：高度公式里上外下（+1在对数里面就向上取整，外面就向下取整）
6.完全二叉树的叶节点只有可能出现在倒数两行，一个完全二叉树的叶节点要么处于上面那行，要么出现在下面那行
二、二叉树的遍历
前序遍历，根左右，对于一个结点而言，先访问它，再访问其左子树，再访问其右子树。最后被访问到的是该结点右子树的最右下的叶节点。最先访问到的是结点本身。
中序遍历，左根右，对于一个结点而言，先访问其左子树，再访问它，再访问其右子树。最后被访问到的是该结点右子树的最右下转折处的结点。最先访问到的是其左子树最左下转折处的结点。
后序遍历，左右根，对于一个结点而言，先访问其左子树，再访问其右子树，再访问它。最后被访问到的是结点本身。最先访问到的是该结点左子树最左下的叶节点。
层次遍历，利用队列，从根节点进入队列开始，每次出一个，并将其孩子添加到队列中知道队列为空。
四个遍历一定要烂熟于心。
三、创造线索二叉树
介绍：线索二叉树的创造依赖于前、中、后遍历序列。结点的左孩子为空，则设置左孩子指针为其前驱的位置并置ltag = 1；结点的右孩子为空，则设置右孩子指针为其后继的位置并置rtag = 1。ltag与rtag表明了该结点的指针是否为线索。
将一棵二叉树改为线索二叉树：需要对二叉树遍历，而遍历分为先序中序与后序。遍历的种类决定了线索二叉树的种类。
先序：先设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子），再递归到左孩子，最后递归到右孩子。
中序：先递归到左孩子，再设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子），最后递归到右孩子。
后序：先递归到左孩子，再递归到右孩子，最后设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子）。
特别注意：先序遍历创造线索二叉树中，递归到左孩子小心此时的左孩子指针可能不指向其左孩子而指向其前驱。
四、遍历线索二叉树
方法：线索二叉树的遍历需由该线索二叉树的种类决定。但思想是一致的：多米诺骨牌——找到序列的首结点，从序列的首结点出发，想尽办法找到下一个结点。
先序：
找到序列首结点：即一个序列的根节点
找到下一个结点的办法：后继线索存在则用之。否则（右孩子存在），若左孩子不存 在，则下一个结点为右孩子；若左孩子存在，则下一个结点为左孩子。
中序：
找到序列首结点：最左下转折处的结点
找到下一个结点的办法：后继线索存在则用之。否则（右孩子存在），找到右子树序
列首结点。
后序：
找到序列首结点：最左下的叶节点
找到下一个结点的办法：后继线索存在则用之。否则，若其为左孩子且其双亲右孩子
存在，找到其双亲右子树的最左下的叶结点；若其为左孩子且其双亲右孩子不存
在，则其双亲就是后继；若其为双亲的右孩子，则其双亲同样为后继。
可见后序线索二叉树找后继需要找双亲结点，需要借助三叉链表或栈。
五、树、森林转二叉树
每个结点的左右指针存储左孩子右兄弟。相当于整个树/森林顺时针旋转了45度。转成后的二叉树左孩子空指针域都是原来树的叶节点才有的；右孩子空指针域每个非叶节点一个（在非叶节点的最后一个孩子处），若是森林最后一棵树的根节点又有一个。
六、哈夫曼树
若所有叶节点表示一种信息，叶节点的权为信息使用的频度。整棵树的带权路径长度评价了用二进制对信息进行编码的代价。而哈夫曼树做到了使这种代价最小。
构造哈夫曼树（最重要）：若由n个带权结点需要生成哈夫曼树，则将他们所有视为一棵棵单节点树。每次取权值最小的合并，新树权值为合并前两棵树的权值之和。
从构造过程可以看出：每次两棵树合并，左右位置可互换，因此每次合并有两种选择。故哈夫曼树不是唯一的。
每次合并树的数量都少1，初始n棵，最后1棵，故合并了n-1次，产生了n-1个非叶节点，最后的树总计n-1+n=2n-1个结点。
补充1：还可以为三进制、四进制...创造哈夫曼树，此时哈夫曼树就不再是二叉树了。整棵树的度要么为进制数，要么为0。
补充2：哈夫曼树的带权路径长度的两种计算方法：①所有叶节点带权路径长度之和（原始定义）；②所有分支结点（非根节点）权值之和（记住即可，没讲为什么）
七、并查集
能够合并与查找结点所在集合的数据结构称为并查集。采用顺序存储的双亲表示法表示的森林（不一定是二叉树森林）来实现。森林中每一棵树就代表一个集合。
查找：查找一个元素所在的集合，就是查找其所在树的根节点。采用循环访问其双亲结点的索引知道-1（根节点处的索引）即可。另外可以在每次循环结束（找到后）进行一些步骤来优化。具体措施是再走一遍循环，将每一个访问到的结点的索引都改成根节点的索引，即直接称为根节点的孩子，以此减小树高。
合并：合并两棵树。可能需要利用查找找到根节点的索引。直接将一个根节点的数组内容（双亲索引）从-1改为另一个根节点的索引即可。更优化的方法是，让所有根节点的数组内容不再存储-1，而是树的结点个数，在合并的时候使用条件语句保证小树合并到大树，以此减小树高。
1