데이터 구조의 이 진 트 리 - 이 진 트 리 를 구 한 후 순차 적 으로 옮 겨 다 니 고 차원 적 으로 옮 겨 다 니 기 (먼저 나 무 를 만 들 고 다시 옮 겨 다 니 기)

데이터 구조 실험 에서 이 진 트 리 의 순서 와 차원 을 찾 습 니 다.
Time Limit: 1000MS Memory limit: 65536K
제목 설명
 이 진 트 리 의 앞 순 서 를 알 고 있 습 니 다. 이 진 트 리 의 뒤 순 서 를 찾 습 니 다.
입력
 입력 데 이 터 는 여러 그룹 이 있 고 첫 번 째 줄 은 정수 t (t < 1000) 이 며 t 조 테스트 데 이 터 를 대표 합 니 다.각 조 는 길이 가 50 보다 작은 문자열 두 개 를 포함 하고 첫 번 째 문자열 은 이 진 트 리 의 우선 순 서 를 나타 내 며 두 번 째 문자열 은 이 진 트 리 의 중간 순 서 를 나타 낸다.
출력
각 조 의 첫 번 째 줄 은 이 진 트 리 의 뒷 순 서 를 출력 하고 두 번 째 줄 은 이 진 트 리 의 차원 을 출력 합 니 다.
예제 입력

2

abdegcf

dbgeafc

xnliu

lnixu

예제 출력

dgebfca

abcdefg

linux

xnuli


      ：        ，    、         ！    ，      ！
           ：

#include <iostream>

#include <iomanip>

#include <string>

#include <string.h>

#include <stdio.h>

#include <algorithm>

#include <queue>

#include <vector>



using namespace std;



typedef struct node

{

    char a;

    struct node *ll;

    struct node *rr;

}Binode, *tree;



void build(int len, char *s1, char *s2, char *s) //         

{

    if(len<=0)

      return;

    int pos; //  

    int i;



    for(i=0; i<len; i++)

    {

        if(s2[i]==s1[0])

        {

            pos=i;

            break;

        }

    }

    build(pos, s1+1, s2, s );

    build(len-pos-1, s1+pos+1, s2+pos+1, s+pos );

    s[len-1]=s1[0];

}





//        

struct node*creat(struct node *root, char *s, char *s1, int n)

{

    if(n<=0)

      return NULL;

    root=new node;

    root->a=s[0];



    int p=strchr(s1, s[0] )-s1;



    root->ll=creat( root->ll, s+1, s1, p );

    root->rr=creat( root->rr, s+p+1, s1+p+1, n-p-1 );



    return root;

}





//        

void Level_Order(tree root)

{

    queue<tree>q;

    tree qq;



    if(root==NULL)

      return ;

    Binode *p=root;

    cout<<(p->a);



    if(p->ll)

      q.push( p->ll );

    if(p->rr)

      q.push( p->rr );



    while(!q.empty())

    {

        qq=q.front();

        q.pop();

        cout<<qq->a;

        if(qq->ll)

          q.push(qq->ll);

        if(qq->rr)

          q.push(qq->rr);

    }

    return;

}

int main()

{

    int t;

    cin>>t;

    char s1[100], s2[100];

    char s3[100];

    while(t--)

    {

        memset(s3, '\0', sizeof(s3));



        scanf("%s", s1); //  

        scanf("%s", s2); //  

        int len=strlen(s1);

        build(len, s1, s2, s3);

        printf("%s
", s3); //      



        //      

        tree root, tt;

        root=creat(tt, s1, s2, len);



        Level_Order( root);

        cout<<endl;

    }

    return 0;

}

 
 

     ：     、    ，            
     ：

#include <iostream>

#include <iomanip>

#include <string>

#include <string.h>

#include <stdio.h>

#include <algorithm>

#include <queue>

#include <vector>



using namespace std;



typedef struct node

{

    char a;

    struct node *ll;

    struct node *rr;

}Binode, *tree;





//        

struct node*creat(struct node *root, char *s, char *s1, int n)

{

    if(n<=0)

      return NULL;

    root=new node;

    root->a=s[0];



    int p=strchr(s1, s[0] )-s1;



    root->ll=creat( root->ll, s+1, s1, p );

    root->rr=creat( root->rr, s+p+1, s1+p+1, n-p-1 );



    return root;

}



void postorder(tree p)

{

    if(p)

    {

        postorder(p->ll);

        postorder(p->rr);

        printf("%c", p->a );

    }

}



//        

void Level_Order(tree root)

{

    queue<tree>q;

    tree qq;



    if(root==NULL)

      return ;

    Binode *p=root;

    cout<<(p->a);



    if(p->ll)

      q.push( p->ll );

    if(p->rr)

      q.push( p->rr );



    while(!q.empty())

    {

        qq=q.front();

        q.pop();

        cout<<qq->a;

        if(qq->ll)

          q.push(qq->ll);

        if(qq->rr)

          q.push(qq->rr);

    }

    return;

}





int main()

{

    int t;

    cin>>t;

    char s1[100], s2[100];

    char s3[100];



    while(t--)

    {

        memset(s3, '\0', sizeof(s3));



        scanf("%s", s1); //  

        scanf("%s", s2); //  

        int len=strlen(s1);



        //      

        tree root, tt;

        root=creat(tt, s1, s2, len);

        postorder(root);

        cout<<endl;

        

        Level_Order( root);

        cout<<endl;

    }

    return 0;

}