问题 D: 求先序排列

                                                         时间限制: 1 Sec  内存限制: 125 MB
                                                                    提交: 14  解决: 6
                                                          [状态] [提交] [命题人:外部导入]

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入

每个测试文件只包含一组测试数据，每组输入包含两行，第一行输入一个字符串表示二叉树的中序排列，第二行输入一个字符串表示二叉树的后序排列。

输出

对于每组输入数据，输出二叉树的先序排列。

样例输入 

BADC
BDCA

样例输出 

ABCD

 其实不用调say函数，直接在被我标记的地方******************************* 解注释输出即可，

可以节省时间，这个题就是个典型的二叉树知道后序中序求树，的题所以一定要会

#include<bits/stdc++.h>
using namespace std;
struct tree{
	char data;
	struct tree* lchild;
	struct tree* rchild;
};
typedef struct tree* Tree; 
char mid[100],lay[100];
Tree build(char mid[100],char lay[100],int len);

void say(Tree root);//先序输出
int main()
{
	scanf("%s",mid);
	scanf("%s",lay);

	int len = strlen(mid);
	//cout<<len;
	Tree root = build(mid,lay,len);
	say(root);
}
void say(Tree root){
	if(root!=NULL){
		printf("%c",root->data); //先序输出
		say(root->lchild);
		say(root->rchild);
	}

}
Tree build(char mid[100],char lay[100],int len){//建树
	if(len==0){
		return NULL;
	}
	Tree root = (Tree)malloc(sizeof(struct tree));
	root->data = lay[len-1];
	//cout<<lay[len-1];//*******************************
	root->lchild = NULL;
	root->rchild = NULL;
	int i=0;
	for(;i<len;++i){
		if(mid[i]==lay[len-1])//找到根
			break;
	}
	root->lchild = build(mid,lay,i);//递归建左子树
	root->rchild = build(mid+i+1,lay+i,len-i-1);//递归建右子树
	return root;
}