数据结构与算法 －树

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

树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。 树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。

树的定义

树是n(n>=0)个结点的有限集，递归是树的固有特性。

当n=0时，称为空树。当n>0时，有且仅有一个特定的称为根的结点；其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集Ti又是一棵树，并称其为子树。

树的逻辑表示

1. 一般表示法

2. 文氏图法

3. 嵌套括号法

4. 凹入法表示

树的相关术语

1. 结点：由一个数据元素及若干指向其它结点的分支所组成。

2. 度：分为节点的度和树的度。节点的度是该节点的子树数量，即分支的数量。树的度是树中节点的最大值。

3. 叶子：度为零的结点。

4. 非终端结点：度不为零的结点。

5. 孩子：结点的子树的根称为该结点的孩子。

6. 双亲：一个结点称为该结点所有子树根的双亲。

7. 祖先：结点祖先指根到此结点的一条路径上的所有结点。

8. 子孙：从某结点到叶结点的分支上的所有结点称为该结点的子孙。

9. 兄弟：同一双亲的孩子之间互称兄弟。

10. 结点的层次：从根算起，根为第一层，其孩子在第二层, ….， L层上任何结点的孩子都在L+1层上。

11. 堂兄弟：其双亲在同一层的结点。

12. 树的深度：树中结点的最大层次。

13. 有序树：若树中各结点的子树从左到右是有次序的， 不能互换，称为有序树。

14. 无序树：若树中各结点的子树是无次序的， 可以互换，则成为无序树。

15. 森林：是 m(≥0) 棵树的集合。

树的基本运算

1. 求根 Root(T)：求树T的根结点。

2. 求双亲 Parent(T,X)：求结点X在树T上的双亲； 若X是树T的根或X不在T上，则结果为一特殊 标志。

3. 求孩子 Child(T,X,i)：求树T上结点X的第i个孩子 结点；若X不在T上或X没有第i个孩子，则结 果为一特殊标志。

4. 建树 Create(X,T1 ,…,Tk ),k>1：建立一棵以X为根， 以T1 ,…,Tk为第1,…,k棵子树的树。

5. 剪枝 Delete(T,X,i)：删除树T上结点X的第i棵子 树；若T无第i棵子树，则为空操作。

6. 遍历 TraverseTree(T)：遍历树，即访问树中每个 结点，且每个结点仅被访问一次。