[此贴子已经被作者于2006-9-24 3:39:38编辑过]
[此贴子已经被作者于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时就是完全二叉树。
[此贴子已经被作者于2006-9-23 10:31:11编辑过]
你好!感谢你的精彩回答,可是你的程序是不是用delphi编写的呢?我没有学过delphi,有点看不懂,能不能用C语言实现呢?急……
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编辑过]
[此贴子已经被作者于2006-9-24 14:20:46编辑过]