【笔记】树的表示与实现

• 树的抽象数据型
• 树的表示
• 树的实现

1.树的抽象数据型

  与二叉树一样，在树上规定如下基本操作，可以把树定义成抽象数据型。

• Parent(n,T)：返回树T结点n的父亲。若n是根，则返回空。
• LeftMostChild(n,T)：返回树T结点的最左儿子。
• RightSibling(n,T)：返回树T结点n的右兄弟。
• Data(n,T)：返回树T结点n的DATA域的值。
• Create(v,T1,T2,…,Tk)：建立DATA域为v的根结点r，此结点有k颗子树T1,T2,…,Tk，且T1,T2,…,Tk是自左而右排列的。返回以r为根的树；若k=0，则r既是根也是叶结点。
• Root(T)：返回树T的根结点。

  通常可以对树定义3种遍历顺序，假设各子树记为T1,T2,…,Tk。则树的遍历定义如下：

  （1）先根顺序

• 访问根结点。
• 先根顺序遍历T1
• 先根顺序遍历T2
  …
• 先根顺序遍历Tk
• 退出

  （2）中根顺序

• 中根顺序遍历T1
• 访问根结点。
• 中根顺序遍历T2
  …
• 中根顺序遍历Tk
• 退出

  （3）后根顺序

• 后根顺序遍历T1
• 后根顺序遍历T2
  …
• 后根顺序遍历Tk
• 访问根结点。
• 退出

  树的先根遍历算法：

void PreOrder(node n,TREE T)
/*按先根顺序列出树T中结点n及其所有后代的数据域的值*/
{
    node c;
    visit(Data(n,T));
    c=LeftMostChild(n,T);
    while(c!=NULL)
    {
        PreOrder(c,T);
        c=RightSibling(c,T);
    }
}

  如果要按先跟顺序遍历整棵树T，则只要调用PreOrder(Root(T),T)即可。

2.树的表示

树的数组表示

  设T是一棵树，其中的结点命名为1，2，3，…，n。根据树中每个结点只有一个父亲这个特性，可用数组A来表示树T。令数组的下标对应于结点名，数组元素A[i]定义如下：

A[i]={j,0,若结点i的父亲是j若结点i是根

  这种表示法除根结点外，每个结点只有一个指向其父亲结点的链域。所以有时把这种表示法称为树的父链表示法或单链表示法。

  一般来说，Parent(i)=A[i]。数组元素由parent和data两个域构成。可以把上图表示的树的结构描述为：

struct node
{
    int parent;
    char data;
};
typedef node TREE[11];
TREE T;

  这种只有父链的表示方法，对于求父结点及祖先结点都很方便。但对于给定的结点n，欲求其子结点的信息相当困难，也不能反映各兄弟结点的顺序。但是如果在给结点命名时，可按照这样一种顺序：对每个结点n，在对n进行编号之后，按自左而右递增的顺序依次对n的儿子进行编号。在此假设之下，将很容易实现RightSibling和LeftMostChild。

typedef int node;
typedef node TREE[maxnodes];
node LeftMostChild(node n,TREE T)
{
    node i;
    for(i=n+1;i<=maxnodes-1;i++)
        if(T[i]==n)
            return i;
    return 0;
｝

树的邻接表表示

  树的一种重要表示法是每个结点的所有子结点形成一个线性表，但因每个结点所具有的子结点个数不同，所以通常都采用链接式表示。
  上图中的树为例可以表示为下图所示。其中有一个数组header，每一个数组元素header[i]是一个表头结点，指向结点i的儿子结点链表的首结点。对于每个结点i，由header[i]出发，可以很容易地将其全部儿子结点找到。

  邻接表的类型说明：

typedef int node;
struct celltype
{
    node element;
    celltype *next;
};
typedef celltype *LIST;
typedef celltype *position;
struct TREE
{
    LIST header[maxnodes];
    datatype data[maxnodes];
    node root;
};

  用树的这种表示法实现LeftMostChild操作：

node LeftMostChild(node n ,TREE T)
{
    LIST L;
    L=T.header[n];
    if(Empty(L))
        return 0;
    else
        return(Retrieve(First(L),L));
}

树的左右链表示法

  通常，可以按照其自然形式，令每个结点除其信息域外，设置多个链域，使它们指向相应的儿子结点，但这样会使每个结点占用的空间较多。为了节省每个结点所占用的空间，在每个结点中只设置两个链域，令左链指向最左儿子，右链指向紧挨它的右兄弟，树的这种存储表示方法称为树的左右链表示法，也称为树的左兄弟右儿子表示法或者树的二叉链表表示法。这种表示法很容易实现由较小的树来构造较大的树。

  其存储结构为：

struct 
{
    datatype data;
    int leftchild;
    int rightsibling;
}cellspace[maxnodes];

  用树的左右链表示法，很容易实现除Parent操作以外的各种操作。如果希望有效地实现Parent操作，即快速地找到一个结点的父结点，则在每个结点中增加指向父结点的链域。

struct
{
    datatype data;
    int leftchild;
    int rightsibling;
    int parent;
}cellspace[maxnodes];

  此外，还可以选择这样一种结构：令最右儿子的rightsibling域指向右父亲，于是必须对每个结点增加一个标志位，用于区别其rightsibling域是指向兄弟还是指向父亲。在求一个结点的父亲时，只需沿着rightsibling域查到虚线的指向即可。这比在每一个结点中增加parent域可节省控件，但花费的时间稍多一些。

• 树不能为空的理由
  

  如果在设计的体系中定义了森林，同伙私又允许树为空， 那么由于森林是由若干颗树构成的，很可能出现一个集合（森林）包含许多空集（树），或者一个空集（森林）包含许多个空集（树）的情况。如果允许树为空，则很难确定森林中的一颗空树对应于什么样的二叉树，两颗空树对应于什么样的二叉树。

3.树的实现

源码参见树的实现