HDU 1710 二叉树遍历,输入前、中序求后序

1、HDU  1710  Binary Tree Traversals

2、链接:http://acm.hust.edu.cn/vjudge/problem/33792

3、总结:记录下根结点,再拆分左右子树,一直搜下去。感觉像dfs。

题意:二叉树,输入前、中序求后序。

(1)建立出一颗二叉树,更直观。但那些指针用法并不是很懂。

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std; typedef struct tree
{
tree *l,*r;
int num;
};
tree *root; tree *build(int *a,int *b,int n)
{
tree *s;
for(int i=;i<n;i++)
{
if(a[]==b[i]){
s=(tree *)malloc(sizeof(tree)); //不要漏了这个 s->num=b[i];
s->l=build(a+,b,i);
s->r=build(a+i+,b+i+,n-i-);
return s;
}
} return NULL;
} void postorder(tree *ro)
{
if(ro==NULL)return ;
postorder(ro->l);
postorder(ro->r);
if(ro==root){
printf("%d\n",ro->num);
}
else {
printf("%d ",ro->num);
}
} int main()
{
int n;
int a[],b[];
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<n;i++)
scanf("%d",&a[i]);
for(int i=;i<n;i++)
scanf("%d",&b[i]); root=build(a,b,n);
postorder(root);
} return ;
}

(2)直接在遍历时输出。

#include<iostream>
#include<cstdio>
using namespace std; void preorder(int *a,int *b,int n,int flag)
{
for(int i=;i<n;i++)
{
if(a[]==b[i]){
preorder(a+,b,i,);
preorder(a+i+,b+i+,n-i-,);
if(flag){
printf("%d\n",a[]);
}
else {
printf("%d ",a[]);
}
}
}
return ;
} int main()
{
int n,a[],b[];
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<n;i++)
scanf("%d",&a[i]);
for(int i=;i<n;i++)
scanf("%d",&b[i]); preorder(a,b,n,);
} return ;
}
上一篇:HDU 1710 Binary Tree Traversals(树的建立,前序中序后序)


下一篇:Win32下 Qt与Lua交互使用:配置Qt下Lua运行环境