讲解在线视频

这一小节，我们来学习树

与森林

跟现实世界当中的树和森林的关系一样

森林是由若干棵不相交的树组成的

对于一棵树来说

注意，我们这里讲的是一般意义的树，不一定是二叉树

如何来存储一棵树呢

第一种表示方法

双亲表示法

因为，对于任何一棵树来说

树中每一个结点，都有唯一的一个父结点

我们可以采用这个特性，来存储树

无论树是几叉树

现在，我们用一维数组来存储各结点

比如，左边这样一棵树

我们采用一维数组

存放下每一个结点的自身信息，以及该结点的父结点

在数组当中的下标，就可以了

每个结点存放其父结点在数组中的下标

它的优点

是找双亲的时间复杂度是O(1)

直接能找到

比如，我们去找J这个结点它的双亲

J这个结点

它在

下标11的位置

我们发现，它的这个成员是8

于是，我们找到下标为8的单元

它里面的信息是D

于是，J的双亲就是D

但它的缺点也很明显

找孩子的时间复杂度

是O(n)，跟结点个数相关

比如，我们找D这个结点它的所有孩子

D这个结点

它的下标是8

于是

我们就要去扫描整个一维数组，去看哪些结点的第二个成员是8

发现有这3个

于是，找到了D的所有孩子

H、I、J

再来看第二种表示法

孩子表示法，与二叉链表类似

但孩子指针有多个，二叉树

顶多只有两个孩子

所以，我们设了两个指针(左右指针)

现在是一棵普通的树

到底我们设多少个孩子指针呢

第一种方式，全部结点的指针数一致

比如，一个D叉树

我们就设D个孩子指针

比如，根结点

它有10个孩子

每个结点就设10个孩子指针

由于这棵树当中，除了根结点之外

其他的结点都是叶子结点

这些叶子结点是没有孩子的

但是我们已经说了，每个结点它的指针数是一致的

这时候

实现虽然简单

但是浪费了存储空间

我们来改进一下

我们按需分配

每个结点的指针数，等于它的孩子数

有几个孩子

就设置几个孩子指针

但是，这样会导致一个问题

就是每个结点的结构不一致

一旦结点结构不一致

这时候，我们很难去写代码

可能需要调用C语言malloc，去动态地分配若干个指针

这里除了存放若干个用来表示孩子的指针之外

为了方便操作

我们还存放了一个成员，来表示

这个结点的孩子数

将来，可能需要这个值，来动态地分配后面的若干个指针

由于结点之间的结构不一样

不同构，所以，编程实现起来比较困难

这是它的缺点

现在，我们来看第三种表示方法

孩子链表表示法

在这种表示方法下

结点的全部孩子组成一个单链表

比如，这个单链表

所有父结点相同的结点，组成了同一个单链表

比如，B的孩子D和E

它们就位于这个单链表上

每一个结点都会引出一个单链表，B结点引出的单链表的第一个结点的第一个成员是4

第二个结点的第一个成员是5

我们找到4、5下标

发现是D和E

这就是孩子链表

究其本质

就是兄弟结点构成同一个链表

这种存储结构，所有的单链表的头结点，存于一个一维数组

每一个头结点包含

结点自身的信息，以及第二个成员，是一个指针

它指向该结点的第一个孩子

这里的fc，表示的是first child

第一个孩子指针

这种结构，找孩子是比较快的

比如，我们找到B结点，就能找到B的孩子D和E，扫描横向的链表就行了

但是找双亲却比较麻烦

比如，我们现在要去找I结点的双亲

I结点

下标是9

我们要去扫描所有的单链表，去看这些单链表当中，哪一些结点的第一个成员是9

从前往后，一直找

找到最后，才发现这个结点的第一个成员是9

将所有的单链表都扫描完毕

才找到了I的双亲E

所以，它的效率是比较低的

这时候，我们可以继续做改进

无非就是找双亲比较慢

那我们在初始化的时候，为头结点增加

一个成员，表示

每一个结点它的双亲下标

比如

I它的父结点下标5

我们直接放到这里

将来，找双亲就比较快了

再来看下一种存储方式

孩子兄弟表示法

在这种方式下

每个结点只包含两个指针

它的结构，跟二叉链表是一样的

但是，这两个指针的意义是有变化的

这两个指针不再指向当前结点的左、右孩子

而是指向当前结点的第一个孩子，和下一个兄弟

注意，是第一个孩子，和下一个兄弟

它的结点结构是这样的，指针名我们起成了firstChild

和nextSibling

sibling

就是兄弟的意思

这样一种结构

我们以这棵树为例

这棵树实际上是一棵三叉树

E有3个孩子

根结点没什么说的，是A，根结点的左指针

注意，是指向第一个孩子的

我们认为最左边的是第一个孩子

也就是指向B，根结点的右指针是谁呢

由于右指针指向的是下一个兄弟

现在只有一棵树

这棵树的根，它是没有兄弟的

所以，A的右指针为空

再看B

B的左指针，指向第一个孩子D

右指针不是指向E了

而是指向B的兄弟

B的兄弟是C

所以，B的右指针指向的是C

这个需要注意，这种方式下，实际上是将一个普通的树转换成了二叉树

