树的基本概念

1. 树的定义

树 ( tree ) 是由n ( n ≥ 0 ) 个结点（或元素）组成的有限集合 ( 记为T )。

（1）如果n=0，它是一棵空树，这是树的特例。

（2）如果n>0，这n个结点中有且仅有一个结点作为树的根结点，简称为根 ( root )，其余结点可分为m ( m ≥ 0 ) 个互不相交的有限集T1，T2，…，Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树 ( subtree )。

（3）树的定义是递归的

2. 树的抽象数据类型

3. 树的逻辑表示方法

（1）树形表示法

（2）文氏图表示法

（3）凹入表示法

（4）括号表示法

A( B(E, F), C(G(J)), D(H, I(K, L, M)))

每棵树对应一个形如 “根(子树1，子树2，…，子树m)” 的字符串，每棵子树的表示方式与整棵树类似，各子树之间用逗号分开。

4. 树的基本术语

结点的度：某个结点的子树的个数称为该结点的度( degree of node)。

树的度：树中所有结点的度中的最大值称为树的度(degree of tree)。通常将度为m的树称为m次树 ( m-tree )。如上图是一棵3次树。

分支结点：树中度不为零的结点称为非终端结点，又叫分支结点(branch)。

单分支结点：对于度为1的结点，其分支数（该结点的度）为1，被称为单分支结点。

双分支结点：对于度为2的结点，其分支数为2，被称为双分支结点，依此类推。

叶子结点：度为零的结点称为叶子结点(leaf)。

路径（或逆路径）

路径长度：路径长度(path length)是该路径所通过的结点数目减1(即路径上分支数目)。

孩子结点，双亲结点和兄弟结点：

在一棵树中，每个结点的后继结点被称为该结点的孩子结点(children)。相应地，该结点被称为孩子结点的双亲结点(parents)。具有同一双亲结点的孩子结点互为兄弟结点(sibling)。

子孙节点和祖先结点：

每个结点对应子树中的所有结点(除自身外)称为该结点的子孙结点(descendant)，把从根结点到达某个结点的路径上经过的所有结点(除自身外)称为该结点的祖先结点( ancestor)，（包括双亲结点）。

结点层次（或结点深度）：结点层次(level)或结点深度(depth)是从树根开始定义的，根结点为第一层，它的孩子结点为第二层，依此类推，一个结点所在的层次为其双亲结点的层次加1。

树的高度（或树的深度）：树中结点的最大层次称为树的高度(height of tree)或树的深度(depth of tree)。

有序树和无序树：

若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树 ( ordered tree )，否则称为无序树 ( unordered tree )。一般情况下，如果没有特别说明，默认树都是指有序树。

森林：n ( n > 0 ) 个互不相交的树的集合称为森林。

把含有多棵子树的树的根结点删去就成了森林(forest)。给m ( m > 1) 棵独立的树加上一个根结点，并把这m棵树作为该结点的子树，则森林就变成了一棵树。

5. 树的性质

（1）树中的结点数 = 所有结点的度数之和+1

（2）度为 m 的树中第 i 层最多有个结点（i 1）.

（3）高度为 h 的 m 次树最多有个结点

（4）具有 n 个结点的 m 次树的最小高度为（取上阶）

6. 树的基本运算（主要讨论二叉树的基本运算）

• 寻找满足某种特定条件的结点，如寻找当前结点的双亲结点等。
• 插入或删除某个结点，如在树的指定结点上插入一个孩子结点或删除指定结点的第 i 个孩子结点等。
• 遍历 ( traversal ) 树中的所有结点。

•  先根遍历 ( preorder traversal )

（1）访问根结点;

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

例如，对于上图所示的树,采用先根遍历得到的结点序列为 ABEFCGJDHlKLM。从中可以看出,先根遍历序列的第一个元素即为根结点对应的结点值。

• 后根遍历 ( postorder traversal )

（1）按照从左到右的顺序后根遍历根结点的每一棵子树;

（2）访问根结点。

例如,对于上图所示的树，采用后根遍历得到的结点序列为 EFBJGCHKLMIDA。从中可以看出,后根遍历序列的最后一个元素即为根结点对应的结点值。

• 层次遍历 ( level traversal )

（1） 从根结点开始按从上到下、从左到右的次序访问树中的每一个结点。

例如,对于上图所示的树，采用层次遍历得到的结点序列为ABCDEFGHIJKLM。从中可以看出，层次遍历序列的第一个元素即为根结点对应的结点值。

7. 树的存储结构

• 双亲存储结构（parent storage structure）——顺序存储结构
  

类型说明如下：

typedef struct
{
  ElemType data;  //存放节点的值 
int parent;  //存放双亲的位置 
} PTree[MaxSize];

每个结点的位置是按照从上到下、从左到右、从 0 开始标记的（即按层次遍历标记），其中根节点的双亲结点位置设置为 -1。

优点：求某节点的双亲结点容易

缺点：求某个节点的孩子结点时需要遍历整个存储结构

• 孩子链存储结构（child chain storage structure）

类型说明如下：

typedef struct node
{
  ElemType data;  //结点的值 
struct node *son[MaxSize];  //指向孩子节点 
}TSonNode;

优点：查找某节点的孩子结点方便

缺点：查找某节点的双亲结点比较费时，当树的度较大时存在较多的空指针域

• 以孩子链作为存储结构，设计一个求树 t 高度的递归算法。

int TreeHeight1(TSonNode *t)
{
  TSonNode *p;
int i, h, maxh = 0;
if(t == NULL)  //空树返回高度0 
return 0;
else
  {
for(i = 0; i < MaxSize; i++)
    {
      p = t->son[i];  //p指向t的第 i+1 个孩子结点 
if(p != NULL)  //若存在第 i + 1 个孩子结点 
      {
        h = TreeHeight1(p); //求出对应子树的高度 
if(maxh < h)
          maxh = h;
      }
    }
return (maxh + 1);
  }
}

• 孩子兄弟链存储结构（child brother chain storage structure）

类型说明如下：

typedef struct tnode
{
  ElemType data;  //结点的值 
struct tnode *hp;  //指向兄弟结点 
struct tnode *vp;  //指向孩子结点 
}TSBNode;

优点：可方便的实现树和二叉树的相互转换

缺点：寻找双亲结点比较麻烦

• 以孩子兄弟链作为存储结构，设计一个求树 t 高度的递归算法。

int TreeHeight2(TSBNode *t)
{
  TSBNode *p;
int h, maxh = 0;
if(t == NULL)
return 0;
else
  {
    p = t->vp;  // p 指向第一个孩子结点 
while(p != NULL)
    {
      h = TreeHeight2(p);  //求p子树的高度 
if(maxh < h)
        maxh = h;
      p = p->hp;
    }
return (maxh +1);
  } 
} 
#当采用 孩子兄弟链存储结构时，树的算法同广义表的算法十分相似

转载请注明：XAMPP中文组官网 » 树的基本概念