给出二叉树的 前序遍历 和 中序遍历,求 后序遍历。。
算法: 由前序遍历的第一个元素可确定左、右子树的根节点,参照中序遍历又可进一步确定子树的左、右子树元素。如此递归地参照两个遍历序列,最终构造出二叉树。
由前序和中序结果求后序遍历结果 树的遍历:
给你一棵树的先序遍历结果和中序遍历的结果,让你求以后序遍历输出用递归。每次把两个数组分成三个部分,父节点,左子树,右子树,把父节点放到数组里边,重复此步骤直到重建一棵新树, 这时,数组里元素刚好是后序遍历的顺序 关键点:
中序遍历的特点是先遍历左子树,接着根节点,然后遍历右子树。这样根节点就把左右子树隔开了。而前序遍历的特点是先访问根节点,从而实现前序遍历结果提供根节点信息,
中序遍历提供左右子树信息,从而实现二叉树的重建
例:
Sample Input
9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6
Sample Output
7 4 2 8 9 5 6 3 1
递归函数调试好长时间啊。。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
int i,j,k;
int n;
int a[1010],b[1010];
int c[1010];
struct node
{
int data;
node * pl;
node * pr;
}p[1010];
int pa;
node * dfs(int zhi,int l,int r)
{
int t=-1;
for(i=l;i<=r;i++)
if(b[i]==zhi){
t=i;
break;
}
if(t==-1)
{
return NULL;
}
int ans=pa;
pa++;
p[ans].data=zhi;
p[ans].pl=dfs(a[pa],l,t-1);
if(p[ans].pl!=NULL)
{
pa++;
}
p[ans].pr=dfs(a[pa],t+1,r);
if(p[ans].pr==NULL)
pa--;
return p+ans;
}
int flag;
void post(node * pp)
{
if(pp->pl!=NULL)
post(pp->pl);
if(pp->pr!=NULL)
post(pp->pr);
if(flag==0){
printf("%d",pp->data);
flag=1;
}
else
printf(" %d",pp->data);
}
int main()
{
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
pa=1;
node * pp=dfs(a[pa],1,n);
flag=0;
post(pp);
printf("\n");
}
}