无论是几叉的树

我们通过第一个孩子和下一个兄弟这种表示法

将一棵普通的树转换成了二叉树

这棵二叉树

它的根的右指针总是空的

刚才我们已经分析过了

我们继续来看，森林与二叉树的转换

森林是多棵不相交的树构成的集合

我们约定，这多棵树的根互为兄弟

这样，我们就可以将一个包含多棵树的森林

转换成对应的二叉树

二叉树的根，就是第一棵树的根

根及其左子树，就对应着森林当中的第一棵树

右子树

就对应着后面若干棵树

我们也可以根据

转化而来的二叉树，将它还原回对应的森林

这里需要注意，在转换而来的二叉树当中

从根沿着右孩子的方向，经历的所有的结点

比如E、G，实际上是每一棵树的根

因为，我们已经约定了，这多棵树的根互为兄弟

而孩子兄弟链表当中

右指针存放的，就是下一个兄弟

我们继续来看树的遍历

分为先序遍历和后序遍历

跟我们前面讲的二叉树不一样

二叉树

可以把根放在左、右子树的中间遍历

而树呢

没有一个位置是确切的中间位置

所以

对于树来说

它是没有中序遍历的，我们先来看先序遍历，先序遍历先访问根，再以先序遍历根的各个子树

这个跟二叉树的先序遍历类似，都是递归的定义

我们很容易写出遍历的序列

最先访问整棵树的根结点

然后，以先序访问它的第一棵子树

再以先序访问第二棵子树

一直往后

后序遍历，先以后序遍历根的各个子树，各个子树以后序遍历完了之后，最后才去访问根

所以，后序序列，最后一个结点是整棵树的根

我们观察可以发现，树的先序遍历等价于它对应着的二叉树的先序遍历

这个原因，我们可以这样分析

比如，现在只选3个结点

A

B

C

假设，这3个结点在树当中，是这样的关系

那么，它转换成对应的二叉树

应该是这样，B的下一个兄弟是C

我们对左边这棵树进行先序遍历

那么，得到的序列一定是A在最前面，B和C谁在前呢

因为是BC

B是在C的前面的

一个是第一个孩子

一个是第二个孩子

所以，B在C前面

右边这样一棵二叉树

只有以先序遍历，才会得到相同的序列

所以，这二者的先序序列是一样的

现在我们再来看

树的后序遍历

它却等价于对应二叉树的中序遍历

这个稍微有点不一样

为什么对树进行后序遍历

它等价于对对应的二叉树进行中序遍历呢

我们采用同样的分析方法

ABC，在树当中，是这样的

它对应着的二叉树，是这样的

首先，树的后序遍历得到的序列

是BCA，那么，我们先看这里的BC，B是出现在C的前面的

要对对应的二叉树进行什么样的遍历

才能保证B出现在C前面呢？可以是先序遍历

但先序遍历，A出现在最前面

跟这个不一样

所以，它不是先序遍历

还有一种

就是中序遍历

也能保证B出现在C前面

因为，B的左子树为空

然后到B

然后再到右子树C，最后

到A，因为BC是作为A的左子树的，所以我们会发现，树的后序遍历

实际上对应着二叉树的中序遍历

我们来看森林的遍历，森林，刚才已经说过了

是由若干棵不相交的树构成的集合

比如，这个森林

它由3棵树构成

我们对森林进行遍历

第一种，先序

它很简单

依次以先序遍历

各个树，就可以了

先以先序遍历第一棵树

再以先序遍历第二棵树，一直往后

第二种遍历方式

后序，以后序遍历各个树

先以后序遍历第一棵树，再以后序去遍历

第二棵树，一直往后，有一些资料

把这种遍历方式称为森林的中序遍历

为什么会这样定义呢

我们先以X序来称这种遍历方式

我们以X序，遍历首棵树除根外的子树森林

比如，第一棵树

它除了根A外

剩下3棵树，BCD

也就是，先以某一种序遍历

首棵树除根外的

这3棵树，说明根最后访问

对于这棵树来说，不就是后序遍历吗

这跟我们前面讲的树的后序遍历，是一致的

然后，再以X序遍历

剩下的这些树

它认为

访问第一棵树的根的位置，是在这两个递归的步骤之间

所以，它认为是中序遍历

实际上

我认为把它理解成后序遍历，更简单一些

因为，这跟前面的树的后序遍历是一致的

依次以后序遍历各个树，就可以了

如果我们把这样一个森林，转换成对应的二叉树

前面我们已经讲过了转换的方法

就是采用第一个孩子、下一个兄弟这种方式来转换

我们会发现

对森林的先序遍历与对

对应的二叉树的先序遍历是一致的

这个我们已经分析过了，同样

对森林的后序遍历

它跟二叉树的中序遍历是对应的

那原因呢

其实跟我们刚才讲的类似

我们可以这样想

我们可以把这3棵树，把它们合并成一个虚拟的

唯一的一棵树

比如，这是第2棵树

这是第3棵树

我们认为这3棵树的根，隶属于一个不存在的

父结点，比如X

现在，这个森林就变成了一棵树

对这棵树进行后序遍历

不就是我们前面讲的

对对应的二叉树

进行中序遍历吗