怎么判断一个二叉树是否是完全二叉树?
如题;
假如一个二叉树,用二叉链表方式存储;
那么如何判断该二叉树是否是完全二叉树?
[解决办法]
采用层次遍历：
bool IsFullBitree(BinNode * T)//
{
queue<BinNode *> Q;
BinNode *p;
bool flag=false;
if(T!=0)
{
Q.push(T);
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(!p)
flag=true;
else if(flag)
return false;
else
{
Q.push(p->lchild);
Q.push(p->rchild);
}
}
}
return true;
}
[解决办法]
给个思路， 同时满足下面几个条件的：
1. 左、右子树都是完全二叉树
2. 左子树的高度和右子树一样或大1
3. 若左子树比右子树高度大1，则右子树必须是满的（节点数等于2^高度-1）
4. 若左子树和右子树高度一样，左子树必须是满的
满足上面几点的就是完全二叉树，写个递归程序遍历一边，算出层数、节点数以及是否完全二叉树等信息，就可以很容易判断。应该不难
[解决办法]
1.当检查当某个接点只有右儿子时,则退出
2.当检查到某个接点只有左儿子或没有儿子接点,这时要保证接下去遍历的结点都没有儿子,才是完全二叉树,所以设置一个flag标记，一旦发现这种情况，就标记，再取下一个结点的时候因为flag已被标记，所以判断是否没有儿子，如果有，那么就不是完全二叉树，如果队列取空时，都没有出现有儿子的结点，那么就是完全二叉树。
可以画图思考一下。
