#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef char TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//////////////////////////////////////////////队列定义
typedef struct QNode
{
    BiTree data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
////////////////////////////////////队列的基本操作
void InitQueue(LinkQueue *Q)
{
    Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q->front) exit(0);
    Q->front->next=NULL;
}
void DestoryQueue(LinkQueue *Q)
{
    while(Q->front)//*******
    {
        Q->rear=Q->front->next;
        free(Q->front);
        Q->front=Q->rear;
    }
}
void EnQueue(LinkQueue *Q,BiTNode *e)
{
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(0);
    p->data=e;//说明这个结点的两个域1
    p->next=NULL;//2
    Q->rear->next=p;
    Q->rear=p;
}
void DeQueue(LinkQueue *Q,BiTree *e)
{
    QueuePtr p;
    if(Q->front==Q->rear) exit(0);
    p=Q->front->next;
    *e=p->data;
    Q->front->next=p->next;
//    free(p);
    if(Q->rear==p)
        Q->rear=Q->front;
    free(p);//
}
int QueueEmpty(LinkQueue *Q)
{
    if(Q->front==Q->rear)
        return(1);
    else
        return(0);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
BiTree CreatBiTree()//先序建立二叉链表
{
    TElemType ch;
    BiTree T;
    scanf("%c",&ch);
    if(ch==' ')
        T=NULL;
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        if(!T)
            exit(0);
        T->data=ch;
        T->lchild=CreatBiTree();
        T->rchild=CreatBiTree();
    }
    return T;
}



//判断是否为完全二叉树
int LayerTraverse(BiTree T)//通过层序遍历改编
{

    int flag=1;//默认其为完全二叉树
    LinkQueue queue;
    InitQueue(&queue);
    if(T)
        EnQueue(&queue,T);
    else
    {
        printf("该树为空树!\n");
        exit(0);
    }
    while(!QueueEmpty(&queue))
    {
        DeQueue(&queue,&T);   
        if((T==NULL)&&(!QueueEmpty(&queue)))//出队列元素是空指针且此时队列不为空，则可以判断该树不为完全二叉树,返回假值
        {
            flag=0;
            break;
        }
        if(T->lchild||T->rchild)//T->rchild
            break;
        else//有一个不为空就进队列
        {
            EnQueue(&queue,T->lchild);//左子树进队列
            EnQueue(&queue,T->rchild);//右子树进队列
        }            
    }
    return(flag);
}
void main()
{
    BiTree t;
    printf("<------------先序建树--------------->\n");
    printf("请按先序遍历序列输入二叉树中各个结点的值(字符)，若为空树时输入空格键:\n");
    printf("<参考数据:abc@@de@g@@f@@@，则用空格键表示@，输完后再输入一个回车键.>\n");
    t=CreatBiTree();
    printf("\n");
    printf("<------判断是否为完全二叉树操作---->\n");
    if(LayerTraverse(t))
        printf("该二叉树是完全二叉树!\n");
    else
        printf("该二叉树不是完全二叉树!\n");
}

明白了