树与森林

一、树的存储结构

(一)双亲表示法

树的双亲表示法主要描述的是结点的双亲关系,如下图所示:

树的双亲表示法:
树的双亲表示法

C++ 类型定义如下:

#define MAXSIZE 100

class TreeNode {
  public:
    DataType data;
    int parent;
};

class Tree {
  public:
    TreeNode elem[MAXSIZE];
    int n;      //树中当前的结点数目
};

从图中可看出,这种表示法采用的是顺序存储。它的特点是寻找结点的双亲很容易,但寻找结点的孩子比较困难。

(二)孩子表示法

孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定,所以利用链式存储结构更加适宜。对每个结点建立一个链表,链表中的元素就是头结点的孩子。n 个结点就有 n 个链表,如何管理这些链表呢?最好的方法是将这些链表的头结点放在一个一维数组中。上图树的双亲表示法所示的树可存储为以下结构:

孩子表示法:
孩子表示法

该存储结构用C++描述如下:

const int MAXSIZE = 100  //MAXSIZE 为数组最大容量

class link {
  public:
    int child;     //孩子序号
    link *next;    //下一个孩子指针
};

class node {
  public:
    DataType data;   //结点信息
    link *first;    //指向第一个孩子
};

class tree{
  public:
    int n;      //结点个数
    node T[MAXSIZE];
};

从图孩子表示法中可看出,对每个结点建立一个链表,所有链表的表头用顺序存储结构。这种存储结构的特点是寻找某个结点的孩子比较容易,但寻找双亲比较麻烦。所以,在必要的时候,可以将双亲表示法和孩子表示法结合起来,即将一维数组元素增加一个表示双亲结点的域 parent,用来指示结点的双亲在一维数组中的位置。

(三)孩子兄弟表示法

孩子兄弟表示法也是一种链式存储结构。它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系,其结点结构如下图所示:

树孩子兄弟表示法结点结构:
树孩子兄弟表示法结点结构

其中,firstchild 为指向该结点第一个孩子的指针,nextbrother 为指向该结点的下一个兄弟, elem 是数据元素内容。上图树的双亲表示法所示的树可存储以下结构:

树孩子兄弟表示法
树孩子兄弟表示法

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

从树的孩子兄弟表示法可以看到,如果设定一定规则,就可用二叉树结构表示树和森林。这样,对树的操作实现就可以借助二叉树存储,利用二叉树上的操作来实现。接下来将讨论树、森林与二叉树之间的转换方法。

(一)树转换为二叉树

对于一棵无序树,树中结点的各孩子的次序是无关紧要的,而二叉树中结点的左、右孩子结点是有区别的。为避免发生混淆,约定树中每一个结点的孩子结点按从左到右的次序编号。如下图所示的一棵树,根结点 A 有 B、C、D 3 个孩子,可以认为结点 B 为 A 的第一个孩子结点,结点 C 为 A 的第二个孩子结点,结点 D 为 A 的第三个孩子结点。

一棵树
一棵树

将一棵树转换为二叉树的方法如下:

  1. 树中所有相邻兄弟之间加一条线
  2. 对树中的每个结点,只保留它与第一个孩子结点之间的连线,删去它与其他孩子结点之间的连线。
  3. 以树的根结点为轴心,将整棵树顺时针转动一定的角度,使之结构层次分明。

可以证明,树进行这样的转换所构成的二叉树是唯一的。下图给出了转换示意图:

树转换为二叉树的转换过程示意图
树转换为二叉树的过程示意图

由上面的转换可以看出,在二叉树中,左分支上的各结点在原来的树中是父子关系,而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟,所以变换后的二叉树的根结点的右孩子必为空。

事实上,一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。

由上面的转换可以看出,在二叉树中,左分支上的各结点在原来的树中是父子关系,而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟,所以变换后的二叉树的根结点的右孩子必为空。

事实上,一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。

(二)森林转换为二叉树

