度
节点的度(单个节点)
某个节点的度,该节点拥有的 子节点个数
例子:
- 叶子节点:没有孩子 → 度 = 0
- 有 2 个孩子的节点 → 度 = 2
- 有 3 个孩子的节点 → 度 = 3
树的度(整棵树)
树的度,树中 所有节点的度的 最大值
如:树中某个节点有 n 个子节点,其他节点的子结点数量都比 n 少,所以 树的度是 n
例子:
- 二叉树:所有节点最多有 2 个孩子,所以 二叉树的度是 2
- 三叉树:最多有 3 个孩子,所以 三叉树的度是 3
- 某个普通树,某个节点有 5 个孩子,其他节点的子结点都更少,所以 树的度是 5
阶
阶(Order),树中任意节点 最多允许有子节点的数量,即:允许的最多子结点数量(上限)
阶 和 度 的区别
- 节点的度:当前节点 实际有几个孩子
- 树的度:整棵树里 最大的实际度数
- 树的阶:整棵树 最多允许(不是实际拥有) 有几个孩子(上限)
例子
二叉树结构图:
A(度=2)
/ \
B(度=1) C(度=0)
/
D(度=0)
各个节点的度
- A:有 B、C 两个孩子 → 度 = 2
- B:只有 D 一个孩子 → 度 = 1
- C:无孩子(叶子)→ 度 = 0
- D:无孩子(叶子)→ 度 = 0
树的度
- 所有节点度:2、1、0、0
- 最大值是 2,所以 树的度 = 2
阶
- 因为是 二叉树,规定最多 2 孩子,所以 阶 = 2