树

树(Tree)是n(n>=0)个结点的有限集。在一棵非空树中：
(1) 有且仅有一个特定的称为根的结点;
(2) 当n>1时其余结点可分为m(m>0)个互不相交的有限集T1,T2...Tm,其中,每一个集合
本身 又是一棵树, 并且称为根的子树(subtree)例如,在图6.1中,(a)是只有一个根
结点的树;(b)是有 13个结点的树,其中A是根,其余结点分成三个互不相交的子树：

　　树是一种数据结构 : Tree=(D,R) 其中：D是具有相同特性的数据元素的集合；若D只含一个数据元素,则R为空集,否则R是D上个二元关系的集合，即R={H}。H为如下描述二元关系：

• (1) 在D中存在发唯一的称为根的数据元素,它在关系H下无前驱;
• (2) 若D-{root}≠φ，则存在D-{root}的一个划分D1,D2,...Dm(m>0),对任意一对j≠k ??? (l<=j,k<=m)有Dj∩Dk=φ，且对任意的i(l<=i<=m)，唯一存在数据元素Xi∈Di，有 ∈H;
• (3) 对应于D-{root}的划分，H-{ ,..., }有唯一的一个划分H1,H2,...，Hm(m>0),对任意一对j≠k(l<=j,K<=m)有，Hj∩Hk=φ，且对任意的i(l<=i<=m)Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。

一、树的基本术语
　　　　　　　
　　 1.