二叉树

二叉树的定义

二叉树的每个结点最多只有两个分支，结点数只可能是 0, 1, 2。

二叉树是由一个根结点和两颗互不相交的分别称作这个根的左子树和右子树的二叉树定义（递归定义），子树有顺序之分不能调换顺序。

二叉树有以下 5 种基本形态：

∅			⚪			⚪		⚪				⚪
						/			 \			 /	    \
				  	  ⚪				⚪		⚪		 ⚪
空二叉树 根和空的二叉树 根和左子树 		根和右子树 		根和左右子树

二叉树不是树的特殊情况，它们是两个概念。因为如果二叉树某个结点只有一个孩子结点时仍然需要区分这个结点是左孩子还是右孩子；而树的某个结点只有一个孩子结点时就不需要区分左右孩子。

	⚪		⚪							⚪
  /				\						   |
⚪				⚪						⚪
		二叉树								 树
这两颗二叉树是不一样的结构		   而只有一个孩子的树只有这一种结构

quiz：具有3个节点的二叉树有 ___ 种不同的形态？普通的树呢？(提示：考虑树的层次)

二叉树的性质

1. 在二叉树的第 i 层上至多只有 2^i-1^ 个结点 (i >= 1)

   quiz：第 i 层至少有 ___ 个结点

2. 深度为 k 的二叉树至多有 2^k-1^ 个结点 (k >= 1)

   quiz：深度为 k 时至少有 ___ 个结点

3. 对于任何一颗二叉树 T，如果其叶子数为 n0 ，度为 2 的结点数为 n2 ，则 n0 = n2 + 1

   总结点数为 n ： n = n0 + n1 + n2

   从下往上分析（一个结点只往上产生一条边）总边数 ：n - 1

   从上往下分析（度为 0 的结点产生 0 条边，度为 1 的结点产生 1 条边，度为 2 的结点产生 2 条边）总边数 ：n1 + 2 * n2

两种特殊形式的二叉树

• 满二叉树

  一颗深度为 k 且结点数为 2^k^ - 1 的树是 满二叉树

  特点

  1. 每一层的结点数都是最大结点数，每层都是满的
  2. 叶子节点都在最底层

  编号规则 ：从根节点开始，从上至下、从左至右依次排序

• 完全二叉树

  深度为 k 的具有 n 个节点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树种编号为 1 ~ n 的结点一一对应时，成为 完全二叉树

  性质：

  1. 具有 n 个节点的完全二叉树的深度为 向下取整(log2n) + 1
  2. 对于一颗完全二叉树，结点按照层序编号(从上至下，从左至右)，那么对任一个结点 i (1 <= i <= n) 有：
     1. 如果 i = 1，那么 i 时二叉树的根，没有双亲；如果 i > 1,则其双亲为 i / 2 (向下取整)
     2. 如果 2 * i > n，则结点 i 是叶子节点，没有左孩子；否则其左孩子是 2 * i
     3. 如果 2 * i + 1 > n，则结点 i 无右孩子；否则 其右孩子是节点 2 * i + 1