二叉树之已知前序和中序遍历求后序遍历（POJ HDU ）

本文主要是介绍二叉树之已知前序和中序遍历求后序遍历（POJ HDU ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

POJ2255【题目链接】click here~~

代码：

/*
* Problem: POJ No.2255 && UVA 536
* Running time: 0MS
* Complier: G++
* Author: javaherongwei
* Create Time: 2015-08-18 10:35:06 星期五
* binary search tree
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>using namespace std;
typedef long long LL;const int N= 1e2+10;
char res[N],pre[N],in[N],last[N];
void findlast(int n,char* pre,char* in,char* res)///递归构造,输入先序遍历，中序遍历，求后序遍历
{if(n<=0) return ;int p=strchr(in,pre[0])-in;///找到根节点在中序遍历的位置findlast(p,pre+1,in,res);///递归构造左子树的后序遍历findlast(n-p-1,pre+p+1,in+p+1,res+p);///递归构造右子树的后序遍历res[n-1]=pre[0];///添加根节点到最后面
}
int main()
{while(scanf("%s%s",pre,in)==2){int n=strlen(in);findlast(n,pre,in,res);res[n]='\0';printf("%s\n",res);} return 0;
}另一种写法：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>using namespace std;
typedef long long LL;
const int N=100+10;char pre[N],in[N],last[N];void Find_Last(int p1,int p2,int q1,int q2,int root)
{if(p1>p2) return;for(root=q1; in[root]!=pre[p1]; ++root);Find_Last(p1+1,p1+root-q1,q1,root-1,0);Find_Last(p1+root+1-q1,p2,root+1,q2,0);printf("%c",in[root]);
}
int main()
{while(scanf("%s%s",pre,in)==2){int len=strlen(pre)-1;Find_Last(0,len,0,len,0);puts("");} return 0;
}/*
*输入先序遍历，中序遍历，求后序遍历
*样例：
DBACEGF ABCDEFG
ACBFGED
BCAD CBAD
CDAB
*/

HDU 1710【题目链接】： click here~~

写法仿照上题。

/*
* Problem: HDU No.1710
* Running time: 62MS
* Complier: G++
* Author: javaherongwei
* Create Time: 2015-09-16 14:37:06 星期三
* binary search tree
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>using namespace std;
typedef long long LL;
const int N=1e4+10;int pre[N],in[N],last[N];void Find_Last(int p1,int p2,int q1,int q2,int root,int ck) // 标记一个变量
{if(p1>p2) return;for(root=q1; in[root]!=pre[p1]; ++root);Find_Last(p1+1,p1+root-q1,q1,root-1,0,0);Find_Last(p1+root+1-q1,p2,root+1,q2,0,0);if(ck==1) printf("%d",in[root]);else printf("%d ",in[root]);
}
int main(){int t;while(~scanf("%d",&t)){for(int i=0; i<t; ++i) scanf("%d",&pre[i]);for(int i=0; i<t; ++i) scanf("%d",&in[i]);Find_Last(0,t-1,0,t-1,0,1);puts("");}return 0;
}

这篇关于二叉树之已知前序和中序遍历求后序遍历（POJ HDU ）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---