SDUTACM 二叉排序树

╰+哭是因爲堅強的太久メ 2022-07-19 06:20 150阅读 0赞

## 题目描述 ##

二叉排序树的定义是：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 今天我们要判断两序列是否为同一二叉排序树

## 输入 ##

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。

接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉排序树。

接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉排序树。(数据保证不会有空树)

## 输出 ##

## 示例输入 ##

2
    123456789
    987654321
    432156789
    0

## 示例输出 ##

NO
    NO

我的代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    struct hh 
    {
        int data;
     struct hh *l;
     struct hh *r;
    };
    int k;
    int pqx[20],b,phx[20];
    struct hh *creat(struct hh *p,int x)
    {
     if(p==NULL)
     {
      p=(struct hh *)malloc(sizeof(struct hh));
      p->data=x;
      p->l=NULL;
      p->r=NULL;
     }
     else
     {
      if(x<p->data)
       p->l=creat(p->l,x);
      else
          p->r=creat(p->r,x);
     }
     return p;
    }
    void inp(struct hh *p)
    {
     if(p!=NULL)
     {
      pqx[b++]=p->data;
      inp(p->l);
      inp(p->r);
     }
    }
    void postp(struct hh *p)
    {
     if(p!=NULL)
     {
      postp(p->l);
      postp(p->r);
      phx[b++]=p->data;
     }
    }
    void main()
    {
        int n,i,m,x,l,j;
     struct hh *p,*t;
     char a[20],d[20];
     while(scanf("%d",&n)!=EOF)
     {
      if(n==0)
       break;
      else
      {
                scanf("%s",&d);
                m=strlen(d);
       p=NULL;
          for(i=0;i<m;i++)
       {
                    x=d[i]-'0';
           p=creat(p,x);
       }
          for(i=0;i<n;i++)
       {
        k=1;
        t=NULL;
        scanf("%s",&a);
        l=strlen(a);
        if(l!=m)
        {
         k=0;
         printf("NO\n");
        }
        else
        {
         b=0;
         postp(p);//后续
         b=0;
         inp(p);//前序
         int sum=0;
         for(j=0;j<l;j++)
         {
          //printf("%d#%d\n",pqx[j],a[j]-'0');
          if(pqx[j]!=a[j]-'0')
          {
           sum++;
           break;
          }
         }
         //printf("--------\n");
         for(j=0;j<l;j++)
         {
          //printf("%d#%d\n",phx[j],a[j]-'0');
          if(phx[j]!=a[j]-'0')
          {
           sum++;
           break;
          }
         }
         //printf("--------\n");
         for(j=0;j<l;j++)
         {
          //printf("%d#%d\n",d[j]-'0',a[j]-'0');
          if(d[j]-'0'!=a[j]-'0')
          {
           sum++;
              break;
          }
         }
         if(sum==3)
         {
                            k=0;
          printf("NO\n");
         }
         if(k==1)
          printf("YES\n");
        }
       }
      }
     }
    }