数据结构重学日记（十五）树的基本概念

概念

树是有 n(n >= 0) 个结点的有限集，在任意一棵非空树中，有且仅有一个特定的称为根的结点，当 n > 1 时，其余结点可分为 m(m > 0)个互不相交的有限集 ，，…，其中每个集合本身又是一棵树，并称为根的子树。

树的示例

树的结构定义是一个递归的定义。树的结点包含一个数据元素及若干个指向其子树的分支，结点拥有的子树数量称为结点的度。

度为 0 的树称为叶子或终端结点，度不为 0 的结点称为非终端结点或分支结点。

除了根节点之外，分支结点也称为内部结点，树的度是树内各结点的度的最大值。例如上图中 A 的度为 3 ， D 是 A 的孩子，A 是 D 的双亲。H 和 I 互为兄弟。

树中结点的最大层次称为树的深度或高度，上图的深度为 4。

如果树中结点的子树从左向右是有序的，子树间不能互换位置，则称该树为有序树，否则为无序树。

由 n 棵互不相交的树组成的集合称为森林。

树的特性

• 树中所有结点数等于所有结点的度加 1

还以上图为栗，A 的度为 3，B 的度为 2，C 的度为 1，D 的度为 3，E 的度为 2，H 的度为 1
3 + 2 + 1 + 3 + 2 + 1 = 12，结点总数为 13。

• 度为 m 的树上第 i 层最多有 个结点（i > = 1 ）

A 的度为 3 ，第 2 层有 = 3 个结点。

• 高度为 H 的叉树最多有 ( - 1) / (m -1)个结点

• 具有 n 个结点的 m 叉树的最小高度为 [(n(m -1) + 1)]