二叉树

满二叉树

定义：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

对于国内的满二叉树

从数学上看，满二叉树的各个层的结点数形成一个首项为1，公比为2的等比数列。
因此由等比数列的公式，满二叉树满足如下性质。

1. 层数为k的满二叉树总结点数为：，因此满二叉树的结点数一定是奇数个。
2. 第 i 层上的结点数为：
3. 层数为k的满二叉树的叶子结点数（也就是最后一层）：

对于国外的满二叉树
**
满二叉树的结点要么是叶子结点，度为0，要么是度为2的结点，不存在度为1的结点。

因此，上图中这个二叉树也是满二叉树。但是按照国内的定义，它却不是满二叉树。
美国以及国际上所定义的满二叉树，即full binary tree,和国内的定义不同，美国NIST给出的定义为：满二叉树的任意节点，要么度为0，要么度为2.换个说法即要么为叶子结点，要么同时具有左右孩子。霍夫曼树是符合这种定义的，满足国际上定义的满二叉树，但是不满足国内的定义。

完全二叉树

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

完全二叉树满足如下性质：

1. 只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；
2. 对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个。

二叉树的性质

1. 在二叉树的第ｉ（ｉ>=１）层最多有 个结点。
2. 深度为k(k>=0)的二叉树最少有k个结点，最多有 个结点。
3. 对于任一棵非空二叉树，若其叶结点数为 ，度为2的非叶结点数为 ，则 。
4. 具有n个结点的完全二叉树的深度 为 ， 表示不大于x的最大整数。
5. 如果将一棵有n个结点的完全二叉树自顶向下，按层编号，然后按此结点编号将树中各结点顺序的存放于一个一维数组，并简称编号为i的结点为结点i（ ｉ>=１ && ｉ<=ｎ）,则有以下关系：
   （1）若 ｉ= 1，则结点i为根，无父结点；若 ｉ> 1，则结点 i 的父结点为结点int_DOWN（ｉ / ２）;
   （2）若 ２＊ｉ <= ｎ，则结点 ｉ 的左子女为结点 ２＊ｉ；
   （3）若２＊ｉ＜＝ｎ，则结点ｉ的右子女为结点２＊ｉ＋１；
   （4）若结点编号ｉ为奇数，且ｉ！＝１，它处于右兄弟位置，则它的左兄弟为结点ｉ－１；
   （5）若结点编号ｉ为偶数，且ｉ！＝ｎ，它处于左兄弟位置，则它的右兄弟为结点ｉ＋１；
   （6）结点ｉ所在的层次为 int_DOWN（log（2，ｉ））＋１。