Question

编写程序判别给定二叉树是否为完全二叉树。

Answer 1

int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0
{int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大
if(p==null) return (1);
QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队
while (!QueueEmpty(Q))
{p=QueueOut(Q); //出队
if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队
else {if (p->lchild) return 0; //前边已有结点为空，本结点不空
else tag=1; //首次出现结点为空
if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队
else if (p->rchild) return 0; else tag=1;
} //while
return 1; } //JudgeComplete

Answer 2

bool check(BiTree T)
{ if (T == NULL) return false;
queue<BiTree> Q;
Q.push(T); while (!Q.empty())
{
BiTree p = Q.front();
Q.pop(); if (p->left && p->right) {
Q.push(p->left);
Q.push(p->right);
} else if(p->right && p-left == NULL) return false; else
{ if(p->left && p-right == NULL)
Q.push(p->left); while(!Q.empty())
{
p = Q.front(); Q.pop(); if(p->left || p->right) return false;
}

}
} return true;
}