树

树的基本概念

• 节点、根节点、父节点、子节点、兄弟节点
• 一棵树可以没有任何节点,称为空树
• 一棵树可以只有一个节点,也就是只有根节点
• 子树、左子树、右子树
• 节点的度: 子树的个数
• 树的度:所有节点度中的最大值
• 叶子节点:度为 0 的节点
• 非叶子节点:度不为 0 的节点
• 层数: 根节点在第1 层,根节点的子节点在第二层,以此类推
• 节点的深度:从根节点到当前节点的唯一路径上的节点总数
• 节点的高度:从当前节点到最远叶子节点的路径上的节点总数
• 树的深度:所有节点深度中的最大值
• 树的高度:所有节点高度中的最大值
• 树的深度等于树的高度
• 有序树: 树中任意节点的子节点之间有顺序关系
• 无序树: 树中任意节点的子节点之间没有顺序关系,也称"自由树"
• 森林: 由 M(M>=0) 棵互不相交的树组成的集合

二叉树

特点:

• 每个节点的度最大为 2(最多拥有 2 棵子树)
• 左子树和右子树是有顺序的
• 即使某节点只有一颗子树,也要区分左右子树
• 二叉树是有序树

性质

• 非空二叉树的第 i 层，最多有 2^(i − 1) 个节点（ i ≥ 1 ）
• 在高度为 h 的二叉树上最多有 2^h - 1 个节点(h>=1)
• 对于任何一颗非空二叉树,如果叶子节点个数为 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

真二叉树

• 所有节点的度都要么为 0,要么为 2

  
  

满二叉树

• 最后一层节点的度都为 0,其他节点的度都为 2
• 假设满二叉树的高度为 h(h>=1),那么:
  第 i 层的节点数量为:2^(i-1)
  叶子节点数量为:2^(h-1)
  总子节点数量:
  n = 2^h - 1 = 2⁰⁺²1+2^2+...+2-1
  h = log2(n+1)
• 在同样高度的二叉树中,满二叉树的叶子节点数量最多,总结点数量最多

• 满二叉树一定是真二叉树,真二叉树不一定是满二叉树

  
  

完全二叉树

• 对节点从上至下、从左至右开始编号,其所有编号都能与相同高度的满二叉树中的编号对应
• 叶子节点知会出现在最后 2 层,最后一层的叶子节点都靠左对齐
• 完全二叉树从根节点至倒数第 2 层是一颗满二叉树
• 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树
• 度为 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
• 一颗有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, 它无右子节点
• 一颗有 n 个节点的完全二叉树(n>0),从上到下,从左到右对节点从 0 开始进行编号,对任意第一个节点
  如果 i=0,它是根节点
  如果 i>0, 它的父节点编号为 floor((i-1)/2)
  如果 2i + 1<=n-1,它的左子节点编号为 2i + 1
  如果 2i + 1>=n - 1,它无左子节点
  如果 2i + 2 <= n - 1,它的右子节点编号为 2i+2
  如果 2i + 2 > n - 1, 它无右子节点

image.png