树——基础

1. 前言

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

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

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

2. 树的定义

    树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：
    (1)有且仅有一个特定的称为根(Root)的结点；
    (2)其余的结点可分为m(m≥0)个互不相交的子集T_l，T₂，…，T_m，其中每个子集本身又是一棵树，并称其为根的子树(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） 有序树中，同一组兄弟结点从左到右有长幼之分。
    对这一关系加以延拓，规定若k₁和k₂是兄弟，且k₁在k₂的左边，则k_l的任一子孙都在k₂的任一子孙的左边，那么就定义了树中结点之间的横向次序。