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

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

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

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

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

算法思想：按层次遍历，先找出结点中左右孩子都没有的第一个结点，然后判断其后的结点是不是都没有左右孩子，如果是则返回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编辑过]

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