【转】二叉树的三种遍历的相互转化——已知先序中序求后序

时间：2015-10-09 21:29:11 阅读：248 评论：0 收藏：0 [点我收藏+]

http://blog.csdn.net/huangxy10/article/details/8010698

题目：

已知二叉树的先序和中序遍历字符串,编程实现输出后序遍历字符串,

如果没有成功输出Failed,最后分析时间和空间复杂度。

题目来源：

经典题目，也是网易游戏2011年游戏开发工程师的一道笔试题。

分析：

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

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

二叉树如下所示：

↙ ↘

b c

↙↘ ↘

d e g

前序： abdecg

中序： dbeacg

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

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

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

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

1，先求左子树的后序；

2，求右子树的后序；

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

代码：

[cpp] view plain copy print ?

#include <string>
#include <iostream>
using namespace std;
string FindPostOrder( string pre_order, string in_order );
int _tmain(int argc, _TCHAR* argv[])
{
string pre_order, in_order, post_order;
cin >> pre_order >> in_order;
cout << FindPostOrder( pre_order, in_order );
return 0;
}
string FindPostOrder( string pre_order, string in_order )
{
if( pre_order.length() != in_order.length() ) //前序中序元素个数不相等出错
{
cout << "Failed" << endl;
exit(1);
}
if( pre_order.length() == 1 ) //递归终止
{
if( pre_order != in_order ) //一个元素时前序中序不相等
{
cout << "Failed" <<endl;
exit(1);
}
return pre_order;
}
if( pre_order.length() == 0) //前序为空时，后序也为空
return string();
char node = pre_order[0]; //取第一个元素
int index = in_order.find( node ); //找到其在中序中的位置
if( index == string::npos ) //没有找到，则出错
{
cout << "Failed" <<endl;
exit(1);
}
int len = pre_order.length();
//左子树的后序
string left_part = FindPostOrder( pre_order.substr(1,index), in_order.substr(0,index) );
//右子树的后序
string right_part = FindPostOrder( pre_order.substr(1+index, len-index-1), in_order.substr(1+index,len-index-1) );
return left_part+right_part+node; //串联起来
}

原文：http://www.cnblogs.com/royalisme/p/4865110.html

踩

(0)

评论一句话评论（0）

分享档案

更多>