9.4.1　基本概念

树（tree）是n（n＞=0）个节点的有穷集。n=0时称为空树。

在任意一个非空树中：

（1）每个元素称为节点（node）；

（2）仅有一个特定的节点被称为根节点或树根（root）。

（3）当n＞1时，其余节点可分为m（m≥0）个互不相交的集合T1，T2，……Tm，其中每一个集合Ti（1＜=i＜=m）本身也是一棵树，被称作根的子树（subtree）。

注意：

·n＞0时，根节点是唯一的。

·m＞0时，子树的个数没有限制，但它们一定是互不相交的。

节点拥有的子树数被称为节点的度（Degree）。度为0的节点称为叶节点（Leaf）或终端节点，度不为0的节点称为分支节点。除根节点外，分支节点也被称为内部节点。节点的子树的根称为该节点的孩子（Child），该节点称为孩子的双亲或父节点。同一个双亲的孩子之间互称为兄弟。树的度是树中各个节点度的最大值。

节点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。双亲在同一层的节点互为堂兄弟。树中节点的最大层次称为树的深度（Depth）或高度。如果将树中节点的各个子树看成从左到右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。森林是m（m＞=0）棵互不相交的树的集合。

树的定义如图9-19所示：

图9-19　树的定义更换图片