二叉树已知先序遍历+中序遍历求后序遍历
本帖最后由 Knuth学徒 于 2011-3-26 19:02 编辑刚QQ上一个MM问我怎么写，其实就是个递归的问题，一般有两种解法，先根据先序遍历和中序遍历重新构造这棵树，然后对这棵树进行后序遍历，只是时间复杂度和空间复杂度都太高。
第二种方法就是 纯递归，在读取先序和中序的同时输出后序遍历，这样效率很高。
代码本来用C写的，但是例如 pre;这种太难看了……最近习惯用容器和模板库了.
/*
*************************
* Auther:Knuth学徒
* Lang : C++
* Time : 2011-2-11
*************************
*/
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;
void solve(string PreOrder, string InOrder)
{
if(PreOrder.size()== 0 || InOrder.size() == 0 )
return ;
char t = PreOrder; //根节点
int mid = InOrder.find(t); //在中序遍历中找出根节点
solve(PreOrder.substr(1 , mid) , InOrder.substr (0 , mid));//分治
solve(PreOrder.substr(mid+1,PreOrder.size() - 1- mid ) , InOrder.substr(mid+1 , InOrder.size()- 1- mid));
cout<<t;//输出后序遍历的根节点
}
int main()
{
string Pre;
string In;
cin>>Pre>>In;
solve(Pre,In);
cout<<endl;
return 0;
}
页:
[1]