数据结构C语言实现10.树

引言

　　前面我们介绍了的线性表，栈和队列等数据结构都属于线性结构，他们的共同特点是：各元素之间逻辑关系呈现出简单的一对一关系．而非线性结构的各元素之间，其逻辑关系则呈现出一对多或多对多的关系．
　　树形结构是一类重要的非线性结构，其逻辑关系呈现出一对多的关系．树形结构中元素(结点)之间具有明确的层次关系．元素(结点)之间有分支，非常类似与自然界的树．
　　
在計算機科學中，树（tree）是一种抽象資料型別（ADT）或是實作這種抽象資料型別的資料結構，用來模擬具樹狀結構性質的資料集合。
它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

它具有以下的特点：

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；

---

一．树的基本术语

下面介绍树形结构中常用的基本术语：

1. 树的节点：包含一个数据元素，及若干指向其子数的分支．

2. 节点的度：一个节点含有的子树的个数称为该节点的度；//如上图中Ｂ的节点的度为3,Ａ的节点的度为2,Ｐ的节点的度为0；

3. 树的度：一棵树中，最大的节点的度称为树的度；即各个节点度的最大值；//上图中，树的度为３；

4. 叶子，叶节点或终端节点：度为零的节点；//如Ｐ；

5. 非终端节点或分支节点：度不为零的节点；//如Ｃ；

6. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；//DEF是B的孩子．

7. 双亲，父亲节点或父节点：若一个节点ｉ含有子节点ｊ，则这个节点ｉ称为其子节点ｊ的父节点；

8. 兄弟节点：具有相同父节点的节点互称为兄弟节点；//ＢＣ的父节点都是Ａ，所以ＢＣ互为兄弟．

9. 节点的祖先：从根到该节点所经分支上的所有节点均为该节点的祖先；//图中所示树中ABE是J的祖先．

10. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

11. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；若某节点在Ｌ层，则其子树的根在第L+1层．

12. 树的高度或深度：树中节点的最大层次；//所示树深度为５；

13. 堂兄弟节点：父节点在同一层的节点互为堂兄弟；

14. 森林：由m（m>=0）棵互不相交的树的集合称为森林；

15. 有序树或无序树：若树中每个节点各个子树从左到右的次序不能互换，则称该树为有序树，否则为无序树．

    二．树的分类

–

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
• 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
  • 二叉树：每个节点最多含有两个子树的树称为二叉树；
    • 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
      • 满二叉树：所有叶节点都在最底层的完全二叉树。
    • 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树。
    • 排序二叉树(二叉查找树（Binary Search Tree），也称二叉搜索树、有序二叉树)
  • 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
  • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树
    　　

三．树的表示

　　树的表示方法有以下4种，各用于不同的目的。

• 1. 树形表示法
  　　　　树的树形(直观)表示法就是以倒着的分支树的形式表示，就是一棵树的直观表示。其特点就是对树的逻辑结构的描述非常直观，是数据结构中最常用的树的描述方法。
  

• 2. 嵌套集合表示法
  　　所谓嵌套集合是指对于一些集合，其中任何两个集合，或者不相交，或者一个包含另一个。用嵌套集合的形式表示树，就是将根结点视为一个大的集合，其若干梯子树构成这个大集合中若干个互不相交的子集，如此嵌套下去，即构成一棵树的嵌套集合表示。因图(a)就是这棵树的嵌套集合表示。
  

• 3. 广义表表示法
  　　树用广义表表示，就是将根作为由于树森林组成的表的名字写在表的左边，这样依次将树表示出来。图(b)就是图的广义表表示。
  　　 　　

• 4. 凹入表示法
  　　树的凹入表示法如图(c)所示。树的凹入表示法主要用于树的屏幕和打印输出。
  　　

  四．树的存储结构

• -

I. 双亲链表表示法

　双亲链表表示法利用树中每个结点的双亲唯一性，在存储结点信息的同时，为每个结点附设一个指向其双亲的指针parent，惟一地表示任何-棵树。

　1. 双亲链表表示法的实现

　　　方法① 用动态链表实现
　　　方法② 用向量表示——更为方便

　2. 双亲链表向量表示的形式说明

    　#define MAXSIZE 100     //向量空间的大小，由用户定义
    　typedef char DataType； //应由用户定义
    　
    　typedef struct
    　{
    　    　DataType data；   //结点数据
    　    　int parent；      //双亲指针，指示结点的双亲在向量中的位置
    　}PTreeNode；
    　
    　typedef struct
    　{ 
    　    　PTreeNode nodes[MAXSIZE];
    　    　int n；           //结点总数 
    　}PTree；
    　
    　PTree T；              //T是双亲链表

　 注意：
　　若T.nodes[i].parent = j，则T.nodes[i]的双亲是T.nodes[j]。

　3. 双亲链表表示实例

　　双亲链表表示如下面数组所示。

　　分析：
　　　E和F所在结点的双亲域是1，它们的双亲结点在向量中的位置是1，即B是它们的双亲。
　　注意：
　　　　1. 根无双亲，其parent域为-1。
　　　　2. 双亲链表表示法中指针parent向上链接，适合求指定结点的双亲或祖先(包括根)；求指定结点的孩子或其它后代时，可能要遍历整个数组。

II.孩子链表表示法

　1 结点结构

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

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

　2 孩子链表表示法

　　　孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。

　 　<1>. 孩子链表表示法的类型说明 　

//以下的DataType和MAXSIZE由用户定义
typedef struct CNode{    //子链表结点
    int child；          //孩子结点在向量中对应的序号
    struct CNode *next；
}CNode；
  
typedef struct{ 
    DataType data；     //存放树中结点数据
    CNode *firstchild； //孩子链表的头指针
}PTNode；

typedef struct{
    PTNode nodes[MAXSISE]；
    Int n，root；       //n为结点总数，root指出根在向量中的位置
}CTree；

Ctree T； //T为孩子链表表示

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

　 　＜2＞. 孩子链表表示法实例
　 　【例】图示树的孩子链表表示T如下面所示。
　　　　

　　　　　
　 注意：
　 　1. 孩子结点的数据域仅存放了它们在向量空间的序号。
　 　2. 与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。
　 　3. 将双亲链表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。
　　　上面的(b)图就是用双亲链表表示法来存储图中的树。

　*III. 孩子兄弟链表表示法 *

　 　1. 表示方法
　　　在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域leftmostchild和rightsibling，即可得树的孩子兄弟链表表示。

　 　2. 表示实例
　　　　【例】图中树的孩子兄弟链表如下图所示。
　　　
　　　
　 　注意：
　　　　这种存储结构的最大优点是：它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。

总结：

　　　树，是数据结构中非常重要的非线性结构．
　　　我们将对其具体情况做更深入的探究，例如我们将对二叉树的各种操作做详细研究，比如遍历啦，搜索啦～