一棵二叉树用二叉链表存储，如何判断此二叉树是否是完全二叉树?想了好久没有想出……

[此贴子已经被作者于2006-9-24 3:23:14编辑过]

除叶子结点那一层以上的是一个满二叉树.
叶子结点始终往左靠,就是说,如果左边没有排满,就不可以放在右边.

是用先序，中序，后序还是按层，如果按层的化，只要判断i个结点是后2i个结点的双亲就行，又怎么知道i个结点是否是后2i个结点的双亲……
哦，对了！
可以先求出树的深度K，在求出如果是完全二叉树的话，Ｋ－１层的结点个数,
按层遍历，判断每一个结点是否有左右孩子，如果除最后一个结点有左孩子，或者所有结点都有左右孩子，那么就可判断此二叉树是完全二叉树，否则此二叉树不是完全二叉树。不知对不对呢？

[此贴子已经被作者于2006-9-23 11:10:29编辑过]

恩,就是按层遍历,但你的方法有点问题,
应该是这样:
1.当检查当某个接点只有右儿子时,则退出
2.当检查到某个接点只有左儿子或则没有儿子接点,
这时要保证接下去遍历的接点都没有儿子,才是完全二叉树

我编写了下面的代码，不知对不对，高手指教……

算法思想：按层次遍历，先找出结点中左右孩子都没有的第一个结点，然后判断其后的结点是不是都没有左右孩子，如果是则返回0,是完全二叉树，否则不是完全二叉树。

typedef struct node {
char data;
struct node *leftchile,*rightchile;
}Bitree;

int wanqutree(Bitree *bt)
{
Bitree *p;
Bitree *Q[MAXSIZE]; //定义队列，用于存取树结点的地址
int front,rear;
if(bt==NULL)return;
front=0;
rear=0;
Q[rear++]=bt; //初始化队列
p=bt;
while((front!=rear)&&(p->leftchile!=NULL)&&(p->rightchile!=NULL))
{ //此循环找到其左右孩子均为空的结点
Q[rear++]=p->leftchile;
Q[rear++]=p->rightchile;
p=Q[front];
}
while(front!=rear) //此循环判断上循环找到的结点以后的
{ 结点其左右孩子是不是都为空，如果是
p=Q[front++]; 则返回0，此树是完全二叉树
if((p->leftchile!=NULL)||(p->rightchile!=NULL))
return 0;
}
return 1; //不是完全二叉树则返回1
}

[此贴子已经被作者于2006-9-24 3:18:47编辑过]

判断每个结点:当出现某个结点有右孩子而没有左孩子则结束返回0,或者第一次出现只有左孩子(或没有孩子)时,做个标记,以后如果碰到某个结点有孩子则结束返回0.上述两个都没有出现则返回1.
flag=0;
while(p!=NULL)
{
if(p->lchild==NULL&&p->rchild)
{
return(0);
}
if(p->rchild==NULL)
{
flag=1;
}
if(flag==1&&p->lchild!=NULL||p->rchild!=NULL)
{
return(0);
}
...进队...
...改变p的值...
}
return(1);
}
/*自己的程序对不对,写个主函数测试就知道了,但根据楼主的思想,应该有疏漏,不是找第一个没有左右孩子的.假如前面有个只有右孩子的,此时就可以判断它不是完全二叉树.*/

版主nuciewth的好像容易理解，谢谢了！