树的定义

树是数据结构中的一种，其属于非线性数据结构。树（Tree）是n（）个结点的有限集；时称为空树。在任意一棵非空树中：1） 有且仅有一个特定的称为根（Root）的结点；2）当时，其余结点可分为m（）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

图1 树的示例

图1是使用树结构存储的集合{A, B, C, D, E, F, G, H, I, J, K, L, M}的示意图。对于数据A ，和数据B、C、D有关系；对于数据B，和E、F有关系。这就是“一对多”的关系。

将具有“一对多”关系的集合中的数据元素，按照图1中第一张图的形式进行存储，整个存储形状在逻辑结构上看，类似于实际生活中倒着的树（图1中第二张图），所以称这种存储结构为“树型”存储结构。

树的结点

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。树的度是树内各结点的度的最大值。

图2 结点的度

结点间的关系双亲和孩子：结点的子树的根称为该结点的孩子（Child），相应地该结点称为孩子的双亲（Parent）。如B的双亲是A，A的孩子有E和F。兄弟：同一个双亲的孩子之间互称为兄弟。例如H、I和J互为兄弟。祖先：从根到该结点所经分支上的所有结点都称为祖先。例如M的祖先为A、D和H。子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。例如B的子孙为E、K、L和F。堂兄弟：双亲在同一层的结点互为堂兄弟。例如结点G与E、F、H、I、J互为堂兄弟。树的层次和高度

结点的层次（Level）从根开始定义起，根为第一层，其孩子为第二层。若某结点在第层，则其子树的根就在第层。如图3中，D、E、F是堂兄弟，而G、H、I、J也是堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度，当前树的高度为4。

图3 树的高度

树的其他概念有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。森林：由 m（m >= 0）个互不相交的树组成的集合被称为森林。图 1（A）中，分别以 B、C、D 为根结点的三棵子树就可以称为森林。前面讲到，树可以理解为是由根结点和若干子树构成的，而这若干子树本身是一个森林，所以，树还可以理解为是由根结点和森林组成的。用一个式子表示为：Tree =（root, F）。其中，root 表示树的根结点，F 表示由 m（m >= 0）棵树组成的森林。