[数据结构与算法]判断完全二叉树（21.6.13）

题目描述：

二叉树用二叉链表形式存储，写一个判别二叉树是否为完全二叉树的算法。

算法思想：

根据完全二叉树的定义，具有n个结点的完全二叉树和满二叉树中1~n的结点一一对应。可以利用层次遍历，将所有的结点加入队列（包括空结点）。遇到空结点时，查看其后是否有非空的结点。若有则不是完全二叉树。

代码如下：

bool IsComplete(BiTree T){
	InitQueue(Q);
	if(!T)
		return 1; //空树也为完全二叉树 
	EnQueue(Q,T);
	while(!IsEmpty(Q)){
		DeQueue(Q,p);
		if(p){  //结点非空，将左、右子树入队列 
			EnQueue(Q,p->lchild);
			EnQueue(Q,p->rchild);
		}
		else
			while(!IsEmpty(Q)){
				DeQueue(Q,p);
				if(p)
					return 0;
			}
	}
	return 1;
}