题目链接:http://acm.sdibt.edu.cn:8080/judge/contest/contest/view.action?cid=347#problem/A
做完这道题之后,感觉方法不好,看了别人的解题报告发现用顺序存储的树来实现这题更简单,更高效,下面是我的思路,也算是个方法吧!
#include <stdio.h>
#include <stdlib.h>
typedef struct treenode
{
   char date;
   int l,r;
   struct treenode *lch,*rch;
}node;
node *set(int n)
{
  char x;
  int a,b,i,j;
  node *p;
  node *q[1000];//用来存各结点的指针
   p=(node *)malloc(sizeof(node));
   q[1]=p;
   getchar();
   scanf("%c%d%d",&x,&a,&b);
   p->date=x;
   p->l=a;
   p->r=b;
   p->lch=NULL;
   p->rch=NULL;
   q[1]=p;
  for(i=2;i<=n;i++)
  {
    p=(node *)malloc(sizeof(node));
   q[i]=p;
    getchar();
    scanf("%c%d%d",&x,&a,&b);
    p->date=x;
    p->l=a;
    p->r=b;
 p->lch=NULL;
 p->rch=NULL;
 for(j=1;j<=i;j++)//找当前结点的parent,并链接到parent
 {
  if(q[j]->l!=0)
  {
   q[j]->lch=p;
   q[j]->l=0;
   break;
  }
  if(q[j]->r!=0)
  {
   q[j]->rch=p;
   q[j]->r=0;
   break;
  }
 }
  } 
  return q[1];
}
void preoder(node *p)
{
if(p!=NULL)
{ printf("%c",p->date);
    preoder(p->lch);
preoder(p->rch);
}
}
void inoder(node *p)
{
    if(p!=NULL)
 {
    inoder(p->lch);
        printf("%c",p->date);
    inoder(p->rch);
}
}
void postoder(node *p)
{
    if(p!=NULL)
{
    postoder(p->lch);
postoder(p->rch);
        printf("%c",p->date);
}
}
int main()
{
int m,n,i;
node *head;
scanf("%d",&m);
    for(i=1;i<=m;i++)
{
scanf("%d",&n);
head=set(n);
printf("Case %d:",i);
        printf("\n");
preoder(head);
printf("\n");
inoder(head);
printf("\n");
postoder(head);
printf("\n");
}
return 0;
}
欢迎指点!

发表评论

电子邮件地址不会被公开。

Post Navigation