由森林的概念可知,森林是若干棵树的集合。只要将森林中各棵树的根视为兄弟,每棵树又可以用二叉树表示。这样,森林也同样可以用二叉树表示。

森林转换为二叉树的方法如下。

  1. 将森林中的每棵树转换成相应的二叉树。

  2. 第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子。当所有二叉树连起来后,此时所得到的二叉树就是由森林转换得到的二叉树。

这一方法可形式化描述为:

如果 F={T1,T2,…,Tm}是森林,则可按如下规则转换成一棵二叉树 B=(root,LB,RB)

  1. 若 F 为空,即 m=0,则 B 为空树。

  2. 若 F 非空,即 m≠0,则 B 的根 root 即为森林中第一棵树的根 Root(T1);B 的左子树 LB 是从 T1中根结点的子树森林 F1={T11,T12,…,T1m}转换而成的二叉树;其右子树 RB 是从森林 F ={T2,T3,…,Tm}转换而成的二叉树。

下图所示为森林及其转换为二叉树的过程:

森林及其转换为二叉树的过程示意图

(三)二叉树转换为树和森林

树和森林都可以转换为二叉树。二者不同的是,树转换成的二叉树,其根结点无右分支,而森林转换后的二叉树,其根结点有右分支。显然,这一转换过程是可逆的,即可以依据二叉树的根结点有无右分支,将一棵二叉树还原为树或森林,具体方法如下。

  1. 若某结点是其双亲的左孩子,则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来;

  2. 删去原二叉树中所有的双亲结点与右孩子结点的连线;

  3. 整理由 1、2 两步所得到的树或森林,使之结构层次分明。

这一方法可形式化描述为:

如果 B=(root,LB,RB)是一棵二叉树,则可按如下规则转换成森林 F={T1,T2,…,Tm}。

  1. 若 B 为空,则 F 为空;

  2. 若 B 非空,则森林中第一棵树 T1的根 root(T1)即为 B 的根 root;T1中根结点的子树森林 F1是由 B 的左子树 LB 转换而成的森林;F 中除 T1之外的树组成的森林 F’={T2,T3,…,Tm}是由 B 的右子树 RB 转换而成的森林。

下图为一棵二叉树还原为森林的过程示意图:

二叉树还原为森林的过程示意图

三、树和森林的遍历

同二叉树一样,对树和森林最常见的操作也是遍历。

(一)树的遍历

树的遍历通常有以下两种方式。

  1. 先根遍历

    先根遍历的定义为:

    • 访问根结点;

    • 按照从左到右的顺序先根遍历根结点的每一棵子树。

    按照树的先根遍历的定义,对图一棵树所示的树进行先根遍历,得到的结果序列为:

    A B E F C D G

  2. 后根遍历

    后根遍历的定义为:

    • 按照从左到右的顺序后根遍历根结点的每一棵子树。

    • 访问根结点。

    按照树的后根遍历的定义,对图一棵树所示的树进行后根遍历,得到的结果序列为:

    E F B C G D A

根据树与二叉树的转换关系以及树和二叉树的遍历定义可以推知,树的先根遍历与其转换的相应二叉树的先序遍历的结果序列相同;树的后根遍历与其转换的相应二叉树的中序遍历的结果序列相同。因此,树的遍历算法是可以采用相应二叉树的遍历算法来实现的。

(二)森林的遍历

森林的遍历有前序遍历和后序遍历两种方式。

  1. 前序遍历

    前序遍历的定义为:

    • 访问森林中第一棵树的根结点;

    • 前序遍历第一棵树的根结点的子树;

    • 前序遍历去掉第一棵树后的子森林。

  2. 后序遍历

    后序遍历的定义为:

    • 后序遍历第一棵树的根结点的子树;

    • 访问森林中第一棵树的根结点;

    • 后序遍历去掉第一棵树后的子森林。

这两种遍历方法基于树的遍历,具体的例子不再给出。

用户头像
登录后发表评论