【数据结构】树的基本概念与性质

1. 树的基本概念

1. 数的基本概念

树是n(n>=0)个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点。
2. 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

说明：根结点A有三棵子树，他们之间互不相交。

树作为一种逻辑结构，非空树具有以下特点：

1. 有且仅有一个根结点。
2. 没有后继的结点称为“叶子结点”（或终端结点）。
3. 有后继的结点称为“分支结点”（或非终端结点）。
4. 除根节点外的所有结点有且只有一个前驱。
5. 树中所有的节点可以有零个或多个后继。

2. 结点、树的属性

说明：

• 结点的层次（深度）——（默认从1开始）从上往下数。
• 结点的高度——从下往上数。
• 数的高度（深度）——总共有多少层
• 结点的度——有几个孩子（分支）
• 树的度——各结点度的最大值。

3. 有序树和无序数

• 有序树—-逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
• 无序树――逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

4. 树和森林

森林：森林是m（m>=0）棵互不相交的数的集合。m为0时表示空森林。

2. 树的性质

1. 节点数运算

结点数=总度数+1

图中：结点数=12+1=13

说明：结点的度表示结点有几个孩子（分支）

2. 度为m的树和m叉树的区别

树的度——各结点的度的最大值。

m叉树——每个结点最多只能有m个孩子的树。

3. 树的层数与结点的关系

4. 是的高度h和m叉树的关系

5. 高度h、m叉树与结点的关系

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

高度为h、度为m的树至少有h+m-1个结点。

6. 求n个结点m叉树的最小高度

3. 小结

性质部分第2条和第6条是重点。