二叉树性质

1. 在二叉树的第i层上至多有2^（i-1）个结点（i≥1）

2. 深度为k的二叉树至多有2^k-1个结点（k≥1）

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

满二叉树：一颗深度为k且有2^k-1个结点的二叉树

特点：每层都满；叶子节点全部在最底层

编号规则：从上到下，从左到右

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

性质：

具有n个结点的完全二叉树的深度【log2n】+1；（n和k的关系）

如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i，有：

1. 如果i=1，则结点i是二叉树的根，无双亲；如果i＞1，则其双亲结点【i/2】

2. 如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i

3. 如果2i+1＞n，则结点i无右孩子；否则，其右孩子是结点2i+1

（双亲结点和孩子结点编号的关系）

二叉树的顺序存储：按满二叉树的结点层次编号，依次存放二叉树中的数据元素

二叉树的链式存储：用链表来指示元素之间的逻辑关系。通常有两种存储形式：

• 链表中每个结点由三个域组成，除了数据域之外，还有两个指针域，分别用来给出该结点的左孩子和右孩子所在的存储地址。

• 链表中每个结点由四个域组成，除了数据域之外，还有三个指针域，分别用来给出该结点的左孩子、右孩子和双亲结点所在的存储地址。