已知一颗二叉树的后序遍历序列和中序遍历序列确定二叉树算法

Question

如题所述

Answer 1

1. 依据后序遍历序列的最后一个元素确定根结点T
2. 在中序序列中找到1中确定的根节点，其左边的序列L为根结点的左子树结点集合，其右边的序列R为根结点右子树结点集合。
3. 将L看做一棵树的序列集合重复1,得到左子树的根结点，将R看做一棵树的序列集合重复1得到右子树的根结点。这两个结点即为T的左结点和右结点。
4. 将L看做一棵树的序列集合重复2得到L子树的左子树和右子树，将R看做一棵树的序列集合重复2得到R子树的左子树和右子树
5. 对得到的子树序列重复3，4直到产生的子树序列都为空为止

Answer 2

#include <iostream>
#include <string>
using namespace std;
string pre;
void preorder(string a,string b)
{
if(b.length()==1) {pre+=b;}
else
{
int k=a.find(b.substr(b.length()-1,1));
pre+=a[k];
if (k>0)
preorder(a.substr(0,k),b.substr(0,k));
if (k<a.length()-1)
preorder(a.substr(k+1,a.length()-k-1),b.substr(k,b.length()-k-1));
}
}
void main()
{
string a,b;
cout<<"input string a:";
cin>>a;
cout<<"input string b:";
cin>>b;
preorder(a,b);
cout<<pre<<endl;
}