[树](4)树和森林

▲重点记录树的表示以及遍历操作,并建立森林与二叉函数的对应关系(代码实操将在题集中演示)

树的存储结构

在大量的应用中,人们曾使用多种形式的存储结构来表示树,这里只记录最常用的三种存储结构

一、双亲表示法

假设以一组连续空间存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置,其形式说明如下:

typedef int TElemType;
typedef struct PTNode//结点结构
{
    TElemType data;
    int parent;//双亲位置域
}PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int r, n;//根的位置和结点数
}PTree;

如右图所示,展示一棵树及其双亲表示的存储结构:

img树的双亲表示法示例

这种存储结构利用了每个结点(除根之外)只有惟一双亲的性质,PARENT(T,x)操作可以在常量时间内实现,反复调用PARENT操作,知道遇见无双亲的结点时,并找到了树的根,这就是ROOT(x)操作的执行过程

但是,在这种表示法中,求结点的孩子时需要遍历整个结构

二、孩子表示法

由于树中每个结点可能又多棵子树,则可用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根结点,此时链表中的结点可以有如下两种结点格式:

img

若采用第一种结点格式,则多重链表中的结点是同构的,其中d为树的度,由于树种很多结点的度小于d,所以链表中有很多空链域

若采用第二种结点格式,则多重链表中的结点是不同构的,其中d为结点的度,degree域的值同d。

此时,虽能节约存储空间,但是操作不方便

另一种办法是把每个结点的孩子结点排列起来,看成是一个线性表,且以单链表作存储结构,则n个结点有n个孩子链表(叶子的孩子链表为空表),而n个头指针又组成一个线性表,为了便于查找,可采用顺序存储结构

这种存储结构可形式的说明如下:

typedef struct CTNode {//孩子结点
    int child;
    struct CTNode* next;
}*ChildPtr;
typedef struct {
    TElemType data;
    ChildPtr Firstchild;//孩子链表头指针
}CTBox;
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;//结点树和根的位置
};

下图是孩子表示法,与双亲表示法相反,孩子表示法便于那些涉及孩子的操作的实现,却不适用于PARENT(T,x)操作,我们可以把双亲表示法孩子表示法结合起来,即将双亲表示和孩子链表合在一起

img按升序排列:
1、一般树
2、上述树的孩子链表
3、上述树的带双亲孩子链表

孩子兄弟表示法(二叉链表示法)

又称为二叉树表示法,或二叉链表表示法,则以二叉链表作树的存储结构,链表中结点的两个域分别指向该结点的第一个孩子结点和下一个兄弟结点,分别命名为:fristchild域和nexrsibling域

img

typedef struct CSNode{
    TElemType data;
    struct CSNode* fristchild;
    struct CSNode* nextchild;
}CSNode,*CSTree;

下图为上述树的孩子兄弟链表,利用这种存储结构便于实现各种树的操作,首先易于实现找孩子结点等的操作

img

则只要先从firstchild域找到第一个孩子结点,然后沿着孩子结点的nextsibling域连续走i-1步,便可以找到x的第i个孩子,当然,如果为每个结点增设一个PARENT域,则同样能方便的实现PARENT(T,x)操作。

森林与二叉树的转换

由于二叉树和树都可用二叉链表作存储结构,则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系,也就是说,给定一棵树,可以找到唯一的一棵二叉树与之对应

从物理结构来看,他们的二叉链表是相同的,只是解释不同而已,下图直观的展示了树与二叉树之间的对应关系

img

从树的二叉链表表示法的定义可以得知,任何一棵树和树对应的二叉树,其右子树必空,若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟,则同样可以导出森林和二叉树的关系

如下图所示:

img

这个一一对应的关系导致森林或树与二叉树可以相互转换,其形式定义如下:

1、森林转换成二叉树

  • 如果F={T1,T2,...,Tm}是森林,则可按如下规则转换成一棵二叉树B=(root,LB,RB)
  • 若F为空,则m=0,则B为空树
  • 若F非空,即m!=0,

则B的根root即为森林中第一棵树的根ROOT(T1)

  • B的左子树LB是从T1中根节点的子树森林F1={T11,T12,T13...,T1m1}转换而来的二叉树
  • 其右子树RB是从森林F’={T2,T3,...,Tm}转换而成的二叉树

2、二叉树转换成森林

  • 如果B=(root,LB,RB)是一棵二叉树则可按如下规则转换成森林F={T1,T2,T3}
  • 若B为空,则F为空
  • 若B非空,则F中

第一课树Ti的根ROOT(Ti)即为二叉树B的根root

  • T1中根结点的子树森林F1是由B的左子树LB转换而来的森林
  • F中除了T1之外,其余树组成的森林F'={T2,T3,...,Tm}是由B的右子树RB转换而来的森林

从上述递归定义容易写出相互转换的递归算法,同时,森林和树的操作亦可转换成二叉树的操作来实现(操作看题集,这边只记录思路)

树和森林的遍历

由树结构的定义可引出两种次序遍历树的方法:

  • 一种是

先根(次序)遍历树

    • 即:先访问树的根结点,然后依次先根遍历根结点的每棵子树
    • 另一种是

    后根(次序)遍历

    • 即:先依次后根遍历没棵子树然后返回根结点

    如下图:

    img**结论:树转换成二叉树,只是为了其操作方便
    、而不能乱了树结点的次序和结构层次**

    按照森林和树相互递归的定义,我们可以推出森林的两种遍历方法:

    • 先序遍历森林
    • 若森林非空,则可按下述规则遍历之

      1. 访问森林中第一棵树的根结点
      2. 先序遍历第一棵树中根节点的子树森林
      3. 先序遍历除去第一课树之后剩余树构成的森林
    • 中序遍历森林
    • 若森林非空,可按向下述规则遍历之

      1. 中序遍历森林中第一课树的根节点的子树森林
      2. 访问第一课树的根结点
      3. 中序遍历除去第一棵树之后剩余树构成的森林

    img

    从上我们可以知道:树和森林转换为二叉树,只是为了简化其操作,而不能影响原本树和森林的性质和特性,更不能改变其结构。

    当森林转换成二叉树时,其第一课树的子树森林转换成左子树,剩余树的森林转换成右子树,则上述森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历

    本文链接:

    https://nullcode.fun/43.html
    1 + 6 =
    快来做第一个评论的人吧~