sdutacm-二叉排序树

二叉排序树

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

PRoblem Description

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

Input

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

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

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

Output

Example Input

2

123456789

987654321

432156789

0

Example Output

NO

NO

Hint

Author

#include<stdio.h>#include<algorithm>#include<string.h>#include<iostream>#include<math.h>#include<queue>#include<stdlib.h>using namespace std;typedef struct node{   char data;   struct node *l;   struct node *r;}tree;char c[1002],d[1002],cc[1002];int k,kk,kkk;void insert(tree*&root,int x){     if(root == NULL)     {        tree*p;        p = (tree*)malloc(sizeof(tree));        p->data = x;        p->l = NULL;        p->r = NULL;        root =  p;     }     else if(x<root->data)     {         insert(root->l,x);     }     else     {        insert(root->r,x);     }}tree* build(tree*root,char a[],int o){    root = NULL;    for(int i= 0;i< o;i++)    {       insert(root,a[i]);    }    return root;}int top;//控制空格输出void inout(tree*root){     if(root)     {         inout(root->l);         /*if(top)top=0;         else printf(" ");*/         printf("%d",root->data);         inout(root->r);     }}void firstout(tree*root){    if(root)    {       firstout(root->l);       c[k++] = root->data;       firstout(root->r);    }}void lastout(tree*root){    if(root)    {       firstout(root->l);       firstout(root->r);       cc[kkk++] = root->data;    }}void firstout2(tree*root){    if(root)    {       firstout(root->l);       d[kk++] = root->data;       firstout(root->r);    }}void qiangge(tree*root,tree* root2){    if(root&&root2)    {       if(root->data!=root2->data)top = 0;       else       {          qiangge(root->l,root2->l);          qiangge(root->r,root2->r);       }    }    else if(root&&!root2||!root&&root2)top = 0;}int main(){    int n,o,oo;    while(~scanf("%d",&n))    {       if(n==0)       break;       //top = 1;        char a[1002],b[1002],i;        scanf("%s",a);         //k = kkk = 0;         tree *root;         o = strlen(a);         root = build(root,a,o);        // firstout(root);         //lastout(root);         for(i=0;i<n;i++)         {           top = 1;           scanf("%s",b);           //kk=0;           tree*root2;           oo = strlen(b);           root2 = build(root,b,oo);          // firstout2(root2);           qiangge(root,root2);           if(top)printf("YES/n");           else printf("NO/n");           /*if(strcmp(c,d)==0)           printf("YES/n");           else if(strcmp(cc,d)==0)           printf("YES/n");           else if(strcmp(a,b)==0)           printf("YES/n");           else           printf("NO/n");*/         }    }   return 0;}/***************************************************User name: jk160505徐红博Result: AcceptedTake time: 0msTake Memory: 168KBSubmit time: 2017-02-08 09:53:39****************************************************/