数据结构的度

1 (l) 结点：树中的一个独立单元。包含一个数据元素及若于指向其子树的分支，如图5.1 (b) 中的A 、B 、C 、D 等。（下面术语中均以图5.1 (b) 为例来说明） (2)结点的度：结点拥有的子树数称为结点的度。例如，A的度为3, C的度为l, F的度 为0。 (3)树的度： 树的度是树内各结点度的最大值。图5.1 (b) 所示的树的度为3。 (4) 叶子：度为0 的结点称为叶子或终端结点。结点K 、L 、F 、G 、M 、I 、J都是树的 叶子。 (5) 非终端结点：度不为0 的结点称为非终端结点或分支结点。除根结点之外，非终端结点 也称为内部结点。 (6)双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例 如，B的双亲为A, B的孩子有E和F。 (7) 兄弟：同一个双亲的孩子之间互称兄弟。例如，H 、I 和J互为兄弟。 (8) 祖先：从根到该结点所经分支上的所有结点。例如， M 的祖先为A 、D 和H。 (9) 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如B 的子孙为E 、K 、L 和F。 (10) 层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的 层次等千其双亲结点的层次加l。 (11)堂兄弟：双亲在同一层的结点互为堂兄弟。例如，结点G 与E 、F、H 、I 、J互为 堂兄弟。 (12)树的深度：树中结点的最大层次称为树的深度或高度。图5.1 (b)所示的树的深度 为4。 (I3 )有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换）， 则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的 称为最后一个孩子。 (14)森林：是m (m􀁑O)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即 为森林。由此，也可以用森林和树相互递归的定义来描述树。

从根节点到叶节点依次 经过的节点(含根、叶节点)形成树的一条路径，最长路径的长度为树的深度。