1. 前言

    树形结构是一类重要的非线性结构。树形结构是结点之间有分支,并具有层次关系的结构。它非常类似于自然界中的树。

树结构在客观世界中是大量存在的,例如家谱、行政组织机构都可用树形象地表示。

树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程。

2. 树的定义

    树(Tree)是n(n≥0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:
(1)有且仅有一个特定的称为根(Root)的结点;
(2)其余的结点可分为m(m≥0)个互不相交的子集Tl,T2,…,Tm,其中每个子集本身又是一棵树,并称其为根的子树(Subree)。

注意:

树的递归定义刻画了树的固有特性:一棵非空树是由若干棵子树构成的,而子树又可由若干棵更小的子树构成。

树的示例-家族树:在现实生活中,有入如下血统关系的家族可用树形图表示:

  • 张源有三个孩子张明、张亮和张丽;
  • 张明有两个孩子张林和张维;
  • 张亮有三个孩子张平、张华和张群;
  • 张平有两个孩子张晶和张磊。

图 家族树

以上表示很像一棵倒画的树。其中"树根"是张源,树的"分支点"是张明、张亮和张平,该家族的其余成员均是"树叶",而树枝(即图中的线段)则描述了家族成员之间的关系。显然,以张源为根的树是一个大家庭。它可以分成张明、张亮和张丽为根的三个小家庭;每个小家庭又都是一个树形结构。

 

3. 树的基本概念

树形表示:用一个圆圈表示一个结点,圆圈内的符号代表该结点数据信息,结点之间的关系通过连线表示。虽然每条连线上都不带箭头,但它仍然是有向的,其方向隐含着从上向下,即连线的上方结点是下方结点的前驱,下方结点是上方结点的后继。

下图给出了树的逻辑表示,它形如一棵倒长的树。图a是空树,一个结点都没有。图b是只有一个根结点的树,它没有子树。图c是有13个结点的树,其中A是根结点,它一般画在树的顶部。其余结点分成3个互不相交的子集:T0={B,E,F,K,L},T1={C,G},T2={D,H,I,J,M},它们都是根结点A的子树。再看T0,它的根是B,其余根结点又分为2个互不相交的子集T00={E,K,L},T01={F},它们是T0的子树。

图 树的示意图

下面介绍关于树的一些基本概念:

①结点:包含一个数据元素及若干指向其子树的分支。例如,在上图c的树总共13个结点。为方便起见,每个数据项用单个字母表示。

②结点的度:结点所拥有的子树的个数。例如,在图c所示的图中,根A的度为3,结点E的度为2,结点K,L,F,G,M,I,J的度为0。

③树的度:树中各结点的度的最大值。例如,图c所示的树的度为3。

④叶结点(终端结点):度为0的结点。例如,在图c所示的树中,{K,L,F,G,M,I,J}构成树的叶结点的集合。

⑤分支结点(非终端结点):除叶结点以外的结点(度不为0的结点)。例如,在图c所示的树中,A,B,C,D,E,H就是分支结点。

⑥子女结点:若结点x有子树,则子树的根结点即为结点x的子女。例如,在图c所示的树中,结点A有3个子女,结点B有2个子女,结点L没有子女。

⑦双亲结点:若结点x有子女,x即为子女的双亲。例如,在图c所示的树中,结点B,C,D有一个双亲A,根结点A没有双亲。

⑧兄弟结点:同一双亲的子女互称为兄弟。例如,在图c所示的树中,结点B,C,D成为兄弟,E,F也称为兄弟,但F,G,H不是兄弟。

⑨祖先结点:从根结点到该结点所经分支上的所有结点。例如,在图c所示的树中,结点L的祖先为A,B,F。

⑩子孙结点:某一结点的子女,以及这些子女的子女都是该结点的子孙。例如,在图c所示的树中,结点B的子孙为E,F,K,L。

结点的层次:树中的每个结点都处在一定的层次上,即从根到该结点所经路径上的分支条数。例如,在图c所示的树中,根结点在第1层,它的子女结点在第2层,依次类推,树中任意一结点的层次为它的双亲结点的层次加1。

树的高(深)度:树中结点所处的最大层次,空树的高度为0,只有一个根结点的树的高度为1。例如,在图c所示的树中,树的高度为4。

有序树:树中各结点的子树是按照一定的次序从左向右排列的,且相对次序是不能随意变换的。

无序树:树中各结点的子树是没有一定的排列次序,且相对次序是可以随意变换的。

森林:n(n≥0)个互不相交的树的集合。删去一棵非空树的根结点,树就变成森林;反之,若增加一个根结点,让森林中每一棵树的根结点都变成它的子女,森林就成为一棵树。

4. 树的表示

    树的逻辑表示方法可以分为四种:树形表示法、文氏图表示法、广义表表示法和凹入表示法。

   

(1)树形表示法:图形表示法是最常用的一种表示法,它能直观、形象地表示出数的逻辑结构,能够清晰地反映出树中结点之间的逻辑关系。树中的结点使用圆圈表示,结点间的关系使用直线表示,位于直线上方的结点是双亲结点,直线下方的结点是孩子结点。

(2)文氏图表示法:文氏图表示是利用数学中的集合的图形化表示来描述树的逻辑关系。

(3)广义表表示法:采用广义表的形式表示的树的逻辑结构,广义表的子表表示结点的子树。

(4)凹入表示法:凹入表示法类似于书的目录,章、节、小节、逐个凹入。

5. 树的基本操作

(1)InitTree(&T);

操作结果:构造空树T。

(2)DestroyTree(&T);

初始条件:树T存在。

操作结果:销毁树T。

(3)CreateTree(&T,definition);

初始条件:definition给出树T的定义。

操作结果:按definition构造树T。

(4)ClearTree(&T);

初始条件:树T存在。

操作结果:将树T清为空树。

(5)TreeEmpty(T);

初始条件:树T存在。

操作结果:若T为空树,则返回TRUE,否则返回FALSE。

(6)TreeDepth(T);

初始条件:树T存在。

操作结果:返回树T的深度。

(7)Root(T);

初始条件:树T存在。

操作结果:返回树T的根。

(8)Value(T,e);

初始条件:树T存在,e是T中某个结点。

操作结果:返回e的值。

(9)Assign(T,e,value);

初始条件:树T存在,e是T中某个结点。

操作结果:结点e赋值为value。

(10)Parent(T,e);

初始条件:树T存在,e是T中某个结点。

操作结果:若e是T的非根结点,则返回它的双亲,否则返回"空"。

(11)LeftChild(T,e);

初始条件:树T存在,e是T中某个结点。

操作结果:若e是T的非叶子结点,返回e的最左子女。否则返回"空"。

(12)RightSibling(T,e);

初始条件:树T存在,e是T中某个结点。

操作结果:若e有右兄弟,返回e的右兄弟,否则返回"空"。

(13)InsertChild(&T,&p,i,c);

初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度+1,非空树c与T不相交。

操作结果:插入c为T中p所指结点的第i棵子树。

(14)DeleteChild(&T,&p,i);

初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度。

操作结果:删除T中p所指结点的第i棵子树。

(15)TraverseTree(T,Visit());

初始条件:树T存在,Visit是对结点操作的应用函数。

操作结果:按某种次序对T的每个结点调用函数Visit一次且仅一次。一旦Visit()失败,则操作失败。

6. 树形结构的逻辑特征

树形结构的逻辑特征可用树中结点之间的父子关系来描述:
(1) 树中任一结点都可以有零个或多个直接后继(即孩子)结点,但至多只能有一个直接前趋(即双亲)结点。
(2) 树中只有根结点无前趋,它是开始结点;叶结点无后继,它们是终端结点。
(3) 祖先与子孙的关系是对父子关系的延拓,它定义了树中结点之间的纵向次序。
(4) 有序树中,同一组兄弟结点从左到右有长幼之分。
对这一关系加以延拓,规定若k1和k2是兄弟,且k1在k2的左边,则kl的任一子孙都在k2的任一子孙的左边,那么就定义了树中结点之间的横向次序。