数据结构(五)——树的基本概念

五、树

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个孩子