二叉树的性质和存储结构

性质：

1. 在二叉树的第i层最多有2^(i-1)个结点（i>=1)
2. 深度为k的二叉树最多有2^k-1个结点（运用等比求和）
3. 对任何一棵二叉树T，如果叶子数为n0,度为2的结点数为n2,则n0=n2+1(根据二叉树的边来计算）

二叉树种两种特殊形式的二叉树：

         满二叉树

•       一棵深度为k且有2^k-1个结点
•       每一层都是满的
•       叶子结点在最后一层

        完全二叉树

•      深度为k的具有n个结点的二叉树，每一个结点都与深度为k的满二叉树种编号为1~n的结点一一对应
•      叶子只能分布在最后一层
•      对于任意结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1
•      具有n个结点的完全二叉树的深度为[log2 n]+1(用二叉树的结点计算，2^(k-1)<n<2^k-1
•      如果有一个结点数为n的完全二叉树，结点按层序编号，则对任一结点i有（双亲结点与孩子结点的关系）

1.    如果i=1，则结点是根；若i>1,其双亲是结点[i/2]
2.    如果2i>n,则结点i是叶子结点，无左孩子；否则，其左孩子是结点2i
3.    如果2i+1>n,则结点i无右孩子；否则右孩子是2i+1        

存储结构：

        顺序存储结构：按满二叉树的结点层次编号，依次存放

       #define  MAXTSIZE100

       typedef TElemType SqBiTree[MAXTSIZE]//TElemType 是树的元素类型

       SqBiTree bt;//Sq是顺序表,BiTree是二叉树

       缺点：位置浪费，如果二叉树有k层，就要需要定义一个2^k-1长度的一维数组，但是如果仅有k个元素需要存储，其他位置就浪费了。它适于存储满二叉树与完全二叉树

      要求：给出二叉树的结点数值，画出二叉树

          链式存储结构：需要两个指针，指向它的左右孩子，还有一个数据域

         typedef struct BiNode{

         TElemType data;

         struct BiNode  *lchild,*rchild;

         }BiNode,*BiTree;//链式结构类型，结点类型，指向该结点的指针

        在n个结点的二叉链表中，有2n-(n-1)=n+1个空指针

       三叉链表：除了两个指针，一个自身结点的数据域，再加上一个指向双亲结点的指针

      typedef struct TriTNode{

        TElemType data;

        struct TriNode  *lchild,*rchild，*parent;

      }TriTNode,*TriTree;