首页 > 代码库 > 大话数据结构(十三)——树的理论知识

大话数据结构(十三)——树的理论知识

1、树的定义

树(Tree)是n(n>=0)个结点的有限集。

n=0时称为空树。

在任意一棵非空树中:

(1)有且仅有一个特定的称为根(root)的结点。

(2)当n>1时,其余结点可以分为m(m>0)个互不相交的有限集T1,T2,T3……Tm,其中每个集合本身又是一棵树,并且称为根的子树(SubTree)。

1.1 结点分类

树的结点包含一个数据元素及若干指向其子树的分支。

(1)结点拥有的子树数称为结点的度(Degree)。

(2)度为0的结点称为叶结点(leaf)或者终端结点;度不为0的结点称为非终端结点或分支结点。

(3)除了根结点之外,分支结点也称为内部结点。

(4)树的度是树内各结点的度的最大值。

1.2 结点间的关系

结点的子树的根称为该结点的孩子(child)。同样地,该结点称为 孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。

结点的祖先是从根到该结点所经分支上的所有结点。反之,以某结点为根的子树中的任一结点都称为该结点的子孙。

1.3 树的其他相关概念

结点的层次(level)从根开始定义起,根为第一层,根的孩子为第二层。若某结点在第i层,则其子树的根就在第i+1层。其双亲在同一层的结点互为堂兄弟。

树中结点的最大层次称为树的深度(Depth)或高度。

如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称为该树为有序树,否则称为无序树。

森林(Forest)是m(m>=0)颗互不相交的树的集合。对于树中每个结点而言,其子树的集合即为森林。

对比线性表和树结构,它们有很多的不同:

线性表:

第一个数据元素:无前驱;最后一个数据元素:无后继;中间元素:一个前驱一个后继

树结构:

根结点:无双亲,唯一;叶结点:无孩子,可以多个;中间结点:一个双亲多个孩子。

2、树的存储结构

树的存储结构不能用简单的顺序存储结构来实现。但是,可以充分利用顺序存储结构和链式存储结构的特点,完全可以实现对树的存储结构的表示。

这里要介绍三种不同的表示法:双亲表示法、孩子表示法、孩子兄弟表示法。

2.1 双亲表示法

以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点在数组中的位置。也就是说结点不仅知道自己是who,还知道它的parent在哪。

表示为

data parent

 

其中,data是数据域,存储结点的数据信息,而parent是指针域,存储该结点的双亲在数组中的下标。约定根结点的为位置域设置为-1,这意味着我们所有的结点都存有它的双亲的位置。

技术分享

 

这样的存储结构,我们可以根据结点的parent指针很容易找到它的双亲结点,所用的时间复杂度为O(1),直到parent为-1,表示找到了树结点的根。

那么,如果我们要是想知道结点的孩子是什么,我们可以增加一个结点最左边孩子的域,不妨叫它长子域,这样就可以很容易得到结点的孩子。如果没有孩子的结点,这个长子域不妨设为-1.

技术分享

若我们关注各兄弟之间的关系,可以增加一个右兄弟域来体现兄弟关系,每一个结点如果它存在右兄弟,则记录右兄弟的下标,如果不存在,记录为-1。

技术分享

存储结构的设计是一个非常灵活的过程,一个存储结构设计是否合理,取决于基于该存储结构的运算是否合适、是否方便,时间复杂度好不好等。

2.2 孩子表示法

由于树中每个结点可能有很多棵子树的根结点,我们把这种方法叫做多重链表表示法。不过,树的每个结点的度是不同的,所以设计两种方案解决。

2.2.1 方案一:指针域的个数等于树的度。

data child1 child2 child3

 

……

childd

 

 

 

其中,data是数据域,child1到childd是指针域,用来指向该结点的孩子结点。

技术分享

缺点:浪费空间,有些结点的指针域都是空的,

2.2.2 方案二:每个结点指针域的个数等于该结点的度,取一个位置专门存储结点指针域的个数

data degree child1 child2 …… childd

 

其中,data是数据域,degree是度域,也就是存储该结点的孩子结点的个数,child1到childd为指针域,指向该结点的各个孩子的结点。

技术分享

缺点:带来时间上的浪费

2.2.3 优化的结构

孩子表示法:把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点,则此单链表为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中。

技术分享

为此,设计两种结点结构。一个是孩子链表的的孩子结点,如

child next

 

其中,child是数据域,用来存放某个结点在表态数组中的下标,next是指针域,用来存储向某结点的下一个孩子结点的指针。

另一个是表头数组的表头结点,

data firstchild

 

其中,data是数据域,存储某结点的数据信息,firstchild是头指针域,存储该结点的孩子链表的头指针。

还有一种可以遍历双亲的,称为双亲孩子表示法

技术分享

2.3 孩子兄弟表示法

任何一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。

data firstchild rightsib

 

其中,data是数据域,firstchild为指针域,存储该结点的第一个孩子结点的存储地址,rightsib是指针域,存储该结点的右兄弟结点的存储地址。

 

大话数据结构(十三)——树的理论知识