定义：每个结点最多有两个子树的结构，子树又分为左子树和右子树。可以没有结点

二叉树的可能形态

• 空二叉树
• 只有一个根结点的二叉树
• 只有左子树
• 只有右子树
• 完全二叉树
• 一般二叉树

易错：二叉树不是树的特殊情形，他们的主要差别为：

• 树中结点的最大度数没有限制，二叉树节点的最大度数为2
• 树的结点无左右子树之分，而二叉树的结点有左右子树之分

二叉树性质

• 在二叉树的第i层最多有2^(i-1)个结点，i>=1
• 深度为K的二叉树至多有2^(k) -1个结点（k>=1）
• 对任何一棵二叉树T，如果其叶节点数为n0,度为2的结点数为n2,则n0 = n2 + 1
• 具有n个结点的完全二叉树的深度为log2(n) +1
• 将一棵有n个结点的完全二叉树自顶向下，逐层自左向右连续为结点编号0，1，….，n-1，则有
  • 若i = 0,则无双亲，若i>0,则i的父结点为（i-1）/2
  • 若2*i + 1 < n,则i的左子结点为2*i + 1,若 2*i + 2 < n,则右子节点为 2*i+2
  • 若结点编号i为偶数，且i != 0,则左兄弟结点i-1
  • 若结点编号i为奇数，且i != n-1,则右兄弟结点为i+1
  • 结点i所在的层次：log2(i+1)