普通二叉树

二叉树

特点：

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

真二叉树（Proper Binary Tree）

真二叉树：所有节点的度都要么为0，要么为2

满二叉树（Full Binary Tree）

满二叉树：所有节点的度都要么为0，要么为2。且所有的叶子节点都在最后一层

• 在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多
• 满二叉树一定是真二叉树，真二叉树不一定是满二叉树

假设满二叉树的高度为h（h大于等于1）：

第i层的节点数量：2的i-1次方

叶子节点数量：2的h-1次方

总节点数量：2的h次方-1

完全二叉树（Complete Binary Tree）

完全二叉树：叶子节点只会出现最后2层，且最后1层的叶子结点都靠左对齐

• 完全二叉树从根结点至倒数第2层是一颗满二叉树
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

完全二叉树的性质

• 度为1的节点只有左子树

• 度为1的节点要么是1个，要么是0个

• 同样节点数量的二叉树，完全二叉树的高度最小

• 假设完全二叉树的高度为h（h对于等于1）：

  • 至少有2的h-1次方个节点
  • 最多有2的h次方-1个节点
  • 总节点数量为n：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个节点

  • 如果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，它无右子节点