数据结构:树的度、阶

度

节点的度(单个节点)

某个节点的度,该节点拥有的 子节点个数

例子:

  • 叶子节点:没有孩子 → 度 = 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

原文出处:/show_1GW2jvyiIpdG.html