程序员人生网站导航

数据结构 - 树和森林表示与遍历

栏目：数据库应用时间：2015-05-19 08:32:33

双亲表示法(顺序存储结构)

      用1组连续的存储空间来存储树的结点，同时在每一个结点中附加1个唆使器(整数域) ，用以唆使双亲结点的位置(下标值) 。数组元素及数组的类型定义以下：

＃define MAX_SIZE  100
typedef  struct PTNode
{  ElemType  data ;
int  parent ;
}PTNode ;

typedef  struct
{  PTNode  Nodes[MAX_SIZE] ;
int  root;    /*  根结点位置  */
int  num ;   /*  结点数   */ 
}Ptree ;

所示是1棵树及其双亲表示的存储结构。这类存储结构利用了任1结点的父结点唯1的性质。可以方便地直接找到任1结点的父结点，但求结点的子结点时需要扫描全部数组。

孩子链表表示法

2 孩子链表表示法
树中每一个结点有多个指针域，每一个指针指向其1棵子树的根结点。有两种结点结构。
⑴ 定长结点结构
指针域的数目就是树的度。
其特点是：链表结构简单，但当树中各结点的度相差很大时，指针域的浪费明显。但如果树的各结点的度相差很小时，那开辟的空间被充分利用了，这类存储结构的缺点就变成了优点。
结点结构

⑵ 不定长结点结构（按需分配）
树中每一个结点的指针域数量不同，是该结点的度。没有过剩的指针域，但操作不便。
优点：空间利用率提高了
缺点：各个结点的链表结构不相同，实现起来比较困难；
其次要保护结点的度的值，运算上会带来时间的消耗。

⑶ 复合链表结构
（顺序存储+链式存储）
具体办法是：把所有结点放到1个顺序存储的数组中，然后将每一个结点的孩子结点排列起来，用单链表作存储结构（由于每一个结点的孩子数不肯定）。

    n个结点的树有n个（孩子）单链表(叶子结点的孩子链表为空)；
   n个头结点又组成1个线性表，采取顺序存储结构，寄存进1个1维数组中。

设计两种结点结构：
表头数组的表头结点: (firstchild存储该结点的孩子链表的头指针）；
孩子链表的表结点：(childno用来存储某个结点在表头数组中的下标，next指向下1个孩子）。

数据结构类型定义

数据结构类型定义以下：

＃define  MAX_NODE  100
typedef  struct  listnode
{   int   childno ;    /*  孩子结点编号  */
struct listno  *next ;
}CTNode;    /*  表结点结构  */
typedef  struct
{  ElemType   data ;
CTNode  *firstchild ;
}HNode;    /*  头结点结构  */

typedef  struct
{  HNode   nodes[MAX_NODE] ;
int  root;    /*  根结点位置  */
int  num ;   /*  结点数   */
}CLinkList;    /*  头结点结构  */
复合链表结构点评：
优点：便于查找结点的孩子或结点的兄弟
缺点：查找某结点的双亲需遍历整棵树

孩子兄弟表示法(2叉树表示法)

3 孩子兄弟表示法(2叉树表示法)

  树有以下特点：任意1棵树，它的结点的第1个孩子如果存在就是唯1的，它的兄弟如果存在也是唯1的。因此，设置两个指针，分别指向该结点的第1个孩子和它的右兄弟结点。结点类型定义以下：

typedef  struct   CSnode
{  ElemType   data ;
struct   CSnode *firstchild, *nextsib ;
}CSNode;

孩子兄弟表示法点评：
便于查找某个结点的孩子
通过firstchild找到该结点的长子，然后通太长子结点的nextsib找到次子……直到找到要找的孩子。
难以找到双亲
解决办法：增加1个双亲parent指针域

森林与2叉树的转换

     由于2叉树和树都可用2叉链表作为存储结构，对照各自的结点结构可以看出，以2叉链表作为媒介可以导出树和2叉树之间的1个对应关系。

◆ 从物理结构来看，树和2叉树的2叉链表是相同的，只是对指针的逻辑解释不同而已。
◆ 从树的2叉链表表示的定义可知，任何1棵和树对应的2叉树，其右子树1定为空。

树转换成2叉树
对1般的树，可以方便地转换成1棵唯1的2叉树与之对应。其详细步骤是：
⑴ 加虚线。在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。
⑵ 去连线。除最左的第1个子结点外，父结点与所有其它子结点的连线都去掉。
⑶ 旋转。将树顺时针旋转450，原本的实线左斜。
⑷ 整型。将旋转后树中的所有虚线改成实线，并向右斜

3 森林转换成2叉树
当1般的树转换成2叉树后，2叉树的右子树必为空。若把森林中的第2棵树(转换成2叉树后)的根结点作为第1棵树(2叉树)的根结点的兄弟结点，则可导出森林转换成2叉树的转换步骤以下：
1、把每棵树转换为2叉树
2、按给出的森林中树的次序，第1棵树不动，从第2棵树开始，顺次把后1棵树的根结点作为前1棵2叉树的根结点的右孩子，用线连起来，当所有的2叉树连接起来后，就得到了由森林转换来的2叉树。

树和森林的遍历

这里写图片描述
1 树的遍历
由树结构的定义可知，树的遍历有2种方法。
⑴ 先序遍历：先访问根结点，然后顺次先序遍历完每棵子树。如图的树，先序遍历的次序是：
ABCDEFGIJHK
⑵ 后序遍历：先顺次后序遍历完每棵子树，然后访问根结点。如图的树，后序遍历的次序是：
CDBFGIJHEKA
说明：
◆ 树的先序遍历实质上与将树转换成2叉树后对2叉树的先序遍历相同。
◆ 树的后序遍历实质上与将树转换成2叉树后对2叉树的中序遍历相同。
2 森林的遍历
设F={T1, T2,?,Tn}是森林，对F的遍历有2种方法。
⑴ 先序遍历：按先序遍历树的方式顺次遍历F中的每棵树。
⑵ 中序遍历：按中序遍历树的方式顺次遍历F中的每棵树。

------分隔线----------------------------

上一篇 Laravel blade 模板积累

下一篇 MyEclipse建立树形结构包

------分隔线----------------------------