하나.분석

두 갈래 나무의 재구성은 두 갈래 나무의 선차적 역주행과 중차적 편리를 주고 출력 후차적 역주행 결과를 명확하게 한다. 우선 문제를 명확히 해야 한다. 우리는 두 갈래 나무를 구축해야 한다. 그러나 두 갈래 나무의 중요한 특징은 두 갈래 나무가 역주행으로 정의된 것이기 때문에 우리는 종종 역주행으로 해결한다. 그러면 문제는 한 단락의 선차적 역주행과 중차적 역주행 후이다.두 갈래 나무의 세 가지 중요한 원소, 즉 뿌리 노드와 왼쪽 나무와 오른쪽 나무를 확정한다. 순서가 편리한 특징에 따라 우리는 첫 번째 원소가 뿌리 노드라는 것을 알고 있다. 그러나 우리는 왼쪽 나무와 오른쪽 나무를 확정해야 한다. 중간 순서가 편리한 특징에 따라 우리는 중간 순서가 중간 뿌리 노드 이전의 원소는 왼쪽 나무에 속하고 그 후의 원소는 오른쪽 나무에 속한다는 것을 안다. 그러면 우리는 두 갈래 나무의 세 원소를 확정할 수 있다.이후에 우리는 이 문제를 차례로 해결할 수 있다.

//
//  main.cpp
//   
//
//  Created by   on 16/2/4.
//  Copyright © 2016   . All rights reserved.
//

#include <iostream>
#include <cstring>
using namespace std;
char str1[500],str2[500],len;
int find(char *s,char key)
{
    int p=0;
    while(s[p]!=key) p++;
    return p;
}
void buid(int s1,int e1,int s2,int e2)
{
    if(s1==e1) {cout<<str1[s1]<<" ";return;}
    else if(s1>e2) return;
    else
    {
        int p=find(str2,str1[s1]);
        buid(s1+1,p-s2+s1,s2,p-1);
        buid(p-s2+s1+1,e1,p+1,e2);
        cout<<str2[p]<<" ";
    }
}
int main(int argc, const char * argv[]) {
    freopen("/Users/zhangjiatao/Desktop/input.txt","r",stdin);
    cin>>str1;
    cin>>str2;
    len=strlen(str1);
    buid(0,len-1,0,len-1);
    return 0;
}