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

2019-01-18 本文已影响1人南瓜方糖

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

树的示例

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

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

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

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

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

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

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

A 的度为 3 ，第 2 层有 $3^2-1$ = 3 个结点。