树图

第三讲 树（Tree）

树型结构是一类重要的非线性结构，树型结构是结点之间有分支，并具有层次关系的结构，它非常类似于自然界中的树。树型结构在客观世界中是大量存在的，例如家谱、行政组织结构都可用树形象的表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序语法结构；在数据库系统中，可以用树来组织信息。

从本讲开始重点讲解什么是树和二叉树，下一讲将和大家共同讨论二叉树遍历。 一、 树的概念：

在现实生活中，存在很多可用树型结构描述的实际问题，例如，某家族的血统关系如下：张源有三个孩子张明、张亮和张丽；而张明有两个孩子张林和张维；张亮有三个孩子张平、张华和张君；张平有两个孩子张晶和张磊。这个家庭关系可以很自然地用图一所示的树型图来描述，它很象一倒画的树。其中“树根”是张源，树的“分支点”是张明、张亮和张平，该家族的其余成员均是“树叶”，而树枝则描述了家族成员之间的关系。显然，以张源为根的树是一个大家庭。它可以分成张明、张平为根的三个

张亮和小

家

庭；每个小家庭又都是一个树型结构。由此可抽象出树的递归定义。

图一

定义：树（Tree）是n（n＞0）个结点的有限集合T，它满足如下两个条件：

（1）、有且仅有一个特定的称为根（Root）的结点； （2）、其余的结点可分为m（m≥0）个互不相交的有限集合T1，T2，…，Tm，其中每个集合又是一棵树，并称其为根的子树（Subtree）。

注意：有的文献为了方便，也将n＝0的空集合定义为空树。

在树的树型图表示中，结点通常是用圆圈表示的，结点

名字一般是写在圆圈旁边见图二，有时也可以写在圆圈内。

树的递归定义刻化树的固有特性，即一种树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。用该定义来分析图二所示的树，它是由结点有限集T＝｛A，B，C，D，E，F，G，H，I，J｝所构成。其中A是根结点，T中其余结点，可分成三个互不相交的子集；T1＝｛B，E，F， I，J｝，T2＝｛C｝，T3＝｛D，G，H｝；T1，T2和T3是根结点A的三棵子树，且本身又都是一棵树，例如T1，其根为B，其余结点可分为两个互不相交的子集T11＝｛E｝和T12＝｛F，I，J｝，它们都是B的子树。T11是只含有一个根结点E的树；而T12的根F有两棵互不相交的子树｛I｝和｛J｝，其本身有都是只含有一个结点的树。对T1和T3也可以进行类似的分析。

（a）树型表示法 （b）集合表示法

图二

下面给出树结构中常用的基本术语，其中有许多术语借用了家族树中的一些习惯用词。

一个结点的子树个数称为该结点的度（Degree）。一棵树的度是指该树中结点最大度数。度为零的结点称为叶子（Leaf）或终端结点。如图二中，A、B、E的度分别为3、2、0。树的度为3，C、E、G、H、I和J均为叶子。度不为零的结点或非终端结点，除根据结点之外的分支结点统称为内部结点。

树中某个结点子树之根称为该结点孩子（Child）或儿子，相应地，该结点称为孩子的双亲（Parents）或父亲。如图二中，B是结点A的子树T1的根，故B是A的孩子，而A是B的双亲。同一个双亲的孩子称为兄弟（Sibling）。如图二中，B、C、D互为兄弟。

若树中存在一个结点序列k1，k2，…，kj，使得ki是ki+1的双亲（1≤i