第一节 树的基本概念和术语

二、树的定义

1、树(Tree)是n(n≥0)个结点的有限集T，n=0时称为空树，任意非空树

（1）有且仅有一个特定的称为根(Root)的结点；

（2）n>1时，除根结点外的其余结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。

2、从逻辑上看，树形结构具有以下特点：

（1）任何非空树中有且仅有一个结点没有前驱结点，这个结点就是树的根结点。

（2）除根结点之外，其余所有结点有且仅有一个直接前驱结点。

（3）包括根结点在内，每个结点可以有多个直接后继结点。

（4）树形结构是一种具有递归特征的数据结构。

（5）树形结构中的数据元素之间存在的关系通常是一对多，或者多对一的关系。

三、树的表示法

1、树结构

2、嵌套集合

3、凹形表示法

4、广义表表示法

（A（B（E，（F（J,K））），C（G），D（H，I）））

（1）结点的度：结点所拥有的子树的个数。如A的度为3，E的度为2。

（2）树的度：树中结点度的最大值。如图4-1所示的树的度为3。

（3）叶子（终端结点）：度为0的结点。如K，L，F，J等结点都是叶子结点。

（4）分支结点（非终端结点）：度不为0的结点。除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。如A，B、I等结点是分支结点。

（5）孩子：结点的直接后继（即结点的子树的根）。如B是A的孩子，N是I的孩子。

（6）双亲：结点的直接前趋。如B的双亲是A，N的双亲是I。

（7）兄弟：同一双亲的孩子互为兄弟。如B、C，D互为兄弟，M，N互为兄弟。

（8）子孙：一棵树上的任何结点（不包括根结点）称为根的子孙。如图中其它结点都是根结点A的子孙。

（9）祖先：从根结点开始到该结点连线上的所有结点（除该结点）都是该结点的祖先。如N的祖先是I，C，A。

（10）路径：若树中存在一个结点序列k1，k2，…，ki，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从kl到kj的一条路径或道路。路径的长度指路径所经过的边（即连接两个结点的线段）的数目，等于j-1。

注意：

若一个结点序列是路径，则在树的树形图表示中，该结点序列"自上而下"地通过路径上的每条边。

从树的根结点到树中其余结点均存在一条唯一的路径。

（11）结点的层：设根结点的层数为1，其余结点的层数等于双亲结点的层数加1。如B的层数是2，N的层数是4。

（12）树的高度（或深度）：树中所有结点层数的最大值。图所示的树的高度为4。

（13）有序树和无序树：将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树；否则称为无序树。

（14）森林：是m(m≥0)棵互不相交的树的集合。树和森林的概念相近，删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。

五、树的性质

性质一：非空树中的结点总数等于树中所有结点的度之和加1。

证明：

根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个双亲结点，即每个结点与指向它的一个分支结点一一对应，因而除了树的根结点之外的结点数等于树中所有结点的分支数（度数），由此可得知树中的结点总数应为所有结点的度之和加1。

性质二：度为k的非空树的第i层最多有k^{i -1}个结点（i≥1）。

证明：（略）

性质三：深度为h的k叉树最多有 个结点。

证明：

显然，只有当深度为h的k叉树上的每一层都达到该层最大结点总数时，该树的结点总数将达到最大，因此，有

证毕