Tim的资源站一、树的基本概念
树是由n（n≥0）个结点组成的有限集合。若n=0，则称为空树；若n＞0，则称为非空树，在任一棵非空树中，满足以下条件：
-
有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱。
-
除根结点以外的其他结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，且每个集合Ti（i=0，1，…，m-1）本身又是一棵树，称为根的子树。即树T0，T1，…，Tm-1称为这个根结点的子树。
由此可知，树的定义是一个递归的定义，因为树的定义中又用到了树的概念。
从定义中看出树结构具有以下特点：
-
有且仅有一个结点没有直接前驱，即根结点。
-
除根结点之外，其余所有结点有且仅有一个直接前驱结点。
-
包括根结点在内，每个结点可以有多个（或零个）直接后继结点。
从此可见，树形结构的特点是数据元素之间存在着一对多的关系。
树的结构如下图所示：
树结构示意图：
在树结构示意图（c）中，树的根结点为 A，该树还可以分为 3 个互不相交的子集T0、T1、T2，具体请参见图“树的三个子树”，其中，T0 =｛B，E，F，J，K，L｝，T1 =｛C，G｝，T2 =｛D，H，I，M｝，而T0、T1、T2又可以分解成若干棵不相交子树。例如，T0可以分解成T00、T01两个不相交子集，T00 =｛E，J，K，L｝，T01 =｛F｝，而 T00 又可以分为 3 个不相交子集T000、T001、T002，其中，T000 =｛J｝，T001 =｛K｝，T002 =｛L｝。
树的三个子树：
二、树的基本术语
-
树的结点
树的结点是指树中的一个数据元素，一般用一个字母表示。
-
结点的度
一个结点包含子树的数目，称为该结点的度。
-
树叶（叶子）
度为 0 的结点，称为叶子结点或树叶，也叫终端结点。
-
分支结点（非终端结点）
除叶子结点外的所有结点，称为分支结点。通常又将除根结点之外的分支结点称为内部结点。
-
孩子结点
若结点 X 有子树，则子树的根结点为 X 的孩子结点，也称为孩子。树结构示意图（c）中 A 的孩子为 B、C、D。
-
双亲结点
若结点 X 有子女 Y，则 X 为 Y 的双亲结点。
-
祖先结点
一个结点的祖先是从根结点到该结点路径上所经过的所有结点。树结构示意图（c）中 K 的祖先结点是 A、B、E。
-
子孙结点
某一结点的直接后继（子女）和间接后继（子女的子女）为该结点子孙。树结构示意图（c）中 D 的子孙是 H、I、M。
-
兄弟结点
具有同一个双亲的结点，称为兄弟结点。不具有同一个双亲但有共同祖先的结点是堂兄弟。
-
结点的层次
从根结点开始定义，根为第一层，根的孩子为第二层，以此类推。
-
树的高度（深度）
树中结点所处的最大层数称为树的高度，如空树的高度为 0，只有一个根结点的树高度为 1。
-
树的度
树中结点度的最大值称为树的度。
-
有序树
若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序，称该树为有序树。
-
无序树
若一棵树中所有子树的次序无关紧要，则称为无序树。
-
森林（树林）
若干棵（有限棵）互不相交的树组成的集合称为森林。一棵树可以看成一个特殊的森林。树与森林的关系如下：任何一棵非空树，删去根结点就变成了森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。
三、树的表示
-
树形结构表示法
参考树结构示意图 -
凹入表示法
-
嵌套集合表示法
-
广义表表示法
对树结构示意图所示的树结构，用广义表表示法可表示为：A（B（E（J，K，L），F），C（G），D（H（M），I））
