树与二叉树(2)

[toc]

树的存储结构

　　树的存储结构有两种，线式存储 和 链式存储，灵活使用这两种存储结构，具有如下五种存储方式：

• 双亲表示法，一种顺序(线式)表示法
• 孩子表示法，一种链式表示法
• 孩子链表表示法，结合线式存储和链式存储的混合表示方式
• 带双亲的孩子链表表示法，结合线式存储和链式存储的混合表示方式
• 二叉链表(孩子 - 兄弟)存储表示法，一种链式存储方式

双亲表示法

　　这是一种顺序表示法，使用一维数组存储树中的节点，每个存储单元存储节点的值及其双亲节点在数组中的下标值。下面的树 T 使用双亲表示法存储示意图：


树T

树T的双亲表示法





　　对树的根节点使用特殊值 -1 进行标识，一般情况下，使用此种方式存储时，在存储结构中还会存储根节点的位置 r 和树中节点的个数 n。 在这种存储方式中，孩子节点的关系是隐含的，即具有相同 parent 值的节点具有相同的双亲节点，使用这种方式访问孩子节点的效率不高。

孩子表示法

　　这是一种典型的使用链式存储的表示方法，每个节点具有固定的格式，假设树 T 的度为 n,则用来存储树 T 的每个存储单元便有 n 个指针域，指向其孩子节点，如果没有孩子节点，则为空。如树 T₁，其度为3，则其对应的存储单元的结构如下
　　
　　
　　

　　

　　使用此种方式，存在有大量的空指针域，空间利用效率不高。
　　针对上述的问题，有了另外的一种存储结构，根据节点的度动态设置每个节点的指针域的个数，如下示：
　　
　　
　　使用这种存储结构的树 T₁ 如下示：
　　

孩子链表表示法

　　这种方式混合使用线性存储和链式存储的方式，此种存储方式的存储单元有两种，一种是表头节点点，存储有节点的值的数据域 Data 以及指向其第一个孩子节点的指针域 First,如果没有孩子节点，则指针域为空，另外一种是孩子节点，存储有当前孩子节点在表头数组中的序号的 child 以及指向下一个孩子节点的指针域 next.其中的表头数组是一个存储表头节点的一维数组。

树 T 及其表头节点数组：

使用该种存储方式可以很方便的访问孩子节点，但却不方便对节点的双亲节点进行访问。

带双亲的孩子链表表示法

　　针对孩子链表表示法不方便对节点的双亲节点进行访问的问题，在表头节点中增加一个数据域存储当前节点的双亲节点在表头数组中的序号。这便是带双亲的孩子链表表示法。

孩子兄弟表示法

　　此种表示方式使用二叉链表的结构对树进行存储，每个存储单元设置有一个数据域用于存储当前节点的值，还有两个指针域，分别指向当前节点左边的第一个孩子和其右边的第一个兄弟。
　　其节点的存储单元如下示：
　　

　　上面的树 T 的二叉链表表示法示意图如下：
　　
　　在这种表示方式中，如果要查找一个节点的所有孩子节点，需要先通过左孩子指针找到其第一个孩子节点，然后沿着第一个孩子节点的有兄弟指针一直找下去，直至节点的右兄弟指针为空。

树与二叉树的转换

将树转换为二叉树

　　将一棵树转换为二叉树，需要经过三个步骤

1. 加线。在树的兄弟节点之间一次加一连线
2. 抹线。每个节点除左孩子外的与其余孩子间的连线全部抹掉
3. 旋转。将整棵树以树的根节点为轴心顺时针旋转45^o

　　例如，对于如下的树 T，

　　要将其转换为一棵二叉树。
　　第一步，在每个节点的兄弟节点间添加一条线，即B、C、D、E、F、G、H、I 之间添加一条线，添加后如图示：
　　

　　第二步，抹去每个节点除左孩子外与其它孩子节点间的连线，即抹去图中的 A-C、A—D、B-F、B-G 和 D-I ，抹去后如图所示：
　　

　　第三步，将整棵树顺时针旋转45^o,最终的结果如下图：
　　

　　最终得到的二叉树的二叉链表就是这棵树的二叉链表。原来树中的兄弟关系转换为了二叉树中的双亲与右孩子的关系。
　　经转换，对于原来树的操作便可以转换为对其对应的二叉树的操作。

将二叉树转换为树

