二叉树的定义与性质

二叉树的定义
　　二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
    　二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
   这个定义是递归的。由于左、右子树也是二叉树， 因此子树也可为空树。图 6.3 中展现了五种不同基本形态的二叉树。

　　其中 (a) 为空树， (b) 为仅有一个结点的二叉树， (c) 是仅有左子树而右子树为空的二叉树， (d) 是仅有右子树而左子树为空的二叉树， (e) 是左、右子树均非空的二叉树。这里应特别注意的是，二叉树的左子树和右子树是严格区分并且不能随意颠倒的，图 6.3(c) 与图 6.3(d) 就是两棵不同的二叉树。

二叉树不是树的特例 
（1）二叉树与无序树不同
     二叉树中，每个结点最多只能有两棵子树，并且有左右之分。
  　二叉树并非是树的特殊情形，它们是两种不同的数据结构。 
（2）二叉树与度数为2的有序树不同
    在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。
  【例】下图中(a)和(b)是两棵不同的二叉树，它们同右图中的普通树(作为有序树或无序树)很相似，但却不等同于这棵普通树。若将这三棵树均看做普通树，则它们就是相同的了。
 　　　　　　  
  　二叉树并非是树的特殊情形，它们是两种不同的数据结构。

二叉树的性质
　　 二叉树具有以下重要性质：
性质1 二叉树第i层上的结点数目最多为2^i-1(i≥1)。
证明：用数学归纳法证明：
　    归纳基础：i=1时，有2^i-1=2⁰=1。因为第1层上只有一个根结点，所以命题成立。
    　归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2^j-1个结点，证明j=i时命题亦成立。
    　归纳步骤：根据归纳假设，第i-1层上至多有2^i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2^i-2=2^i-1个结点，故命题成立。

性质2 深度为k的二叉树至多有2^k-1个结点(k≥1)。
证明：由性质 (1) 可知各层结点最多数目之和为： 2 0 +2 1 +2 2 +.....+2 k-1 ；由二进制换算关系可知： 2 0 +2 1 +2 2 +.....+2 k-1 = 2 k -1 ；因此二叉树树中结点的最大数目为 2 k -1 。性质 2 证明完毕。
                
性质3 在任意-棵二叉树中，若叶子结点（即度为0的结点）的个数为n₀，度为1的结点数为n₁，度为2的结点数为n₂，则n_o=n₂+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n₁)和2度结点数之和：
                     n=n_o+n₁+n₂ (6.1)
　   
由于有n个结点的二叉树总边数为n-1条，于是得：
                     n-1=0*n₀+1*n₁+2*n₂ (6.2) 
将（6.1）式代入（6.2）式得：n₀=n₂+1。性质3证明完毕

满二叉树和完全二叉树是二叉树的两种特殊情形。
1、满二叉树(FullBinaryTree) 
    　一棵深度为k且有2^k-1个结点的二又树称为满二叉树。
    　满二叉树的特点：
　　（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
　　（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
　　【例】图6.4(a)是一个深度为3的满二叉树。
         


2、完全二叉树(Complete BinaryTree) 
    若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
  特点：
  （1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
  （2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
  （3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
【例】如图6.4(c)中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树。
【例】图6.4(b)是一棵完全二叉树。
  
性质 4 具有 n 个结点的完全二叉树树深为 +1 （其中 表示不大于 x 的最大整数）。 
证明：假设某完全二叉树的结点总数是 n ，它的值应该大于树深为 K-1 的满二叉树结点数 2 k-1 -1 ，小于等于树深为 K1 的满二叉树结点数 2 k -1 。 
2 k-1 -1 < n <= 2 k -1 
由于该不等式各项均为整数，当对两端两项各加 1 时不等式发生变化得： 
2 k-1 <= n < 2 k 
再对其取对数得： k-1<= log 2 n < k 
如果对 log 2 n 取整显然等于 k-1 ：， 所以得： 
性质 4 证明完毕。

性质 5 若对有 n 个结点的完全二叉树进行顺序编号 (1 ≤ i ≤ n) ，那么： 
对于编号为 i(i ≥ 1) 结点 : 
当 i=1 时，该结点为根，它无双亲结点； 
当 i>1 时，该结点的双亲结点编号为 ； 
若 2i ≤ n ，它有编号为 2i 的左孩子，否则没有左孩子； 
若 2i+1 ≤ n ，则它有编号为 2i+1 的右孩子，否则没有右孩子。 
对照图 6.4(a) 或图 6.4(b) 读者可看到由性质 ( ５ ) 所描述的结点与编号的对应关系 。