sdutacm-数据结构实验之查找一：二叉排序树

数据结构实验之查找一：二叉排序树

TimeLimit: 400MS Memory Limit: 65536KB

SubmitStatistic

PRoblem Description

对应给定的一个序列可以唯一确定一棵二叉排序树。然而，一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列{3,1,4}和{3,4,1}插入初始为空的二叉排序树，都得到一样的结果。你的任务书对于输入的各种序列，判断它们是否能生成一样的二叉排序树。

Input

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (n <= 10)和L，分别是输入序列的元素个数和需要比较的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列生成一颗二叉排序树。随后L行，每行给出N个元素，属于L个需要检查的序列。简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

Output

对每一组需要检查的序列，如果其生成的二叉排序树跟初始序列生成的二叉排序树一样，则输出"Yes"，否则输出"No"。

Example Input

4 2

3 1 4 2

3 4 1 2

3 2 4 1

2 1

2 1

1 2

0

Example Output

Yes

No

No

Hint

Author

xam 

#include<stdio.h>#include<algorithm>#include<string.h>#include<iostream>#include<math.h>#include<queue>#include<stdlib.h>using namespace std;typedef struct node{   int 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,int 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,l;    while(~scanf("%d",&n))    {       if(n==0)       break;       scanf("%d",&l);       //top = 1;        int a[1002],b[1002],i;        for(i=0;i<n;i++)        scanf("%d",&a[i]);         //k = kkk = 0;         tree *root;        // o = strlen(a);         root = build(root,a,n);        // firstout(root);         //lastout(root);         for(i=0;i<l;i++)         {           top = 1;            for(int k=0;k<n;k++)        scanf("%d",&b[k]);           //kk=0;           tree*root2;//           oo = strlen(b);           root2 = build(root,b,n);          // 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: 172KBSubmit time: 2017-02-08 10:01:39****************************************************/