二叉树的性质和存储结构

2. 两种特殊的二叉树

• 满二叉树

  • 定义：一棵深度为 k 且有 2^k - 1 个结点的二叉树称为满二叉树。

  • 特点：

    1. 每一层上的结点数都是最大结点数（即每层都满）；
    2. 叶子结点全部在最底层；

  • 对满二叉树结点位置进行编号

    • 编号规则：从根结点开始，自上而下，自左而西；
    • 每一结点位置都有元素；

• 完全二叉树

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

  

  • 注：在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树，一定是连续的去掉！！！
  • 特点：
    1. 叶子只可能分布在层次最大的两层上。
    2. 对任一结点，如果其右子树的最大层次为 i，则其左子树的最大层次为 i 或 i + 1。

3. 性质

• 性质3：任意二叉数的叶子结点数 = 其度为2的结点数 + 1；

• 性质4：具有 n 个结点的完全二叉树的深度为【 log2(n) 】+ 1。

  注：【 x 】：称作x的底，表示不大于x的最大整数。

  

  

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

• 性质5：如果对一棵有n个结点的完全二叉树（深度为【 log2(n) 】+ 1）的结点按层序编号（从第1层，到第【 log2(n) 】+ 1层，没层从左到右），则对任一结点 (1<= i<= n)，有：

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

4. 二叉树的顺序存储

• 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。

  

  //二叉树顺序存储表示
  #define MAXSIZE 100
  Typedef TElemType SqBiTree[MAXSIZE] SqBiTree bt;
  

• 缺点：

  最坏情况：深度为 k 的且只有 k 个结点的单支树需要长度为 2^k -1的一维数组。

• 特点：结点间关系蕴含在其存储位置中浪费空间，适用于满二叉树和完全二叉树。

5.二叉树的链式存储结构

//二叉树链式存储表示
typedef struct BiNode{
    TElemType data;
    struct BiNOde *lchild,*rchild;//左右孩子指针
}BiNode,*BiTree;

• 注：在 n 个结点的二叉链表中，有 n + 1 个空指针域。

• 三叉链表

  typedef struct TriTNode{
     TElemType data;
      struct BiNode *lchild,*parent,*rchild;
  }TriTNode,*TriTree;