第四章：树与二叉树（树和森林的相关知识）

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
}

关于数据结构的知识公众号 理木客同步更新中，下次将会讲解：树与二叉树的应用，欢迎大家的关注