1. 树的存储结构

    通常,树的存储结构有三种,双亲表示法、孩子表示法和孩子兄弟表示法。

(1)双亲表示法

双亲表示法是利用一组连续的存储单元存储树的每个结点,并利用一个指示器表示结点的双亲结点在树中的位置。

树的双亲表示法存储表示描述如下:

 

C代码  收藏代码
  1. #define MaxSize 200
  2. typedef struct PNode        /* 双亲表示法的结点定义 */
  3. {
  4.     DataType data;
  5.     int parent;                    /* 指示结点的双亲 */
  6. }PNode;
  7. typedef struct
  8. {
  9.     PNode node[MaxSize];
  10.     int num;                        /* 结点的个数 */
  11. }PTree;

 

图 树的双亲表示法

 

(2)孩子表示法

由于树中每个结点可能有多个孩子,所以自然想到用多重链表存储树。在这种多重链表的每个结点中除了用于存放数据信息的data域外,还有若干指针域,分别用于指向该结点的孩子结点。但是一棵树中,不同结点的度数是不同的,那么每个结点中到底需要多少个指针域呢?我们有如下二种方案:

① 定长结点

即树中每个结点均按树的度k来设置指针。n个结点的树一共有n*k个指针域,而树中只有n-1条边,故树中的空指针数目为kn-(n-1)=n(k-1)+1(k越大,浪费的空间越多)。

②不定长结点

即树中每个结点按本结点的度来设置指针数,并在结点中增设一个度数域degree指出该结点包含的指针数。各结点不等长,虽然节省了空间,但是给运算带来不便。

孩子结点表示法的类型定义如下:

C代码  收藏代码
  1. //以下的DataType和MaxTreeSize由用户定义
  2.     typedef struct CNode{//子链表结点
  3.         int child; //孩子结点在向量中对应的序号
  4.         struct CNode *next;
  5.       }CNode;
  6.     typedef struct{
  7.         DataType data; //存放树中结点数据
  8.         CNode *firstchild;//孩子链表的头指针
  9.       }PTNode;
  10.     typedef struct{
  11.         PTNode nodes[MaxTreeSize];
  12.         Int n,root; //n为结点总数,root指出根在向量中的位置
  13.       }CTree;
  14.     Ctree T; //T为孩子链表表示

注意:当结点T.nodes[i]为叶子时,其孩子链表为空,即T.nodes[i].firstchild=NULL。

(3)孩子兄弟表示法

孩子兄弟表示法,也成为树的二叉链表表示法。孩子兄弟表示法,采用链式存储结构,链表由一个数据域和两个指针域组成。其中,数据域存放结点的数据信息,一个指针域用来指示结点的第一个孩子结点,另一个指针域用来指示结点的下一个兄弟结点。

图 孩子兄弟表示法

树的孩子兄弟表示法的类型定义如下:

C代码  收藏代码
  1. /* 孩子兄弟表示法的类型定义 */
  2. typedef struct CSNode
  3. {
  4.     DataType data;
  5.     struct CSNode *firstchild, *nextsibling; /* 指向第一个孩子和下一个结点 */
  6. }CSNode, *CSTree;

 

2. 树、森林的遍历

(1)树的遍历

设树T如下图所示,结点R是根,根的子树从左到右依次为T1,T2,…,Tk

(1)树T的前序遍历定义:
  若树T非空,则:
①访问根结点R;
②依次前序遍历根R的各子树T1,T2,…,Tk

(2)树的后序遍历定义:
若树T非空,则:
①依次后序遍历根T的各子树Tl,T2,…,Tk
②访问根结点R。

【例】对下面的(a)图中的树进行前序遍历和后序遍历,得到的前序序列和后序序列分别是ABCDE和BDCEA。

图 树和对应的二叉树

注意:
① 前序遍历一棵树恰好等价于前序遍历该树对应的二叉树
② 后序遍历树恰好等价于中序遍历该树对应的二叉树。

(2)森林的遍历

(1)前序遍历森林
若森林非空,则:
①访问森林中第一棵树的根结点;
②前序遍历第一棵树中根结点的各子树所构成的森林
③前序遍历除第一棵树外其它树构成的森林。

(2)后序遍历森林
若森林非空,则:
①后序遍历森林中第一棵树的根结点的各子树所构成的森林;
②访问第一棵树的根结点;
③后序遍历除第一棵树外其它树构成的森林。
注意:
① 前序遍历森林等同于前序遍历该森林对应的二叉树
② 后序遍历森林等同于中序遍历该森林对应的二叉树
【例】对下面(a)图中所示的森林进行前序遍历和后序遍历,则得到该森林的前序序列和后序序列分别为ABCDEFICJH和BDCAIFJGHE。而(b)图所示二叉树的前序序列和中序序列也分别为ABCDEFICJH和BDCAIFJGHE。

图 森林和对应的二叉树

③ 当用二叉链表作树和森林的存储结构时,树和森林的前序遍历和后遍历,可用二叉树的前序遍历和中序遍历算法来实现。

 

3. 树、森林和二叉树的转换

    树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树;反之,任何一棵二叉树也能惟一地对应到一个森林或一棵树。

(1)树、森林到二叉树的转换

* 将树转换为二叉树
树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树:
①在所有兄弟结点之间加一连线;
②对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。
【例】下面(a)图所示的树可转换为(c)图所示的二叉树。

图 树转化为二叉树

注意:由于树根没有兄弟,故树转化为二叉树后,二叉树的根结点的右子树必为空。
* 将一个森林转换为二叉树
具体方法是:
① 将森林中的每棵树变为二叉树
② 因为转换所得的二叉树的根结点的右子树均为空,故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。
【例】下图中,左边包含三棵树的森林可转换为右边的二叉树。

图 森林转化为二叉树

(2)二叉树到树、森林的转换
把二叉树转换到树和森林自然的方式是:若结点x是双亲y的左孩子,则把x的右孩子,右孩子的右孩子,…,都与y用连线连起来,最后去掉所有双亲到右孩子的连线。
【例】下图的森林就是由二叉树转换成的。

图 森林转化为二叉树