http://acm.hdu.edu.cn/showproblem.php?pid=1710
基本数据结构，根据三种访问特点，进行遍历即可，关键是构造dfs的参数，即：将问题分解为子问题。
#include <iostream>
#include <algorithm>
using namespace std;
// preorder: 1 2 4 7 3 5 8 9 6
// inorder: 4 7 2 1 8 5 9 3 6
//postorder: 7 4 2 8 9 5 6 3 1
int preorder[1005];
int inorder[1005];
void dfs(int pre,int in,int size,bool flag)
{
int i;
if(size==1) //如果有左子树或右子树，就直接输出
{
printf("%d ",preorder[pre]); //不是根节点，所以是空格
return ;
}
if(size<=0) //没有左子树或右子树，则返回上层，遍历右子树或者根
return ;
for(i=0;preorder[pre]!=inorder[in+i];i++);//查找根节点在中序中的位置
dfs(pre+1,in,i,false); //左子树的遍历
dfs(pre+i+1,in+i+1,size-i-1,false); //右子树的遍历
if(flag) //输出根节点
printf("%d\n",preorder[pre]); //整个树的根节点
else
printf("%d ",preorder[pre]); //一般的根节点
}
int main()
{
int n,i;
while(cin>>n)
{
for(i=1;i<=n;i++)
scanf("%d",&preorder[i]);
for(i=1;i<=n;i++)
scanf("%d",&inorder[i]);
dfs(1,1,n,true);
}
return 0;
}如果知道后序遍历和中序遍历，输出先序遍历也是这样，关键是把左子树和右子树分割好，下面是代码：
#include <iostream>
#include <algorithm>
using namespace std;
//postorder: 7 4 2 8 9 5 6 3 1
//inorder: 4 7 2 1 8 5 9 3 6
//preorder: 1 2 4 7 3 5 8 9 6
int postorder[1005];
int inorder[1005];
void dfs(int post,int in,int size,bool flag) //flag用于标识是否输出' '
{
int i;
if(size==1) //有左子树或右子树，进行遍历即可
{
printf(" %d",postorder[post]);
return ;
}
if(size<=0) //不存在左子树或右子树，返回上层
return ;
if(flag) //先遍历根
printf("%d",postorder[post]);
else
printf(" %d",postorder[post]);
for(i=0;postorder[post]!=inorder[in+i];i++);//找出分割点
dfs(post-size+i,in,i,false); //遍历左子树
dfs(post-1,in+i+1,size-i-1,false); //遍历右子树
}
int main()
{
int n,i;
while(cin>>n)
{
for(i=1;i<=n;i++)
scanf("%d",&postorder[i]);
for(i=1;i<=n;i++)
scanf("%d",&inorder[i]);
dfs(n,1,n,true);
cout<<endl;
}
return 0;
} 如果是知道先序遍历和后序遍历，则不能输出唯一的中序遍历，因为找不到分割点。
posted on 2011-04-03 10:51
大大木马 阅读(507)
评论(0) 编辑 收藏 引用