2016年数据结构第五题(判断用二叉链表表示的树是否为完全二叉树）（C/C++)

题目：

代码实现：

#include
using namespace std;

#define TElemType int
typedef struct BiTNode{
 TElemType data;
 struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T)//按照先序遍历的顺序建立二叉链表
{
 int ch;
 cin>>ch;
 if(ch==9999)T=NULL;
 else
 {
  T=new BiTNode;
  T->data=ch;
  CreateBiTree(T->lchild);
  CreateBiTree(T->rchild);
 }
}

#define MAXQSIZE 100
#define QElemType BiTNode*
typedef struct{
 QElemType *base;
 int front;
 int rear;
}SqQueue;

bool InitQueue(SqQueue &Q)//初始化队列
{
 Q.base=new QElemType[MAXQSIZE];
 if(!Q.base)exit(EOVERFLOW);
 Q.front=Q.rear=0;
 return true;
}

int QueueLength(SqQueue Q)//测队列长度
{
 return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

bool EnQueue(SqQueue &Q,QElemType e)//入队
{
 if((Q.rear+1)%MAXQSIZE==Q.front)return false;
 Q.base[Q.rear]=e;
 Q.rear=(Q.rear+1)%MAXQSIZE;
 return true;
}

bool DeQueue(SqQueue &Q,QElemType &e)//出队
{
 if(Q.front==Q.rear)return false;
 e=Q.base[Q.front];
 Q.front=(Q.front+1)%MAXQSIZE;
 return true;
}

QElemType GetHead(SqQueue Q)//取队头元素
{
 if(Q.front!=Q.rear)return Q.base[Q.front];
}

void DestroyQueue(SqQueue &Q)//销毁队列
{
 delete Q.base;
 Q.base=NULL;
}

//本题解答............................................................................
void JudgeTree(BiTree &T)
{
 int length,depth=0,first=0,flag=0;
 QElemType e;//用于保存出队元素
 SqQueue Q;  //之后二叉树T每一层的结点地址都将入此队列Q
 InitQueue(Q);
 
 EnQueue(Q,T);
 while(QueueLength(Q))
 {
  depth++;//该变量最后的值就是二叉树有多少层
  length=QueueLength(Q);
  for(int i=length;i>0;i--)
  {
   DeQueue(Q,e);
   if(e->lchild)EnQueue(Q,e->lchild);
   if(e->rchild)EnQueue(Q,e->rchild);
   if(!e->lchild&&e->rchild)
   {
    printf("n二叉树T不是完全二叉树!n");
    DestroyQueue(Q);//销毁队列
    return;
   }
   if(!e->lchild&&!e->rchild&&flag==0)//当第一个叶子结点出现时，记录下其所在的层次
   {
     first=depth;
     flag=1;
   }
   if((!e->lchild&&!e->rchild)||(e->lchild&&!e->rchild))
   {  //叶子结点的下一个一定是叶子结点，只有左孩子没有右孩子的结点的下一个一定也是叶子结点
    if(QueueLength(Q))
    {
      if(GetHead(Q)->lchild||GetHead(Q)->rchild)
      {
        printf("n二叉树T不是完全二叉树!n");
        DestroyQueue(Q);//销毁队列
        return;
      }
    }
   }
  }
 }
 //完全二叉树的叶子结点只可能在层次最大的两层上出现
 if((depth-first)>1)printf("n二叉树T不是完全二叉树!n");
 else printf("n二叉树T是完全二叉树!n");
 DestroyQueue(Q);//销毁队列
}
//....................................................................................

void DestroyTree(BiTree &T)//销毁二叉树
{
 if(T!=NULL)
 {
  DestroyTree(T->lchild);
  DestroyTree(T->rchild);
  printf("销毁结点: %dn",T->data);
  delete T;
  T=NULL; 
 }
 return;
}

int main()
{
 BiTree T;//二叉树T
 printf("n构造二叉树T:n");
 CreateBiTree(T);//按照先序遍历的顺序建立二叉链表
 JudgeTree(T); //判断T是否为完全二叉树(本题解答)
 DestroyTree(T);//销毁二叉树 
}

算法思想：
设置队列，每一次将每层结点地址入队并依次出队，发现了叶子结点，不但要记下第一个叶子节点的层次以保证其在树的倒数两个层次，还要确保每个叶子结点的下一个也是叶子结点，并且只有左孩子的结点之后的结点应当全是叶子节点。这些条件都满足了，树T才能为完全二叉树