HDU1710---树(知前序遍历与中序遍历 求后序遍历)

知前序遍历与中序遍历 求后序遍历

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
bool fist;
const int maxn=;
struct tree_node
{
int value;
tree_node* leftchild;
tree_node* rightchild;
tree_node()
{
leftchild=NULL;
rightchild=NULL;
}
};
/**
根据中序遍历,前序遍历建树
递归 忽略细节 深入至所有结点建立
*/
tree_node* build_tree(int pre[],int in[],int length)
{
if(length==)return NULL;///终止条件
tree_node* temp = new tree_node;
int pos;
for(pos=;pos<length;pos++)///找到根节点->然后根据中序遍历把左子树和右子树分开
{
if(in[pos]==pre[])break;
}
temp->value=pre[];
temp->leftchild=build_tree(pre+,in,pos);
temp->rightchild=build_tree(pre+pos+,in+pos+,length-pos-);
return temp;
} void postOrder(tree_node* root)
{
if(root!=NULL)
{
postOrder(root->leftchild);
postOrder(root->rightchild);
if(!fist)///根节点输出
{
cout<<root->value;
fist=true;
}
else
cout<<" "<<root->value;
}
}
int main()
{
int n;
int pre[maxn],in[maxn];
while(scanf("%d",&n)==)
{
fist=false;
///input
for(int i=;i<n;i++)scanf("%d",&pre[i]);
for(int i=;i<n;i++)scanf("%d",&in[i]);
///solve
tree_node* tree=build_tree(pre,in,n);
postOrder(tree);
cout<<endl;
}
return ;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn = + ;
int pre[maxn], in[maxn], n, pos[maxn]; void creat(int l, int r, int L, int R) { if (L == R) {
printf("%d ", in[L]);
return;
} int id = pos[pre[l]];///in中父节点位置
if(id > L) creat(l + , l + id - L, L, id - );//边界, 左
if(id < R) creat(l + + id - L, r, id + , R);//右 printf("%d%s", in[id], l == ? "\n" : " ");
} int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif while (~scanf("%d", &n)) {
for (int i = ; i <= n; ++i) scanf("%d", &pre[i]);
for (int i = ; i <= n; ++i) {
scanf("%d", &in[i]);
pos[in[i]] = i;
}
creat(, n, , n);
} return ;
}
上一篇:DS实验题 order


下一篇:linux下用rpm包安装默认配置