程序员人生 网站导航

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

栏目:数据库应用时间: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中的每棵树。

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

最新技术推荐