C语言解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char midord[100];
char preord[100];
int n;

void proc(int low, int high, int index){
if(low > high || index < 0)return;
char root = preord[index];
int mid;
for(mid = low;mid <= high; mid ++){
    if(midord[mid]==root)break;
}
printf("%c",root);
proc(low,mid-1,index - high + mid - 1);
proc(mid+1,high,index-1);
}

int main()
{
    while(scanf("%s %s",midord,preord) != EOF){
        n = strlen(midord);
        proc(0,n-1,n-1);
    }
    return 0;
}

C++解答

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
string s1,s2;
int work(string,string);
int main()
{
	//freopen("test8.in","r",stdin);
	//freopen("test8.out","w",stdout);
	cin>>s1>>s2;
	work(s1,s2);
	return 0;
}
int work(string s1,string s2)
{
	int len=s2.size();
	cout<<s2[len-1];//直接输出后根遍历的最后一个	
	if(len==1) return 0;//如果长度为1，直接退出 
	int k=s1.find(s2[len-1],0);	//求根在中根遍历中的位置 
	string s3,s4;
	if(k>0)//如果位置大于0，表明有左子树 
	{
		s3=s1.substr(0,k);//左子树的中根遍历 
		s4=s2.substr(0,k);//左子树的后根遍历 
		work(s3,s4);		
	}
	if(k<len-1)//如果位置小于最后一个字符的下标表明有右子树 
	{
		s3=s1.substr(k+1,len-k-1);//右子树的中根遍历 
		s4=s2.substr(k,len-k-1);//右子树的后根遍历，注意截取的位置		
		work(s3,s4);
	}
	return 0;
}