五、树
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个孩子