數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)之查找一：二叉排序樹

TimeLimit: 400MS Memory Limit: 65536KB

SubmitStatistic

PRoblem Description

對應(yīng)給定的一個(gè)序列可以唯一確定一棵二叉排序樹。然而，一棵給定的二叉排序樹卻可以由多種不同的序列得到。例如分別按照序列{3,1,4}和{3,4,1}插入初始為空的二叉排序樹，都得到一樣的結(jié)果。你的任務(wù)書對于輸入的各種序列，判斷它們是否能生成一樣的二叉排序樹。

Input

輸入包含若干組測試數(shù)據(jù)。每組數(shù)據(jù)的第1行給出兩個(gè)正整數(shù)N (n <= 10)和L，分別是輸入序列的元素個(gè)數(shù)和需要比較的序列個(gè)數(shù)。第2行給出N個(gè)以空格分隔的正整數(shù)，作為初始插入序列生成一顆二叉排序樹。隨后L行，每行給出N個(gè)元素，屬于L個(gè)需要檢查的序列。簡單起見，我們保證每個(gè)插入序列都是1到N的一個(gè)排列。當(dāng)讀到N為0時(shí)，標(biāo)志輸入結(jié)束，這組數(shù)據(jù)不要處理。

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****************************************************/