主题:关于树的基本运算的问题
以下代码运行后只有A一个字符,估计是create函数出错,请高手解释,谢谢~~!
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}btnode;
btnode *creatbtnode(btnode *b,char *str)
{
btnode *st[MAXSIZE],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(': top++;st[top]=p;k=1;break;
case ')': top--;break;
case ',': k=2;break;
default : p=(btnode *)malloc(sizeof(btnode));
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(k)
{
case '1' : st[top]->lchild=p;break;
case '2' : st[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
return b;
}
btnode *findnode(btnode *b,char x)/*返回值域x的结点的指针*/
{
btnode *p;
if(b==NULL)
return NULL;
else if(b->data==x)
return b;
else
{
p=findnode(b->lchild,x);
if(p!=NULL)
return p;
else
return(findnode(b->rchild,x));
}
}
btnode *lchildnode(btnode *p)
{
return p->lchild;
}
btnode *rchildnode(btnode *p)
{
return p->rchild;
}
int btnodedepth(btnode *b)/*求树高*/
{
int lchilddep,rchilddep;
if(b==NULL)
return 0;
else
{
lchilddep=btnodedepth(b->lchild);
rchilddep=btnodedepth(b->rchild);
return((lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1));
}
}
void disbtnode(btnode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
disbtnode(b->lchild);
if(b->rchild!=NULL)
printf(",");
disbtnode(b->rchild);
printf(")");
}
}
}
int btnodewidth(btnode *b)
{
struct
{
int lno;/*结点层次编号*/
btnode *p;
}qu[MAXSIZE];
int front=0,rear=0;
int lnum,max,i,n;
if(b!=NULL)
{
rear++;
qu[rear].p=b;
qu[rear].lno=1;
while(rear!=front)
{
front++;
b=qu[front].p;
lnum=qu[front].lno;
if(b->lchild!=NULL)
{
rear++;
qu[rear].p=b->lchild;
qu[rear].lno=lnum+1;
}
if(b->rchild!=NULL)
{
rear++;
qu[rear].p=b->rchild;
qu[rear].lno=lnum+1;
}
}
max=0;
lnum=1;
i=1;
while(i<=rear)
{
n=0;
while(i<=rear&&qu[i].lno==lnum)
{
n++;
i++;
}
lnum=qu[i].lno;
if(n>max)max=n;
}
return max;
}
else
return 0;
}
int node(btnode *b)
{
int num1,num2;
if(b==NULL)
return 0;
else if(b->lchild==NULL&&b->rchild==NULL)
return 1;
else
{
num1=node(b->lchild);
num2=node(b->rchild);
return(num1+num2+1);
}
}
int leafnodes(btnode *b)
{
int num1,num2;
if(b==NULL)
return 0;
else if(b->lchild==NULL&&b->rchild==NULL)
return 1;
else
{
num1=leafnodes(b->lchild);
num2=leafnodes(b->rchild);
return(num1+num2);
}
}
void main()
{
btnode *b,*p,*lp,*rp;
b=creatbtnode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("(1)output tree: ");
disbtnode(b);
printf("\n");
printf("(2)H point: ");
p=findnode(b,'H');
if(p!=NULL)
{
lp=lchildnode(p);
if(lp!=NULL)
printf("left child is :%c ",lp->data);
else
printf("no child ");
rp=rchildnode(p);
if(rp!=NULL)
printf("right child is :%c ",rp->data);
else
printf("no child ");
}
printf("\n");
printf("(3)the depth :%d\n",btnodedepth(b));
printf("(4)the width :%d\n",btnodewidth(b));
printf("(5)the point :%d\n",node(b));
printf("(6)the leafpoint :%d\n",leafnodes(b));
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}btnode;
btnode *creatbtnode(btnode *b,char *str)
{
btnode *st[MAXSIZE],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(': top++;st[top]=p;k=1;break;
case ')': top--;break;
case ',': k=2;break;
default : p=(btnode *)malloc(sizeof(btnode));
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(k)
{
case '1' : st[top]->lchild=p;break;
case '2' : st[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
return b;
}
btnode *findnode(btnode *b,char x)/*返回值域x的结点的指针*/
{
btnode *p;
if(b==NULL)
return NULL;
else if(b->data==x)
return b;
else
{
p=findnode(b->lchild,x);
if(p!=NULL)
return p;
else
return(findnode(b->rchild,x));
}
}
btnode *lchildnode(btnode *p)
{
return p->lchild;
}
btnode *rchildnode(btnode *p)
{
return p->rchild;
}
int btnodedepth(btnode *b)/*求树高*/
{
int lchilddep,rchilddep;
if(b==NULL)
return 0;
else
{
lchilddep=btnodedepth(b->lchild);
rchilddep=btnodedepth(b->rchild);
return((lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1));
}
}
void disbtnode(btnode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
disbtnode(b->lchild);
if(b->rchild!=NULL)
printf(",");
disbtnode(b->rchild);
printf(")");
}
}
}
int btnodewidth(btnode *b)
{
struct
{
int lno;/*结点层次编号*/
btnode *p;
}qu[MAXSIZE];
int front=0,rear=0;
int lnum,max,i,n;
if(b!=NULL)
{
rear++;
qu[rear].p=b;
qu[rear].lno=1;
while(rear!=front)
{
front++;
b=qu[front].p;
lnum=qu[front].lno;
if(b->lchild!=NULL)
{
rear++;
qu[rear].p=b->lchild;
qu[rear].lno=lnum+1;
}
if(b->rchild!=NULL)
{
rear++;
qu[rear].p=b->rchild;
qu[rear].lno=lnum+1;
}
}
max=0;
lnum=1;
i=1;
while(i<=rear)
{
n=0;
while(i<=rear&&qu[i].lno==lnum)
{
n++;
i++;
}
lnum=qu[i].lno;
if(n>max)max=n;
}
return max;
}
else
return 0;
}
int node(btnode *b)
{
int num1,num2;
if(b==NULL)
return 0;
else if(b->lchild==NULL&&b->rchild==NULL)
return 1;
else
{
num1=node(b->lchild);
num2=node(b->rchild);
return(num1+num2+1);
}
}
int leafnodes(btnode *b)
{
int num1,num2;
if(b==NULL)
return 0;
else if(b->lchild==NULL&&b->rchild==NULL)
return 1;
else
{
num1=leafnodes(b->lchild);
num2=leafnodes(b->rchild);
return(num1+num2);
}
}
void main()
{
btnode *b,*p,*lp,*rp;
b=creatbtnode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("(1)output tree: ");
disbtnode(b);
printf("\n");
printf("(2)H point: ");
p=findnode(b,'H');
if(p!=NULL)
{
lp=lchildnode(p);
if(lp!=NULL)
printf("left child is :%c ",lp->data);
else
printf("no child ");
rp=rchildnode(p);
if(rp!=NULL)
printf("right child is :%c ",rp->data);
else
printf("no child ");
}
printf("\n");
printf("(3)the depth :%d\n",btnodedepth(b));
printf("(4)the width :%d\n",btnodewidth(b));
printf("(5)the point :%d\n",node(b));
printf("(6)the leafpoint :%d\n",leafnodes(b));