Chinaunix首页 | 论坛 | 博客
  • 博客访问: 103427
  • 博文数量: 34
  • 博客积分: 30
  • 博客等级: 民兵
  • 技术积分: 217
  • 用 户 组: 普通用户
  • 注册时间: 2013-01-10 23:36
文章分类
文章存档

2013年(34)

我的朋友

分类: C/C++

2013-04-01 23:28:47

二叉树的题目基本上都是要用递归的,这题也一样。

而递归的核心是找到结构相同的子问题。

二叉树如下所示:

                  a

              ↙   ↘

            b         c

         ↙↘        ↘

       d      e          g

前序: abdecg

中序: dbeacg

由前序的第一个a,可以把树分为两个部分,左子树和右子树。

在中序序列中找到a,左边部分则是左子树的中序,右边则是右子树的中序,

同样前序a的后面紧跟着左子树的前序和右子树的前序。

则问题可分解为两个结构相同的小问题。

1,先求左子树的后序;

2,求右子树的后序;

3,再将左子树和右子树的后序串起来,最后加上本身节点即可。


代码:

[cpp]
  1. #include  
  2. #include  
  3. using namespace std; 
  4.  
  5. string FindPostOrder( string pre_order, string in_order ); 
  6.  
  7. int _tmain(int argc, _TCHAR* argv[]) 
  8.     string pre_order, in_order, post_order; 
  9.     cin >> pre_order >> in_order; 
  10.     cout << FindPostOrder( pre_order, in_order ); 
  11.     return 0; 
  12.  
  13. string FindPostOrder( string pre_order, string in_order ) 
  14.     if( pre_order.length() != in_order.length() )   //前序中序元素个数不相等出错 
  15.     { 
  16.         cout << "Failed" << endl; 
  17.         exit(1); 
  18.     } 
  19.  
  20.     if( pre_order.length() == 1 )                //递归终止 
  21.     { 
  22.         if( pre_order != in_order )               //一个元素时前序中序不相等 
  23.         { 
  24.             cout << "Failed" <
  25.             exit(1); 
  26.         } 
  27.         return pre_order; 
  28.     } 
  29.  
  30.     if( pre_order.length() == 0)                  //前序为空时,后序也为空 
  31.         return string(); 
  32.  
  33.     char node = pre_order[0];                   //取第一个元素 
  34.     int index = in_order.find( node );          //找到其在中序中的位置 
  35.  
  36.     if( index == string::npos )                 //没有找到,则出错 
  37.     { 
  38.         cout << "Failed" <
  39.         exit(1); 
  40.     } 
  41.     int len = pre_order.length(); 
  42.  
  43.     //左子树的后序 
  44.     string left_part = FindPostOrder( pre_order.substr(1,index), in_order.substr(0,index) );  
  45.     //右子树的后序 
  46.     string right_part = FindPostOrder( pre_order.substr(1+index, len-index-1), in_order.substr(1+index,len-index-1) ); 
  47.  
  48.     return left_part+right_part+node; //串联起来 
  49.  

 

阅读(1415) | 评论(0) | 转发(0) |
0

上一篇:链表归并

下一篇:vs2010调试小技巧

给主人留下些什么吧!~~