7-1 根据后序和中序遍历输出先序遍历（25 分）_7-1 根据后序和中序遍历输出先序遍历分数 25

作者：IT小白 | 2024-06-02 16:26:24

踩

7-1 根据后序和中序遍历输出先序遍历分数 25

7-1 根据后序和中序遍历输出先序遍历（25 分）

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式:

第一行给出正整数 $N$ ( $\leq 30$ )，是树中结点的个数。随后两行，每行给出 $N$ 个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:


7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

Preorder: 4 1 3 2 6 5 7


#include<bits/stdc++.h>
using namespace std;
int hou[1000];
int zhong[1000];
struct Tree{
	int data;
	struct Tree *left,*right;
};
struct Tree *creat(int h1,int h2,int z1,int z2){
	struct Tree *T;
	int i;
	int num;
	if(h1>h2){
		T=NULL;
	}else{
		T=(struct Tree *)malloc(sizeof(struct Tree));
		T->data=hou[h2];
		for(i=z1;i<=z2;i++){
			if(zhong[i]==hou[h2])
			   break;
		}
		num=i-z1;
		T->left=creat(h1,h1+num-1,z1,i);
		T->right=creat(h1+num,h2-1,i+1,z2);
		//起初这段代码 存在错误，错误在于 T->right=creat(h1+num,h2-1,z1+num,z2);
		//中序的起始位置不正确，i的位置为根的位置，中序右子树的起始位置应该为根的右面第一个数据 
	}
	return T;
}
void xianxu(struct Tree *T){
	if(T){
		printf(" %d",T->data);
		xianxu(T->left);
		xianxu(T->right);
	}
}
int main(){
	struct Tree *T;
	int n;
	int i;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>hou[i];
	}
	for(i=0;i<n;i++){
		cin>>zhong[i];
	}
	T=creat(0,n-1,0,n-1);
	cout<<"Preorder:";
	xianxu(T);
	cout<<endl;
}