3
7.1.1 树的定义
树是由 n(n≥0) 个结点构成的集合。 n = 0 的树称为空树;
对 n>0 的树 T 有:
(1) 有一个特殊的结点称为根结点, 根结点没有前驱结
点;
7.1 树
4
(2) 当 n>1 时, 除根结点外其他结点被分成 m(m>0) 个互
不相交的集合 T
1
, T
2
,…, T
m
, 其中每一个集合 T
i
(1≤i≤
m) 本身又是一棵结构和树类同的子树。
显然树是递归定义的。 因此, 在树结构 ( 以及二叉树结
构 ) 的算法中将会频繁地出现递归。
树结构表示了数据元素之间的层次关系。 图 7 - 1 是一个
树的例子, 其中图 7 - 1(a) 是一棵只有根结点的树, 图 7 - 1
(b) 是一棵有 12 个结点的一般的树。
5
图 7 - 1 树的示例
(a) 只有根结点的树; (b) 一般的树