一二叉树用二叉链表形式存放，请写一算法，判断此二叉树是否是完全二叉树？想了好久没有想出，不知哪位高手能够会。

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

function out0_2(T: bitreptr): boolean;
function out02 (T1,T2: bitreptr):boolean;
begin
if (T1=nil) and (T2=nil) then out02:=true
else if (T1=nil) or (T2=nil) then out02:=false
else out02:=out02(T1^.lchild,T1^.rchild) and
out02(T2^.lchild,T2^.rchild);
end;
begin
if T=nil then out0_2:=true
else begin
out0_2:=out02(T^.lchild,T^.rchild);
end;
end;

function high(T: bitreptr): integer;
function max(a,b:integer):integer;
begin
if a>b then max:=a
else max:=b;
end;
begin
if T=nil then high:=0
else
high:=max(high(T^.lchild),high(T^.rchild))+1;
end;

function LTallThanR(T: bitreptr): boolean;
begin
if T=nil then LTallThanR:=true
else
if (high(T^.lchild)>=high(T^.rchild)) and
(high(T^.lchild)<=high(T^.rchild)+1) then LTallThanR:=true
else LTallThanR:=false;
end;

好像没有错了，思路：二叉树的结点满足出度要么为0，要么为2，用function out0_2(T: bitreptr): boolean;来判断，还要满足相对于某个结点，右子树高度<=左子树高度<=右子树高度+1。用function LTallThanR(T: bitreptr): boolean;判断，当同时满足这两个条件时，就时完全二叉树。即out0_2(T) and LTallThanR(T)=true时就是完全二叉树。

delphi下若干组数据测试通过， 先序遍历的数据
'ABD##E##C##';
'Ab##c##';
'ABCD#####';
'ABD###C##';
'ABDH##I##E##CF##G##';
'AB##CD##E##';

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

把上面(high(T^.lchild)>=high(T^.rchild)) and (high(T^.lchild)<=high(T^.rchild)+1)改为
high(T^.lchild)=high(T^.rchild)就是满二叉树的判断了。

你好！感谢你的精彩回答，可是你的程序是不是用delphi编写的呢？我没有学过delphi，有点看不懂，能不能用C语言实现呢？急……

那是pascal

bool out02 (bitreptr T1,T2);
{
if (T1==null) && (T2==null) return(true);
else if (T1==null) || (T2==null) return(false);
else return(out02(T1->lchild,T1->rchild) &&
out02(T2->lchild,T2->rchild));
}

bool out0_2(bitreptr T);
{
if (T==null) return(true);
else
return(out02(T->lchild,T->rchild));
}

int max(a,b:integer);
{
if （a>b） return(a);
else return(b);
}

int high(bitreptr T);
{
if (T==null) return(0);
else
return(max(high(T->lchild),high(T->rchild))+1);
}

bool LTallThanR(bitreptr T);
{
if (T==null) Return(true);
else
if (high(T->lchild)>=high(T->rchild)) &&
(high(T->lchild)<=high(T->rchild)+1) Return(true);
else Return(false);
}

你看看对不对，算法跟上面的pascal的是一样的，函数名也一样，不对的话也应该是修改的错误，我是在word上改的。

发现我犯了个概念性的错误，完全二叉树要满足“右子树高度<=左子树高度<=右子树高度+1”，但不需要每个结点的出度都为0或2，可以有1个结点的出度为1，其它的结点出度为0或2。暂时还没想到办法处理这个情况，待续......

[此贴子已经被作者于2006-9-24 1:56:15编辑过]

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

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

楼主和我一样，犯了个出度都为0或2的概念性的错误。

下面是我的算法(不能再有错了吧)，用层序遍历算法采用链队列存放二叉树。delphi下测试了下面几组数据通过：
//下面是先序遍历的二叉树
//s:='ABD##E##C##';
//s:='ABD##E##CF##G##';
//s:='Ab##c##';
//s:='ABCD#####';
//s:='ABD###C##';
//s:='ABDH##I##E##CF##G##';
//s:='AB##CD##E##';
//s:='A#B##';
//s:='AB##CD###';
//s:='ABD###C##'; 注意这棵也是二叉树。

树和队列结构
type
bitreptr=^bnodetp;
bnodetp=record
data:char;
lchild, rchild: bitreptr;
end;
queueptr=^qnodetp;
qnodetp=record
tr_adr:bitreptr;
next:queueptr;
end;
qheadptr=^qheadtp;
qheadtp=record
front,rear:queueptr;
end;

{判断是否完全二叉树，层序遍历}
function TForm1.iscompletebitre(bt: bitreptr): boolean;
var
la:qheadptr;
p:queueptr;
mantre:boolean;
nomorechild:boolean;
begin
mantre:=true; nomorechild:=false;
if bt<>nil then
begin
new(la); la^.front:=nil;la^.rear:=nil; p:=nil;
enqueue(la,bt);
while (not emptyqueue(la)) and mantre do
begin
dequeue(la,p);
if (p^.tr_adr^.lchild<>nil) and (p^.tr_adr^.rchild<>nil) then
begin
if not nomorechild then
begin
enqueue(la,p^.tr_adr^.lchild);
enqueue(la,p^.tr_adr^.rchild);
end
//当结点A后的结点P有左右孩子，但结点A已显示后面的结点不再有孩子时，
//整棵树不是完全二叉树
else mantre:=false;
end
else if (p^.tr_adr^.lchild<>nil) and (p^.tr_adr^.rchild=nil) then
begin
//当结点P有左没右孩子，且前面的结点未显示后面的结点没孩子
//nomorechild标记结点P后的结点不得有孩子
if not nomorechild then
begin
enqueue(la,p^.tr_adr^.lchild);
nomorechild:=true;
end
//当结点A后的结点P有左没右孩子，但结点A已显示后面的结点不再有孩子时，
//整棵树不是完全二叉树
else mantre:=false;
end
//当结点没有左右孩子时，后面的结点不得再有孩子
else if(p^.tr_adr^.lchild=nil) and (p^.tr_adr^.rchild=nil) then
nomorechild:=true
//当结点没左有右孩子时，整棵树不是完全二叉树
else mantre:=false;
end;
end;
iscompletebitre:=mantre;
end;

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