根据先序序列和中序序列求后序序列从数组变成字符串就不行了
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int k;//统计个数
int n;
char pre[N];//前序序列
char in[N];//中序序列
char post[N];//后序序列
struct node
{
char value;
node *L;
node *R;
node(char value=0,node *L=NULL,node *R=NULL):value(value),L(L),R(R){}//初始化
};
void buildtree(int L,int R,int &t,node * &root)//建树,左子树,右子树,前序序列值的推进,根节点
{
int flag=-1;
for(register int i=L;i<R;i++)
{
if(in[i]==pre[t])//找到了线序序列的位置
{
flag=i;//对应中序序列的位置
break;
}
}
if(flag==-1)//没有就返回
return ;
root=new node(in[flag]);//新建子根节点
t++;//推进
if(flag>L)//如果是在左子树上,那中序序列遍历的根节点左边在左子树上
{
buildtree(L,flag-1,t,root->L);
}
if(flag<R)//如果是在右子树上,那中序序列遍历的根据二点右边在柚子树上,右子树需从i+1进行计数
{
buildtree(flag+1,R,t,root->R);
}
}
void preorder(node *root)//前序遍历
{
if(root!=NULL)
{
post[k++]=root->value;
preorder(root->L);
preorder(root->R);
}
}
void inorder(node *root)//中序遍历
{
if(root!=NULL)
{
inorder(root->L);
post[k++]=root->value;
inorder(root->R);
}
}
void postorder(node *root)//后序遍历
{
if(root!=NULL)
{
postorder(root->L);
postorder(root->R);
//post[k++]=root->value;
printf("%c",root->value);
}
}
void remove_tree(node *root)//删除节点释放空间
{
if(root==NULL)
return ;
remove_tree(root->L);
remove_tree(root->R);
delete root;
}
int main()
{
std::ios::sync_with_stdio(false);
scanf("%s",pre);
scanf("%s",in);
n=strlen(in);
int t=0;//同步前序序列,确定根节点
node *root;
buildtree(0,n,t,root);//建树
postorder(root);//后序遍历
remove_tree(root);//释放空间
return 0;
}