5-4 二叉树的性质和存储结构

• 性质1：在二叉树的第i层上至多有$2^{i-1}$个结点（i≥1）

  例：在第2层上最多有$2^{2-1}=2^1个结点$

  注意：第i层上最少有1个结点

• 性质2：深度为k的二叉树至多有$2^k-1$个结点（k≥1）

  例子：深度为2的二叉树有3个结点

  注意：深度为k时最少有k个结点

• 性质3：对任何一棵二叉树T，如果其叶子数为$n_0$，度为2（有两个后继结点）的结点数为$n_2$，则$n_0=n_2+1$

  

5-4 二叉树的性质和存储结构（2）

特殊形式的二叉树：

• 满二叉树：

  • 定义：一颗深度为k且有$2^k-1$个结点的二叉树叫做满二叉树

  

  • 特点：
    1. 每一层上的结点数都是最大结点数（即每层都满）
    2. 叶子结点全部在最底层
  • 对满二叉树结点位置进行编号：
    • 编号规则：从根结点开始，自上而下，自左而右
    • 每一结点位置都有元素

• 完全二叉树：

  • 定义：深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树

  

  注意：在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全的二叉树

  • 特点：
    1. 叶子只可能分布在层次最大的两层上
    2. 对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1

5-4 二叉树的性质和存储结构（3）

• 性质4：具有n个结点的完全二叉树的深度为

 *性质4表明了完全二叉树结点n与完全二叉树深度k之间的关系* 

• 性质5：如果对一棵有n个结点的完全二叉树（深度为$[log_2n]+1$）的结点按层序编号（从第一层到$[log_2n]+1$层，每层从左到右），则对任一结点i（1≤i≤n），有：

  1. 如果i=1，则结点i是二叉树的根，无双亲；如果i>1,则其双亲是i/2
  2. 如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i
  3. 如果2i+1>n，则结点i无右孩子；否则，其右孩子是结点2i+1

  性质5表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系