2. 树和森林

2. 树和森林

1. 树和森林定义

树：是$n(n \ge 0)$ 个结点的有限集。若$n=0$, 称为空树；

• 若$n=0$, 则是空树

• 若$n \gt 0$ , 有且仅有一个特定的称为根(root)的结点；

  ​ 其余结点可以分为$m(m\ge0)$个互不相交的有限集$T1, T2, \cdots, Tm$

森林： 是$m (m \ge 0)$棵互不相交的树的集合。

2. 树的存储结构

1. 双亲表示法，找双亲简单，找孩子难。

实现：定义结构数组，存放树的结点，每个结点含两个域

• 数据域：存放结点本身信息
• 双亲域：指示本结点的双亲节点在数组中的位置

如下表所示，表示出树的结构如图所示。其中 -1代表没有双亲节点

数组索引	存储数据	双亲节点在数组中的位置
0	R	-1
1	A	0
2	B	0
3	C	0
4	D	1
5	E	1
6	F	3
7	G	6
8	H	6
9	K	6

1. 孩子链表

把每个节点的孩子节点排列起来，看成是一个线性表，用单链表存储n个节点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，用顺序表（含n个元素的结构数组）存储。特点是：找孩子任意，找双亲难。

• 孩子节点结构由：child自身和下一个节点位置 next组成
• 双亲节点结构由： data本身和第一个孩子表头指针 firstchild

跟上表一样的树用孩子链表表示为：

1. 带双亲的孩子链表

2. 孩子兄弟表示法

实现：用二叉链表做树的存储结构，链表中每个节点的两个指针域分布指向其第一个孩子节点和下一个兄弟节点。

图示该表示法的树的存储结构，其中左边指向第一个孩子节点，右边指向相邻的第一个兄弟节点， ^表示空。

3. 树与二叉树的转换

• 将树转化为二叉树处理，利用二叉树的算法来实现对数的操作
• 由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出数与二叉树直接的一个对应关系。

如下图中，对于一棵树，我们可以将其用二叉链表存储，按照上面规则解释，也可将其按照二叉树规则解释。这样左边的树就有与之对应的右边二叉树。

直接将树转化为二叉树：

1. 加线：在兄弟间加一条线
2. 抹线：对每个节点，除了其左孩子外，去除其余其余孩子之间的关系
3. 旋转：以数的根节点为轴心，将整树顺时针旋转45°。

树变二叉树口诀：兄弟相连留长子。示例如下图

逆过程：二叉树变树，记下口诀： 左孩右右连双亲，去掉原来右孩线。

4. 森林与二叉树转化

森林转化为二叉树：

1. 将每棵树分别转换为二叉树
2. 将每棵树的根节点用线相连
3. 以第一棵树的根节点为二叉树的根，再以根节点为轴心，顺时针旋转，构成二叉树结构

简单来说，就是先将树变为二叉树，再将其根相连，口诀：树变二叉根相连。

具体看如下图例子，我们看到根为AEG三棵树组成的森林。

1. 按照树转化为二叉树规则，将其根连接起来，去兄弟，只保留长子
   • 如BCD连起来，再去掉兄弟节点连续，只保留长子
   • EF就变成E为根，F为左子树
   • GHIJ就连接HI，去掉GI连线
2. 将形成的3棵二叉树的根AEG连接，顺时针旋转得到二叉树结构

二叉树转化为森林：

1. 抹线：将二叉树中根节点与其右孩子连线，及沿着有分支搜索到的所有右孩子间连线全部抹掉，使其变为孤立的二叉树
2. 还原：将孤立二叉树还原为树

如下图所示，

5. 树与森林的遍历

树的遍历（三种方式，没有中序遍历）

• 先根遍历：若树不空，先访问根节点，然后依次先根遍历各棵子树
• 后根遍历：若树不空，先依次后根遍历各棵子树，然后访问根节点
• 层次遍历：若树不空，则自上而下自左而右访问树中的每个节点

如下图所示树结构，

1. 先根遍历：ABCDE
2. 后根遍历：BDCEA
3. 层次遍历：ABCED

森林的遍历：

森林遍历可以分为3个部分组成：

1. 森林中第一棵树的根节点
2. 森林中第一棵树的子树森林
3. 森林中其他树构成的森林

比如，先序遍历：

1. 若森林不空，先访问森林中第一棵树的根节点
2. 先序遍历森林中第一棵树的子树森林
3. 先序遍历森林中除第一棵树之外其余树构成的森林。

中序遍历：若森林不空，

1. 中序遍历第一棵树的子树森林
2. 访问第一棵树的根节点
3. 中序遍历森林中除第一棵树之外其余树构成的森林。

如下图中森林遍历如下：

先序遍历：ABCDEFGHIJ

中序遍历：BCDAFEHJIG