树的基本概念(定义、基本术语、性质)

树的基本概念

• • 树的定义
  • 树的特点
  • 基本术语
  • 树的性质

树的定义

树是n（n >=0）个节点的有限集。n = 0时，为空树。

任意一棵非空树应满足：

①、有且仅有一个特定的成为根的结点。

②、当n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每个集合本身又是一棵树，并成为根的子树。

树的特点

1、树的根结点没有前驱，除根结点外所有的结点有且只有一个前驱。

2、树中所有结点可以有零个或多个后继。

树时一种递归的数据结构，是逻辑结构，也是分层结构。

n个结点的树中有n-1条边。

基本术语

看结点Q：从A到Q的唯一路径上任意节点，成为Q的祖先。

E是Q的祖先，Q是E的子孙，J是Q的双亲，P和Q是兄弟

结点的度：一个结点的孩子的个数就是结点的度

树的度：树中结点最大的度称为树的度

分支结点：度大于0的结点称分支节点（又称非终端结点）

叶子结点：度为0的结点称叶子结点（又称终端结点）

结点的层次：从树根开始定义，根节点为第一层，它的子节点为第二层，以此类推。

结点的深度：从根节点开始自定向下逐层累加。

结点的高度：从叶节点开始自底向上逐层累加。

树的高度（或深度）：书中结点的最大层数。

有序树：树中结点的各子树从左到右是有次序的，不能互换

无序树：树中结点的各子树没有次序，可以互换

路径：两结点之间所经过的结点序列构成路径

路径长度：是路径上所经过的边的个数

森林：m（m>=0）棵互不相交树的集合。

树的性质

1、树中的结点数 = 所有结点的度数 （边数）+ 1；

2、度为m的树中第i层上最多有 mi-1 个结点；

m叉树第i层至多有mi-1 个结点；

3、度为m的树至少有一个结点的度 = m，至少有m + 1个结点

m叉树允许所有结点的度<m，可以是空树

4、高度为h的m叉树至多有（mh - 1 ）/（m - 1）个结点

高度为h的m叉树至少有n个结点

高度为h，度为m的 树至少 h+m-1个结点

5、具有n个结点的m叉树的最小高度为 logm(n(m-1)+1)