树的基本概念

树（Tree）是n（n>=0)个结点的有限集。n=0时称为空树

普通树
在任意一颗非空树中：

• 根（Root）结点
  有且仅有一个根（Root）结点，例如A就是root结点
• 子树、左子树、右子树
  例如：B是A的子树，E是B的左子树，F是B的右子树
• 结点的度（degree）：子树的个数
  例如：A结点的度是3，B结点的度是2
• 树的度：所有结点度中的最大值
  例如：A和D结点结点的度最大，都是3，所以树的度就是3
• 叶子结点（leaf）：度为 0 的结点
  例如：F结点
• 非叶子结点：度不为 0 的结点
  例如：E结点
• 层数（level）
  A结点是第一层，BCD结点是第二层,以此类推
• 结点的深度（depth）从根结点到当前结点的唯一路径上的结点总数
  例如：B结点的深度是2，E结点的深度是3
• 结点的高度（height）：从当前结点到最远叶子结点的路径上的结点总数
  例如：B结点的高度是3，F结点的高度是1
• 树的深度：所有结点深度中的最大值
  K结点的深度最大是4，就是树的深度
• 树的高度：所有结点高度中的最大值
  A结点的高度最大是4，就是树的高度

树的深度 等于 树的高度

• 有序树
  树中任意结点的子结点之间有顺序关系
• 无序树
  树中任意结点的子结点之间没有顺序关系
  也称为自由树
• 森林
  由m（m ≥ 0）棵互不相交的树组成的集合

二叉树（Binar y Tree）

普通二叉树

二叉树的特点

1. 每个结点的度最大为 2（最多拥有 2 棵子树）
2. 左子树和右子树是有顺序的
3. 即使某结点只有一棵子树，也要区分左右子树

二叉树是有序树

二叉树的性质

1. 非空二叉树的第i层，最多有 2^(i − 1) 个结点（i ≥1)
2. 在高度为h的二叉树上最多有 2^h - 1个结点（ h≥1)
3. 对于任何一棵非空二叉树，如果叶子结点个数为n0，度为2的结点个数为 n2，则有:n0 = n2 + 1
   论证:
   假设度为 1 的结点个数为 n1，那么二叉树的结点总数 n = n0 + n1 + n2
   二叉树的边数 T = n1 + 2 * n2 = n – 1 = n0 + n1 + n2 – 1
   因此 n0 = n2 + 1

真二叉树（Proper Binar y Tree）

所有结点的度都要么为 0，要么为 2

真二叉树

满二叉树（Full Binar y Tree）

• 最后一层结点的度都为 0，其他结点的度都为 2
• 在同样高度的二叉树中，满二叉树的叶子结点数量最多、总结点数量最多
• 满二叉树一定是真二叉树，真二叉树不一定是满二叉树

满二叉树

假设满二叉树的高度为 h（ h ≥ 1 ）
那么第 i 层的结点数量： 2^(i −1)
叶子结点数量： 2^(h −1)
总结点数量 n
n = 2^h - 1 = 2^0 + 2^1 + 2^2 + ⋯ + 2^(h-1)
h = log2(n + 1)

完全二叉树（Complete Binar y Tree）

完全二叉树：对结点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应

◼ 叶子结点只会出现最后 2 层，最后 1 层的叶子结点都靠左对齐
◼ 完全二叉树从根结点至倒数第 2 层是一棵满二叉树
◼ 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

完全二叉树的性质

◼ 度为 1 的结点只有左子树
◼ 度为 1 的结点要么是 1 个，要么是 0 个
◼ 同样结点数量的二叉树，完全二叉树的高度最小
假设完全二叉树的高度为h（ h ≥ 1 ），那么

• 至少有 2^(h-1) 个结点 （ 2^0 +2^1+ 2^2 + ⋯ +2^(h-2) + 1 ）
• 最多有2^h - 1 个结点（ 2^0 +2^1+2^2 + ⋯ +2^(h-1)，满二叉树 ）
  总结点数量为 n
  ✓ 2^(h-1) ≤ n < 2^h
  ✓ h-1 < log2n<h
  ✓ h = floor( log2n ) + 1
  ➢ floor 是向下取整，另外，ceiling 是向上取整

一棵有 n 个结点的完全二叉树（n > 0），从上到下、从左到右对结点从 1 开始进行编号，对任意第 i 个结点

• 如果 i = 1 ，它是根结点
• 如果 i > 1 ，它的父结点编号为 floor( i / 2 )
• 如果 2i ≤ n ，它的左子结点编号为 2i
• 如果 2i > n ，它无左子结点
• 如果 2i + 1 ≤ n ，它的右子结点编号为2i + 1
• 如果 2i + 1 > n ，它无右子结点

面试题

如果一棵完全二叉树有 768 个结点，求叶子结点的个数?
假设叶子结点个数为n0，度为 1 的结点个数为 n1，度为 2 的结点个数为 n2
总结点个数 n = n0 + n1 + n2 ，而且 n0 = n2 + 1
n = 2n0 + n1 – 1

完全二叉树的 n1 要么为 0 ，要么为 1

1. n1为1 时，n = 2n0 ， n 必然是偶数
➢ 叶子结点个数 n0 = n / 2 ，非叶子结点个数 n1 + n2 = n / 2

2. n1 为 0 时，n = 2n0 – 1 ， n 必然是奇数
➢ 叶子结点个数 n0 = (n + 1) / 2，非叶子结点个数 n1 + n2 = (n – 1) / 2

◼叶子结点个数 n0 = floor( (n + 1) / 2 ) = ceiling( n / 2 )
◼非叶子结点个数 n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 )
◼因此叶子结点个数为 384

国外教材的说法

• Full Binary Tree：完满二叉树
  所有非叶子结点的度都为 2
  就是国内说的“真二叉树”
  

  

• Perfect Binary Tree：完美二叉树
  所有非叶子结点的度都为 2，且所有的叶子结点都在最后一层
  就是国内说的“满二叉树”
  

  

• Complete Binary Tree：完全二叉树
  跟国内的定义一样