#include

#include

#include

#include

using namespace std;

typedef char TElemType;

//二叉树的二叉链表存储表示

typedef struct BiTNode {

TElemType data; //结点数据域

struct BiTNode *lchild, *rchild; //左右孩子指针

} BiTNode, *BiTree;

//根据先序序列pre[pre_low..pre_low+len-1]和中序序列in[in_low..in_low+len-1]建树t

void BuildTree(BiTree& t, char pre[], int pre_low, char in[], int in_low, int len)

{

t = new BiTNode;

if (t)

{

if (len <= 0)

{

t = NULL;

return;

}

t->data = pre[pre_low];

int i = 0;

while (in[in_low + i] != t->data)i++;

BuildTree(t->lchild, pre, pre_low + 1, in, in_low, i);

BuildTree(t->rchild, pre, pre_low + i + 1, in, in_low + i + 1, len - (i + 1));

}

return;

}

// 后序遍历的递归算法

void PostOrderTraverse(BiTree t)

{

if (t) {

PostOrderTraverse(t->lchild);//遍历左孩子

    PostOrderTraverse(t->rchild);//遍历右孩子

    cout<<t->data ;

}

}

void DestroyBitree(BiTree& t)

{

if(t)

{

	DestroyBitree(t->lchild);

	DestroyBitree(t->rchild);

	free(t);

}

}

int main()

{

char pre[30], in[30];

BiTree t = NULL;

while(cin >> pre) {

cin >> in;

  BuildTree(t, pre, 0, in, 0, strlen(in));

  PostOrderTraverse(t);

  DestroyBitree(t);

  cout << endl;

}

}

#include<bits/stdc++.h>
using namespace std;
string a,b;
void dg(int x1,int y1,int x2,int y2)
{
if(x1>y1) return;
int root=b.find(a[x1]);		
dg(x1+1,x1+root-x2,x2,root-1);
dg(x1+root-x2+1,y1,root+1,y2);
cout<<a[x1];
}
int main()
{
cin>>a>>b;
dg(0,a.length()-1,0,b.length()-1);
cout<<endl;
return 0;
}

【精选】根据二叉树前序和中序求后序_根据前序序列和中序序列计算后序序列 题目描述: 给定二叉树的前序遍历序列和中序-CSDN博客