6.49.c

数据结构习题及答案

6.49④ 编写算法判别给定二叉树是否为完全二叉树。

要求实现下列函数：
Status CompleteBiTree(BiTree bt);
/* judge if the binary tree whose root is bt */
/* is a complete tree.                       */

二叉链表类型定义：
typedef struct BiTNode {
    TElemType data;
    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 bt)
/* judge if the binary tree whose root is bt */
/*  is a complete tree.                      */
{    
  Queue Q;
  int exist=1;
  struct BiTNode *p;
  InitQueue(Q);
  EnQueue(Q,bt);
  if(!bt) return TRUE;
  else{
     while(!QueueEmpty(Q))
       {
        DeQueue(Q,p);
        if(p->lchild)
            {if(exist==1) EnQueue(Q,p->lchild);
             else return FALSE;}
        else exist=0;
        if(p->rchild)
            {if(exist==1) EnQueue(Q,p->rchild);
             else return FALSE;}
        else exist=0;
        }//while
     return TRUE;
  }//else
}