树

定义

树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。n=1的结点称为根（root）结点；
（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、······、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree），如下图所示。

图1-1

树表示方法

1.嵌套集合表示
2.广义表表示
3.凹入表示法
4.层次结构表示（如上图1-1显示那样）

树相关基本术语

树的结点

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree）例如图1-1中A的度为2，D的度数为3，H的度数为0.度数为0的结点称为叶子（Leaf）或终端结点。例如图1-1中的G、H、I、J、F都是树的叶子。度数不为0的结点称为非终端结点或分支结点。除根节点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。例如图1-1中树的度为3。结点的子树称为该结点的孩子（Child），相应的，该结点称为孩子的双亲（Parent）。例如图1-1中B和C均是A的孩子，A是B和C的双亲。同一个双亲的孩子之间互称兄弟（Sibling）。例如B和C之间互称兄弟，G、H、I之间互称兄弟。

结点的层次

结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树的根就在第l+1层。其双亲在同一层次的结点互为堂兄弟。例如图1-1中D、E、F是堂兄弟，G、H、I、J也是堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度，当前树的深度为4。
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林

森林（Forest）是m（m>=0）棵互不相交的树的集合。

线性表和树

线性结构	树结构
第一个数据元素：无前驱	根结点：无双亲，唯一
最后一个数据元素：无后继	叶结点：无孩子，可以多个
中间元素：一个前驱一个后继	中间结点：一个双亲多个孩子