注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

keky的博客

GAIN CONFIDENCE _=_!既然选择了远方,便只顾风雨兼程^_^

 
 
 

日志

 
 
关于我

Never Say Never!Do What I Want!

网易考拉推荐
GACHA精选

hoj 1452 Tree Recovery  

2007-07-16 16:41:26|  分类: cs_acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

note:

    write down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal   (left subtree, root, right subtree).  your job is to reconstruct the tree ;

   input: preorder traversal    inorder traversal   

  output:For each test case, recover the binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).

EXAMPLE:

  input:  DBACEGF ABCDEFG

  output: ACBFGED

       由于数据结构课刚上过关于树的遍历算法,看到该题就总想练练手,题意大概就是说:告诉我们先根和中根遍历,让我们输出后根遍历的结果。

         分析题意可知前根遍历中的每一个结点对应中根遍历序列的一个中心节点(祖先)。

         如例中的:先根中的 D  对应中根遍历序列ABCDEFG 中的祖先 D, 因此 D 就为根节点,两边分别为其左右子树,再对左右序列分别进行上述处理。。。( B 为对应序列 ABC 中的祖先B ), 由此递推可修复整棵树,,之后再用后根遍历可的结果。两边分别为其左右子树。。。

          由递归思想可以很容易实现,刚开始在递归里头用了(while)老错误,之后在YAOS帮助下改为( if ) 过了。。具体错因是什么还没弄明白。希望高手指点迷津!

 void BUILD(T tr, int f, int l ) // tr 为父节点指针  f, l 为相关面序列的首尾位置,i 为全局变量
{
  int k;    T  r;
    if( pr[i] != NULL && f <= l )
 {
    for( k = f; k <= l; k++ ) 

 {
           if( in[k] == pr[i])
            { 
         r = new TT;                    //建新节点。。。
                r -> c = pr[i];
                r -> rh = NULL;
                r -> lh = NULL;
              if( fl % 2 == 0)      
              tr ->  rh = r;
              else tr -> lh = r;
              i++;    break;   
            }
}
                fl = 1;     BUILD( r, f, k - 1 );  //左右序列分别进行递归
                fl = 2;    BUILD( r, k + 1, l);
} 

 

  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018