一、定义：

    若设二叉树的深度为k，除第k层外，其他各层（1～（k-1）层）的节点数都达到最大值，且第k层所有的节点都连续集中在最左边，这样的树就是完全二叉树。如下图：

image

     完全二叉树是一种效率很高的数据结构，而堆是一种完全二叉树或者近似完全二叉树，因此堆的效率也很高；像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性是基于完全二叉树的。

    下图是非完全二叉树：

image

二、特点

    1) 在非空二叉树中，第k层的结点总数不超过2^(k-1)，k>=1;

    2) 深度为k的二叉树最多有2k-1个结点(k>=1)，最少有k个结点;

    3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;

    4) 具有n个结点的完全二叉树的深度为log2(n+1);

    5)有n个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

        a、若m为结点编号则 如果m>1，则其父结点的编号为m/2；

        b、如果2*m<=n，则其左儿子（即左子树的根结点）的编号为2*m；若2*m>n，则无左儿子；

        c、如果2*m+1<=n，则其右儿子的结点编号为2m+1；若2m+1>n，则无右儿子。

    6）给定n个节点，能构成h(n)种不同的二叉树，其中h(n)为卡特兰数的第n项，h(n)=C(2*n, n)/(n+1)。

    7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i。