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

双亲表示法：采用一组连续的存储空间来存储每个结点,同时在每个节点中增设一个伪指针,指示双亲结点在数组中的位置。根结点的下标为0,其伪指针域为-1

根结点R没有双亲结点所以parent存储值为-1，其中A结点为根结点故parent值为0，其中D和E的双亲结点为A，故其parent存储双亲结点的下标为1，以此类推

1.2孩子表示法

孩子兄弟表示法：以二叉链表作为树的存储结构，又称二叉树表示法。

2.树&森林&二叉树

2.1树、森林与二叉树的转换

这里我们使用左孩子右兄弟的方法进行转换

那么将二叉树转换成原来的树其实就是逆过程，也就是将结点的右指针指向其双亲结点

2.3森林与二叉树的转换

那么将二叉树转换成原来的森林其实就是逆过程，也就是找到三棵树的位置，接着拆开得到三棵二叉树，接着转成原来的树

这里我们需要知道的是，二叉树只能转换成一种森林或者一种树，也就是二叉树转换成森林或者树是唯一的

3.树和森林的遍历

3.1树的遍历

树的遍历方式和二叉树的遍历方式没有中序遍历，因为树的结点可能有多个孩子结点，所以无法进行中根遍历，树的遍历方式有三种：先根遍历、后根遍历、层次遍历。其中层次遍历和二叉树的层次遍历相同（按照标号顺序，由上到下，由左到右）。

后根遍历：若树非空,则先按从左到右的顺序遍历根结点的每棵子树,再访问根结点。

对上图树进行树先根遍历：RADEBCFGHK

将其转成而二叉树

进行二叉树先序遍历：RADEBCFGHK

由此可得：树的先根遍历序列与这颗树对应的二叉树的先序遍历序列相同

对上图树进行树后根遍历：DEABGHKFCR

将其转成而二叉树

进行二叉树中序遍历：DEABGHKFCR

由此可得：树的后根遍历序列与这颗树对应的二叉树的中序遍历序列相同

3.2森林的遍历

中序遍历：若森林非空,则,中序遍历第一棵树的根结点的子树森林访问第一棵树的根结点,中序遍历除去第一棵树之后剩余的树构成的子树森林(相当于树的后根遍历)

将该森林转换成二叉树

二叉树先序遍历：ADEBCFGHK

可以得出：森林的先序遍历序列与对应的二叉树的先序遍历序列相同

森林中序遍历：DEABGHKFC

将该森林转换成二叉树

可以得出：森林的中序遍历序列与对应的二叉树的中序遍历序列相同

并查集：一种简单的集合表示。

在该集合中有若干个数据元素，我们也通常将该集合划分为几个子集，这些子集组成了该全集。

并查集：

· 通常用树的双亲表示法作为并查集的存储结构，也就是将每个子集表示成一个树的形式，这些树组成了该并查集的森林。

· 通常用数组元素的下标代表元素名,用根结点的下标代表子集合名,根结点的双亲结点为负数。

并查集操作：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.....

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