2.txt

清华大学出版社严蔚敏编著数据结构习题答案

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.                      */
{QElemType p;
 Queue Q;
 int  flag=0;
 InitQueue(Q);
 EnQueue(Q,bt);
 while(!QueueEmpty(Q))
    {DeQueue(Q,p);
     if(!p)flag=1;
     else if(flag)return ERROR;
     else{ 
        EnQueue(Q,p->lchild);
        EnQueue(Q,p->rchild);
     }
 }
 return OK;
}