第四章：树与二叉树（树和森林的相关知识）
1.存储方式
1.1双亲表示法
双亲表示法：采用一组连续的存储空间来存储每个结点,同时在每个节点中增设一个伪指针,指示双亲结点在数组中的位置。根结点的下标为0,其伪指针域为-1
代码实现：
//每一个结点，数据 data 和标识双亲结点的下标的 parent
#define MAX_TREE_SIZE 100
typedef struct{
ElemType data;
int parent;
}PTNode;
//二叉树结构体
typedef struct{
PTNode nodes[MAX_TREE_SIZE]; //所有的结点信息
int n; //该树结点的个数
}PTree;将上述二叉树使用双亲表示法存储：
根结点R没有双亲结点所以parent存储值为-1，其中A结点为根结点故parent值为0，其中D和E的双亲结点为A，故其parent存储双亲结点的下标为1，以此类推
1.2孩子表示法
孩子表示法：将每个结点的孩子结点都用单链表连接起来形成一个线性结构,n个结点具有n个孩子链表。
//每一个孩子结点的结构体
#define MAX_TREE_SIZE 100
typedef struct{
int child; //孩子结点的下标
struct *CNode *next; //下一个孩子结点的指针
}CNode;
//每一个结点存放的数据元素以及第一个孩子结点的指针
typedef struct{
ElemType data;
struct CNode *child;
}PNode;
//整棵二叉树
typedef struct{
PNode nodes[MAX_TREE_SIZE];//所有的结点信息
int n; //该树结点的个数
}CTree;将上述二叉树使用孩子表示法存储：
相当于将每一个结点和其孩子结点构成一个链表，其中R有孩子结点A B C 下标分别为 1 2 3，所以构成的链表的child值存储其下标，A结点有孩子结点D E，下标为4 5，故构成的链表的child值存储其下标，依次类推
1.3孩子兄弟表示法
孩子兄弟表示法：以二叉链表作为树的存储结构，又称二叉树表示法。
我们知道二叉链表仅仅多了两个指针，那么如何如何存放这么多的孩子节点呢？结构设计如下：
因此此方法又称为 左孩子右兄弟
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,CSTree;将上述二叉树使用孩子兄弟表示法存储，在进行表示的时候牢记 左孩子右兄弟
由于根结点没有兄弟结点，所以它的右指针永远为空，他的左指针指向它的第一个孩子结点A....
1.4总结
2.树&森林&二叉树
2.1树、森林与二叉树的转换
上面我们知道树利用孩兄弟表示法可以存储到二叉链表中，而二叉树也可以存储到二叉链表中，所以可以实现树与二叉树的相互转换。
2.2树与二叉树的转换
这里我们使用左孩子右兄弟的方法进行转换
转换：将指针指向它的第一个孩子结点，右指针指向兄弟
变成成我们常见的二叉树的形式
转换规则：每一个结点左指针指向它的第一个孩子结点，右指针指向它在树中相邻的兄弟结点。
那么将二叉树转换成原来的树其实就是逆过程，也就是将结点的右指针指向其双亲结点
2.3森林与二叉树的转换
下面是一个有三棵树的森林
首先我们按照上面的方法将每一棵树转成二叉树（左孩子右兄弟的方法）
接着我们把每一棵树的根结点看作兄弟结点，然后使用右指针将其连接起来
接着转成我们常见的方式
转换规则：将每一棵树转换成二叉树，将每棵二叉树的根依次作为上一棵二叉树的右子树
那么将二叉树转换成原来的森林其实就是逆过程，也就是找到三棵树的位置，接着拆开得到三棵二叉树，接着转成原来的树
这里我们需要知道的是，二叉树只能转换成一种森林或者一种树，也就是二叉树转换成森林或者树是唯一的
3.树和森林的遍历
3.1树的遍历
树的遍历：按照某种方式访问树中的每个结点，且仅访问一次。
树的遍历方式和二叉树的遍历方式没有中序遍历，因为树的结点可能有多个孩子结点，所以无法进行中根遍历，树的遍历方式有三种：先根遍历、后根遍历、层次遍历。其中层次遍历和二叉树的层次遍历相同（按照标号顺序，由上到下，由左到右）。
先根遍历：若树非空,则先访问根结点,再按从左到右的顺序遍历根结点的每棵子树。
后根遍历：若树非空,则先按从左到右的顺序遍历根结点的每棵子树,再访问根结点。
对上图树进行树先根遍历：RADEBCFGHK
将其转成而二叉树
进行二叉树先序遍历：RADEBCFGHK
由此可得：树的先根遍历序列与这颗树对应的二叉树的先序遍历序列相同
对上图树进行树后根遍历：DEABGHKFCR
将其转成而二叉树
进行二叉树中序遍历：DEABGHKFCR
由此可得：树的后根遍历序列与这颗树对应的二叉树的中序遍历序列相同
3.2森林的遍历
先序遍历：若森林非空,则,访问森林中第一棵树的根结点·先序遍历第一棵树的子树森林,先序遍历除去第一棵树之后剩余的树构成的子树森林。
中序遍历：若森林非空,则,中序遍历第一棵树的根结点的子树森林访问第一棵树的根结点,中序遍历除去第一棵树之后剩余的树构成的子树森林(相当于树的后根遍历)
森林先序遍历：ADEBCFGHK
将该森林转换成二叉树
二叉树先序遍历：ADEBCFGHK
可以得出：森林的先序遍历序列与对应的二叉树的先序遍历序列相同
森林中序遍历：DEABGHKFC
将该森林转换成二叉树
二叉树中序遍历：DEABGHKFC
可以得出：森林的中序遍历序列与对应的二叉树的中序遍历序列相同
4.树的应用
4.1并查集
并查集：一种简单的集合表示。
在该集合中有若干个数据元素，我们也通常将该集合划分为几个子集，这些子集组成了该全集。
并查集：
· 通常用树的双亲表示法作为并查集的存储结构，也就是将每个子集表示成一个树的形式，这些树组成了该并查集的森林。
· 通常用数组元素的下标代表元素名,用根结点的下标代表子集合名,根结点的双亲结点为负数。
并查集操作：Initial(S)将集合S中的每个元素都初始化为只有一个单元素的子集合Union(S, Root1, Root2)把集合S中的子集合(互不相交)Root2并入子集合Root1Find(S, x)查找集合S中单元素 x 所在子集合,并返回该子集合的名字，即该元素所在子集合根节点的元素的下标
例子：集合 S={0，1，2，3，4，5，6，7，8，9}，初始化的时候我们将每一个元素初始化为一个子集合：S0={0},S1={1},S2={2},S3={3},S4={4},S5={5},S6={6},S7={7},S8={8},S9={9}，用树表示就是10个根结点
用双亲表示法存放：
接着集合 合并成：S0={0,6,7,8},S1={1,4,9},S2={2,3,5}型的话，它们应该变成什么样的树?
使用双亲表示法存放：
0结点(下标)的parent值为-4，首先0结点为根结点所以为负数，另外0结点所在的树有四个结点所以为-4，它的绝对值代表0结点所在树的结点个数。同样 1 和 2结点.....，对于 3 结点，他有双亲结点为2，所以它的parent为双亲结点的下标2.....
代码实现：
#define SIZE 100
//用一个整性数组表示并查集(这里我们默认数据和数组下标一致，如果不一致可以使用结构体数组)
int UFSets[SIZE];
//初始化 传入并查集S
void Initial(int S[]){
for(int i=0;i<size;i++){
S[i]=-1
}
}
//查找 传入并查集S和要查找的元素x
//我们要查找该元素所在子集合根节点的元素的下标
int Find(int S[],int x){
//注意这里的元素x其实就是双亲结点的下标
while(S[x]>=0){ //如果是正数则不是根结点
x=S[x];
}
return x;
}
//合并 传入 并查集S 以及两个子集合对应根结点的下标
void Union(int S[],int Root1,int Root2){
S[Root2]=Root1; //把Root2合并到Root1
}关于数据结构的知识公众号 理木客同步更新中，下次将会讲解：树与二叉树的应用，欢迎大家的关注
<script type="text/javascript" src="//mp.toutiao.com/mp/agw/mass_profit/pc_product_promotions_js?item_id=6833350710180971020"></script>