当前位置:网站首页>由中序遍历和前序遍历得到后序遍历(树的遍历)

由中序遍历和前序遍历得到后序遍历(树的遍历)

2022-08-02 03:22:00 寒江飞冰

给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式:
输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式:
在一行中输出该树的后序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
输入样例:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例:
3 2 7 6 5 4 1

#include<iostream>
using namespace std;
int a[30];
int b[30];
typedef struct Node{
    
	int data;
	Node *lchild;
	Node *rchild;
	
}Node,*Tree;
Tree build(int *a,int *b,int n)
{
    
	if(n<=0)
	{
    
		return NULL;
	}
	int *p=a;
	while(p)
	{
    
		if(*p==*b) break;
		p++;
	}
	Tree T;
	T=new Node;
	T->data=*p;
	int m=p-a;
	T->lchild=build(a,b,m);
	T->rchild=build(p+1,b+m,n-m-1);
	return T;
}
void Print(Tree T)
{
    
	if(T)
	{
    
		Print(T->lchild);
		Print(T->rchild);
		cout<<' '<<T->data;
	}
}

int main()
{
    
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) cin>>b[i];
	Tree T;
	T=build(a,b,n);
    Print(T); 
	
	
}
原网站

版权声明
本文为[寒江飞冰]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_43874484/article/details/104854931