算法思路来自博客：http://blog.csdn.net/wuruiaoxue/article/details/46797815
要判断一颗二叉树是否为完全二叉树，首先应该看一下完全二叉树的定义：
完全二叉树（来自数据结构课本的定义）：约定从根起，自上而下，自左而右，给满二叉树中的每个结点从1到n连续编号，编号为i的结点可称为i结点。深度为k且且含n个结点的二叉树，如果其每个结点都与深度为k的满二叉树中编号从1至n一一对应，则称为完全二叉树。
有定义可见，“从根起，自上而下，自左而右”。可见我们应该用层次遍历的思路。
层次遍历二叉树：按二叉树的层次从小到大且每层从左到右的顺序一次访问结点。
来看看算法思路：
根据完全二叉树的定义，对完全二叉树按照从上到下、从左到右的层次遍历，应该满足一下两条要求：
●某节点没有左孩子，则一定无右孩子
●若某节点缺左或右孩子，则其所有后继一定无孩子
若不满足上述任何一条，均不为完全二叉树。
算法思路：采用层序遍历算法，用cm变量值表示迄今为止二叉树为完全二叉树（其初值为1，一旦发现不满足上述条件之一，则置cm为0），bj变量值表示迄今为止所有节点均有左右孩子（其初值为1），一旦发现一个节点没有左孩子或没有右孩子时置bj为0），在遍历完毕后返回cm的值。
来看代码：（直接上anyview的代码）
/********** 【题目】编写算法判别给定二叉树是否为完全二叉树。 二叉链表类型定义： typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; 可用队列类型Queue的相关定义： typedef BiTree QElemType; // 设队列元素为二叉树的指针类型 Status InitQueue(Queue &Q); Status EnQueue(Queue &Q, QElemType e); Status DeQueue(Queue &Q, QElemType &e); Status GetHead(Queue Q, QElemType &e); Status QueueEmpty(Queue Q); **********/ Status CompleteBiTree(BiTree T) /* 判别二叉树T是否为完全二叉树 */ { if(T==NULL)return TRUE;//空树肯定是啦 //要用层次遍历 Queue Q; InitQueue(Q); BiTree p = T; int cm = 1;//用cm变量值表示迄今为止二叉树为完全二叉树（其初值为1，一旦发现不满足上述条件之一，则置cm为0 //结束后返回cm的值 int bj = 1;//bj变量值表示迄今为止所有节点均有左右孩子（其初值为1），一旦发现一个节点没有左孩子或没有右孩子时置bj为0 if( !p->lchild && p->rchild )return FALSE;//如果根只有右子树，没有左子树，肯定就不是 EnQueue(Q, p); while(DeQueue(Q, p)==OK && cm) { if(p->lchild && p->rchild) { if(bj==0)cm = 0;//bj为0说明上一颗树没有右孩子或者说两个孩子都没，所以这棵树不能有孩子 EnQueue(Q, p->lchild); EnQueue(Q, p->rchild); } if(p->lchild && !p->rchild) { //如果这棵树只有左子树，在队列后面那颗树一定不能有孩子 if(bj==0)cm = 0;//bj为0说明上一颗树没有右孩子或者说两个孩子都没，所以这棵树不能有孩子 EnQueue(Q, p->lchild); bj = 0; } if(!p->lchild && p->rchild) { //只有右孩子，没有左孩子直接判死刑 cm = 0; } if(!p->lchild && !p->rchild) { //两个孩子都没有，则队列中的下一个元素不能有孩子 bj = 0; } } return cm; }