样例哈
4
/ \
1 6
\ / \
3 5 7
/
2
前中求后序
先给出样例 节点个数+中序+前序：
7
1 2 3 4 5 6 7 中序
4 1 3 2 6 5 7 前序
输出样例：
2 3 1 5 7 6 4 后序
在这里解释一下下哈：
前序是从根节点开始的，所以前序的第一个数4呢就是根节点，然后在中序里找到4，根据中序的性质（左-->节点-->右）知道，1 2 3为左子树，5 6 7 为右子树，接着从前序下手，1就是根节点之后的左节点，6是根节点之后的右节点，根据这个规律，用递归方法左右节点分别遍历~
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);i++) //虽然看见很多代码都是这么写，感觉会减少一些时间
const int maxN = 35;
int N,M;
struct node{int v;node *lc,*rc;}; //分别为左子树和右子树
int mid[maxN],pre[maxN];
node *build(int *p, int *m, int len){ //每次递归的时候p,m指针都会改变吗？嗯，最终返回根节点
if(len==0)
return NULL; //这里用Dev只允许NULL，nullptr的话会报错
node* prt = new node(); //这一步的作用？
prt->v = p[0];
int idx;
for(idx=0;idx<len;idx++)
if(m[idx]==p[0])
break;
int lsz = idx, rsz = len-idx-1;
prt->lc = build(p+1,m,lsz);
prt->rc = build(p+1+lsz,m+idx+1,rsz);
return prt;
}
//输出这里不是很明白
void print_path(node *prt){
if(prt==NULL)
return;
print_path(prt->lc); //每一个prt相当于一个实例，每个节点对应一个实例
print_path(prt->rc);
printf("%d ",prt->v); //因为是后序，所以后面输出
}
int main()
{
freopen("data.in.txt","r",stdin);
scanf("%d",&N);
rep(i,0,N) scanf("%d",&mid[i]);
rep(i,0,N) scanf("%d",&pre[i]);
node *prt = build(pre,mid,N);
print_path(prt);
return 0;
}
后中求前序
输入样例 节点个数+中序+后序：
7
1 2 3 4 5 6 7 中序
2 3 1 5 7 6 4 后序
输出样例：
4 1 3 2 6 5 7 嘿嘿，师兄这里错了//逃
按自己理解解释一波：
根据后序的相关性质，4是根节点，从中序中找到根节点，根节点右边为右节点，左边为左节点，再看回后序，6是右节点，1是左节点，然后分为左右子树分别递归啦~
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);i++)
const int maxN = 35;
int N,M;
struct node{int v;node *lc,*rc;}; //分别为左子树和右子树
//int mid[maxN],pre[maxN];
node *build(int *mid, int *post, int len){
if(len==0)
return 0;
int idx;
for(idx=0;idx<len;idx++)
if(mid[idx]==*(post+len-1))
break;
node *rt = new node;
rt->v = mid[idx];
rt->lc = build(mid,post,idx);
rt->rc = build(mid+idx+1,post + idx,len-(idx+1));
return rt;
}
//两个的输出方式为什么会有区别？
void print_tree(node *rt){
if(rt==NULL)
return;
printf("%d ",rt->v);
print_tree(rt->lc);
print_tree(rt->rc);
}
int main()
{
int post[maxN],mid[maxN];
freopen("data.in.txt","r",stdin);
scanf("%d",&N);
rep(i,0,N) scanf("%d",&post[i]);
rep(i,0,N) scanf("%d",&mid[i]);
node *rt = build(mid,post,N);
print_tree(rt);
return 0;
}
