二叉树的遍历
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 341(80 users) Total Accepted: 144(73 users) Rating: Special Judge: No
Description
给出一棵二叉树的中序和前序遍历，输出它的后序遍历。
Input
本题有多组数据，输入处理到文件结束。
每组数据的第一行包括一个整数n，表示这棵二叉树一共有n个节点。
接下来的一行每行包括n个整数，表示这棵树的中序遍历。
接下来的一行每行包括n个整数，表示这棵树的前序遍历。
3<= n <= 100
Output
每组输出包括一行，表示这棵树的后序遍历。
Sample Input
7
4 2 5 1 6 3 7
1 2 4 5 3 6 7
Sample Output
4 5 2 6 7 3 1
两道题的题意都是一样的，哈理工的输出格式有点问题，可能只有给我们出C语言考试题和数据结构作业的老师才会犯这种每个数字后都有一个空格的错误。
然后“小时候”一直觉得这道题很难很难，也无法弄清楚为啥这么短的代码就能在不清楚树结构的情况下弄出来后序遍历。。。今天再看这题发现不亏是二叉树基础题
首先可以发现，根据输入的前序遍历，我们知道了排序越前的，越是树根，如排第一的是整棵树的树根，然后后面的第二第三就是其子树的树根。但是我们无法判断其左右子树分别有谁，这是只根据一个前序遍历不能确定的结构。
接着是中序遍历，可以发现，中序遍历的序列其实就是一棵拍扁了的树，我们拿前序遍历的第一个数【可以确定是树根】，放到中序遍历里面找，找到其位序，那么该数位序左边的就是整棵树根节点的左子树，而位序右边的就是右子树，至于是什么结构，我们目前还是不知道，但是可以确定的是，我们根据前序遍历，判断出来了被拍扁树【中序遍历】的大体结构。
中序：【@ @ @】 root 【@ @ @ @ @】
前序： root 【@ @ @】 【@ @ @ @ @】
并且，根据前序遍历的性质，我们知道在根节点之后的序列左半部分必定是左子树，右半部分必定是右子树【这点是显然的，可以举例出如果只有3个节点的子树，那么我们把左儿子看做该序列左半部分，右儿子看做该序列右半部分】，至于是左边哪几个和右边哪几个，可以根据在中序遍历中找到的位序得知左子树具体的节点个数和右子树具体节点个数。
那么我们将遍历序列都分成了两段【左子树和右子树】
接着，可以发现了吗，我们继续用同样的方法，找到子树的前序遍历中第一个数，再在中序遍历中找到该子树的根节点位置，又可以将其分成两棵子树，继续对子树的子树进行相同的操作，一层一层的找到其子树的根节点，最后就会形成树结构。
但是想了几分钟没反应过来。。。后序遍历是怎么就放在最后赋值进去就行了的。。。
然后仔细看halfpath这个递归函数，其这不就是多了找子树根节点这个步骤的 递归遍历树 吗？
所以说，其实前面这些找子树根节点的过程其实就是遍历树节点的过程！还是中序遍历！
那么，如果我把c数组的赋值位置放在两个halfpath中间，就是中序遍历，放在之前就是前序遍历，放在最后，就是答案需要的后序遍历！！！
最后看了十几分钟就明白了以前看一两天都没看懂的东西。。。
很简单的一个根据遍历序列复原树结构的问题。。。
当然如果你觉得这样还是比较绕的，不慌，你已经明白了答题思路，一下代码呈现数组模拟递归的简便写法，以及一年前队友写的 真·树结构 代码，队友通过相同的思路用结构体做树节点复原了这棵树，然后再对该树进行后序遍历并记录结果。。。堪称教学典范！
AC代码：
#include<stdio.h>
int num=0,a[1080],n,b[1080],c[1080];
int find(int tmp,int l,int r)
{
for(int i=l;i<r;i++)
if(a[i]==tmp)return i;
}
int halfpath(int bl,int br,int al,int ar)
{//拿出前序遍历的元素到中序遍历中查询位置
if(al==ar) return 0;
int root =find(b[bl],al,ar);//找出前序遍历中第bl个元素在中序遍历序列中的位置
int len=root-al;//中序遍历中第bl个元素的位序差
halfpath(bl+1,bl+1+len,al,root);//左子树
halfpath(bl+1+len,br,root+1,ar);//右子树
c[num++]=a[root];
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
num=0;
for(int i=0;i<n;i++)scanf("%d",&b[i]);//前序遍历
for(int i=0;i<n;i++)scanf("%d",&a[i]);//中序遍历
halfpath(0,n,0,n);
for(int i=0;i<n;i++)printf("%d%c",c[i],i==n-1?'
':' ');
}
}
队友代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<string>
using namespace std;
int pre[1005],mid[1005],behind[1005];
int num;
struct Node
{
int cnt;
Node *l,*r;
};
Node* root;
Node* newnode()///创建新节点并初始化
{
Node* tmp=new Node;
tmp->cnt=0;
tmp->l=tmp->r=NULL;
return tmp;
}
Node *creat(int * pre, int len1, int * mid, int len2)///重新建树
{
int i;
for(i=0; i<len2; i++)
{
if(pre[0]==mid[i]) break;
}
Node *pos=newnode();
pos->cnt=mid[i];
if(i>0) pos->l=creat(pre+1,i,mid,i);
if(i<len2-1) pos->r=creat(pre+i+1,len2-i-1,mid+i+1,len2-i-1);
return pos;
}
void behindquery(Node* root)///在建树之后进行后序遍历
{
if(root==NULL) return ;
behindquery(root->l);
behindquery(root->r);
behind[num++]=root->cnt;
}
void release(Node *pos)///删除树结构回收内存
{
if(pos==NULL) return ;
release(pos->l);
release(pos->r);
free(pos);
return ;
}
int main()
{
int n=0;
while(~scanf("%d",&n))
{
for(int i=0; i<n; i++)
scanf("%d",&pre[i]);
for(int i=0; i<n; i++)
scanf("%d",&mid[i]);
release(root);
root=creat(pre,n,mid,n);
num=0;
behindquery(root);
for(int i=0; i<n; i++)
printf("%d%c",behind[i],i==n-1? '
':' ');
}
release(root);
return 0;
}
大三是不应该有周末的，毕竟和高三一个级别，只是以前有人管有现在没人管罢了，该考研考研该准备面试准备面试。
然后发现周围小伙伴会的东西都是非常深入和底层的了，而自己还啥都不会，也面试不了。。所以应该更新点新东西了。
之后本月将更新一些关于python的、或者面试题、或者Linux的、或者STL底层的，或者epoll相关，，，反正好多想学的东西啊！！！！【其实本月的四级还要努力orz】
这是退役之后一个月复健的第一篇博客，就从简单的开始了。。。