　　将二叉树转换为树，可以看作是将树转换为二叉树的逆操作，因此，也是需要经过三步来实现

1. 加线。若 P 节点是双亲节点的左孩子，则将p的右孩子，右孩子的右孩子，以及沿分支找到的所有的右孩子，都与 P 的双亲节点添加一条线连接起来。其目的在于回复孩子与双亲的关系。
   
   
2. 抹线。抹去原二叉树中双亲节点与其右孩子间的连线。因为其原为树中的兄弟节点不需要连线，可以视为是将树转换为二叉树中加线的逆操作。
   
   
3. 调整节点的层次结构，形成树结构

　　对于上面经转换得到的二叉树，如果需要将其回复为原来的树，则需要经过三步。
　　第一步，加线。需要在 A - C，A - D、B - F，B - G、D - I 之间添加连线
　　
　　第二步，抹线。需要抹去原二叉树中双亲节点与其右孩子节点间的连线，即需要抹去 B - C、C - D、E - F、F - G、H - I 之间的连线
　　
　　第三步，调整节点层次排列，即可得来原来的树 T

将森林转换为二叉树

　　将森林转换为二叉树，同样的需要经过三个步骤

1. 将森林中的每棵树转换为二叉树
2. 将得到的每棵二叉树的根节点用线连接起来
3. 将第一棵二叉树的根作为整棵二叉树的根，然后将整棵树以第一棵子树的根节点为轴心进行顺时针旋转

　　对于如下具有三棵子树的森林，先将其转换为一棵二叉树
　　
　　
　　第一步，将森林中的每棵树转换为二叉树
　　

　　第二步，将转换得到的二叉树的头结点连接起来

　　第三步，旋转
　　

将二叉树转换为森林

　　将二叉树转换为森林，需要经过两步。

1. 第一步，抹线，抹去根节点与其右孩子间的连线，及其沿右分支搜索到的所有右孩子的连线
   　　对于上一次转换得到的二叉树来讲，就是要抹去 A - E、E - G，便可得到三棵孤立的二叉树，如下
   　　
   　　
   
2. 第二步,将每棵二叉树转换为树，从而形成森林
   

树与森林的遍历

树的遍历

　　树的遍历要规定根与子树的访问顺序，以此为依据可以分为两类：先根遍历 和 后根遍历。
　　现有如下的树 T
　　
　　按照前面的将树转换为二叉树的方法，将T转换为二叉树如下所示：
　　

先根遍历

　　对于先根遍历的定义如下，
　　若树为空，则为空操作，否则执行如下步骤

1. 访问根节点
2. 依次先根遍历每棵子树

　　按照上面的定义，树 T 的先根遍历序列如下

先根遍历序列： R - A - D - E - B - C - F - G - H - K

通过观察分析可知，树 T 的先根遍历的序列等同于其对应的二叉树的先序遍历序列。

后根遍历

　　对于后跟遍历的定义如下：
　　若树为空，则为空操作，否则执行如下的操作
　　1. 依次后根遍历树的每棵子树
　　2. 访问树的根节点

　　按照上面的定义，树 T 的后根遍历序列如下

后根遍历序列：D - E - A - B - G - H - K - F - C - R

通过观察分析可知，树 T 的后根遍历的序列等同于其对应的二叉树的中序遍历序列。

森林的遍历

　　森林的遍历可以分为两种：先序遍历 和 中序遍历，对应的遍历序列与其相对应的二叉树的同名遍历序列相同。
　　现有森林 F 如下
　　
　　森林对应的二叉树 T如下
　　

先序遍历

　　森林的先序遍历规则如下：
　　如果森林为空，则空操作，否则执行如下的操作

1. 访问森林中第一棵树的根节点
2. 先序遍历第一棵树中根节点的子树森林
3. 先序遍历除去第一棵树后余下的其它的树组成的森林

　　森林 F 的先序遍历序列如下,等同于其所对应的二叉树的先序遍历序列

F 的先序遍历：A - B - C - D - E - F - G - H - I - J

中序遍历

　　森林的中序遍历规则如下：
　　如果森林为空，则空操作，否则执行如下的操作

1. 中序遍历第一棵树根节点的子树森林
2. 访问第一个树的根节点
3. 中序遍历除去第一棵树外其它树组成的森林

　　森林 F 的中序遍历序列如下，等同于其对应的二叉树的中序遍历序列

F 的中序遍历序列：B - C - D - A - F - E - H - J - I - G