推荐订阅源

概述：完全二叉树是效率很高的数据结构，堆是一种完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

完全二叉树定义　　
完全二叉树(Complete Binary Tree)

　　若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。

　　完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

完全二叉树特点

一、

　　叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1；

二、

　　出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:

　　var tree:array[1..n]of longint;{n:integer;n>=1}

　　对于tree，有如下特点： 　　（1）若i为奇数且i>1，那么tree的左兄弟为tree[i-1]； 　　（2）若i为偶数且i<n，那么tree的右兄弟为tree[i+1]； 　　（3）若i>1，tree的双亲为tree[i div 2]； 　　（4）若2*i<=n，那么tree的左孩子为tree[2*i]；若2*i+1<=n，那么tree的右孩子为tree[2*i+1]； 　　（5）若i>n div 2,那么tree为叶子结点（对应于（3））； 　　（6）若i<(n-1) div 2.那么tree必有两个孩子（对应于（4））。 　　（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

三、

　　完全二叉树第i层至多有2^（i-1）个节点，共i层的完全二叉树最多有2^i-1个节点。

完全二叉树叶子结点的算法

　　

　如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。

　　可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n= n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝（n＋1）/2 ，就可根据完全二叉树的结点总数计算出叶子结点数。
本文摘自：http://bk.baidu.com/view/427107.htm
==================【以下内容摘自CSDN论坛】==================
【摘1】首先树与二叉树的区别就是,二叉树最多只有两个孩子(左孩子和右孩子),树就不一定了；再说完全的概念，深度为 K 的完全二叉树说通俗了就是一个深度为 K 的满二叉树的叶子节点可以从右边开始缺少。K 层的叶子节点至少为一个，如果为0，就成深度为（K-1）的满二叉树了！
【摘2】假设树T是一棵m叉树，那么，若树T中非叶子结点的次数都为m，我们就称树T为一棵m叉完全树。
完全二叉树，顾名思意，就是既是二叉树，又是完全树的树。具体地说就是：
如果把深度为k的满二叉树按层次从上到下，从左到右地进行编号1--(2k－1)，则深度为k的具有n个结点的二叉树，它的每一个结点都与深度为k的满二叉树中的编号从1到n的结点相对应，则这样的二叉树称为完全二叉树。对于完全二叉树，叶子结点只可能在层次最大的两层上出现，最后一层上的叶子结点一定依次都处在该层最左边的位置上。