specialping

hdu 1710

#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;
}


如果知道后序遍历和中序遍历,输出先序遍历也是这样,关键是把左子树和右子树分割好

posted on 2011-12-14 12:20 曦冉 阅读(387) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理