学习数据结构--第四章:树与二叉树(树和森林的相关知识)

学习数据结构--第四章:树与二叉树(树和森林的相关知识)

Scroll Down

第四章:树与二叉树(树和森林的相关知识)

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;

将上述二叉树使用双亲表示法存储:

0123456789
dataRABCDEFGHK
parent-1000113666

根结点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并入子集合Root1
Find(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
}

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