网站app建设需要资源快速的网站开发工具
五、树
5.1 树的基本概念
5.1.1 树的定义
树是n(n>=0)个结点的有限集合，结点数为0的树称为空树
非空树的特性
- 有且仅有一个根节点
- 没有后继的结点称为“叶子结点”（或终端结点）
- 有后继的结点称为“分支结点”（或非终端结点）
- 除了根节点外，任何一个结点都有且仅有一个前驱
- 每个结点可以有0个或多个后继。
5.1.2 树的基本术语
树的属性
- 结点的层次（深度）——从上往下数 (默认从1开始)
- 结点的高度——从下往上数
- 树的高度（深度）——总共多少层
- 结点的度——有几个孩子（分支）★
- 树的度——各结点的度的最大值 ★
有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
森林。森林是m（m≥0）棵互不相交的树的集合。m为0时是“空森林”
5.1.3 树的常考性质
常见考点1:结点数=总度数+1
结点的度—结点有几个孩子(分支)
常见考点2：度为m的树、m叉树 的区别
树的度——各结点的度的最大值 m叉树——每个结点最多只能有m个孩子的树
| 度为m的树 | m叉树 |
| 任意结点的度 ≤ m（最多m个孩子） | 任意结点的度 ≤ m（最多m个孩子） |
| 至少有一个结点度 = m（有m个孩子） | 允许所有结点的度都 ＜ m |
| 一定是非空树，至少有m+1个结点 | 可以是空树 |
常见考点3：度为m的树第 i 层至多有 个结点（i≥1）
m叉树第 i 层至多有 个结点（i≥1）
常见考点4：高度为h的m叉树至多有 个结点。
等比数列求和公式：
常见考点5：高度为h的m叉树至少有 h 个结点。
高度为h、度为m的树至少有 h+m-1 个结点
常见考点6：具有n个结点的m叉树的最小高度为
高度最小的情况——所有结点都有m个孩子
