已知后序与中序输出前序(先序):
后序:3, 4, 2, 6, 5, 1(左右根)
中序:3, 2, 4, 1, 6, 5(左根右)
已知一棵二叉树,输出前,中,后时我们采用递归的方式。同样也应该利用递归的思想:
对于后序来说,最后一个节点肯定为根。在中序中可以找到左子树的个数,那么就可以在后序中找到左子树的根;同理也可以找到右子树。
void pre(int root, int start, int end) {
if(start > end) return ;
int i = start;
while(i < end && in[i] != post[root]) i++;
printf("%d ", post[root]);
pre(root - - end + i, start, i - );
pre(root - , i + , end);
}
如果想要按照层次输出数,那么我们可以增加一个index变量,来存储结点。根节点为0,左子树为index*2+1, 右子树为index*2+2,那么我们按顺序输出不是-1的节点即可
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>lever(,-),post,in;
int n;
void pre(int root,int start,int end,int index)
{
if(start>end)
return;
int i=start;
while(i<end&&in[i]!=post[root])
i++;
lever[index]=post[root];
pre(root-end+i-,start,i-,index*+);
pre(root-,i+,end,index*+);
}
int main()
{
scanf("%d",&n);
post.resize(n+);
in.resize(n+);
for(int i=;i<=n;i++)
scanf("%d",&post[i]);
for(int i=;i<+n;i++)
scanf("%d",&in[i]);
pre(n,,n,);
int cnt=;
for(int i=;i<lever.size();i++)
{
if(lever[i]!=-)
{
cnt++;
if(cnt==n)
{
printf("%d\n",lever[i]);
break;
}
else
printf("%d ",lever[i]);
}
}
}