完全二叉树
完全二叉树的定义、性质以及算法见正文。这里补充一点：完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。
中文名：完全二叉树
外文名：CompleteBinaryTree
日语：完全二進法の木
德语：Komplett-baum
1、判断完全二叉树
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
2、完全二叉树定义
完全二叉树(CompleteBinaryTree)
若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
3、完全二叉树特点
叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L或L+1；
出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:
vartree:arrayoflongint;{n:integer;n>=1}
对于tree，有如下特点：
（1）若i为奇数且i>1，那么tree的左兄弟为tree；
（2）若i为偶数且i<n，那么tree的右兄弟为tree；
（3）若i>1，tree的父亲节点为tree；
（4）若2*i<=n，那么tree的左孩子为tree；若2*i+1<=n，那么tree的右孩子为tree；
（5）若i>ndiv2,那么tree为叶子结点（对应于（3））；
（6）若i<(n-1)div2.那么tree必有两个孩子（对应于（4））。
（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
完全二叉树第i层至多有2^（i-1）个节点，共i层的完全二叉树最多有2^i-1个节点。
完全二叉树的特点是：
1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；
2）对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。即度为1的点只有1个或0个
4、算法
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则①n=n0+n1+n2（其中n为完全二叉树的结点总数）；又因为一个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点，所以②n=1+n1+2*n2；由①、②两式把n2消去得：n=2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2或n0=(n+1)/2。
简便来算，就是n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。