代码一:

#include <bits/stdc++.h>
using namespace std;
char pos[10];//后序
char mid[10];//中序
int num[200];//字母对应的数字
char let[10];//数字对应的字母
struct node
{
    int key;
    node* left = NULL;
    node* right = NULL;
    node(int data) : key(data),left(nullptr),right(nullptr){
    }
 } ;
 using bnode = node*;
 bnode tree_insert(bnode tree_root,int nkey)//第一个是根节点,第二个是字母对应的数值 
 {
    if(tree_root == nullptr)
    {
        return new node(nkey);
    }
    if(nkey > tree_root->key) tree_root -> right = tree_insert(tree_root->right,nkey);
    else tree_root->left = tree_insert(tree_root->left,nkey);
    return tree_root;
 }
 void tree_preorder(bnode k)
 {
    if(k == NULL) return;
    cout << let[k->key];
    tree_preorder(k->left);
    tree_preorder(k->right); 
 }
int main()
{
    bnode root = NULL; 
    cin >> mid >> pos;
    for(int i = 0 ; mid[i] != '\0' ; i++) 
    {
        num[mid[i]] = i;
        let[i] = mid[i];
    }
    for(int i = strlen(pos) - 1;i>=0 ; i--)
    {
        root = tree_insert(root,num[pos[i]]);
    }
    tree_preorder(root);
    return 0;
}

代码二:

#include <bits/stdc++.h>
using namespace std;
void dfs(string inord,string posord)
{
    if(inord.size())
    {
        char c = posord[posord.size() - 1];
        cout << c;
        int fg = inord.find(c);
        dfs(inord.substr(0,fg),posord.substr(0,fg));
        dfs(inord.substr(fg+1),posord.substr(fg,inord.size() - 1 - fg));
    }
}
int main()
{
    string inord,posord;
    cin >> inord >> posord;
    dfs(inord,posord);
    return 0;
}

代码三:

#include <bits/stdc++.h>
using namespace std;
char pos[10];//后序
char mid[10];//中序
int num[200];//字母对应的数字
char let[10];//数字对应的字母
struct node
{
    int key;
    node* left = NULL;
    node* right = NULL;
    node* parent = NULL;
    /*node(int data) : key(data),left(nullptr),right(nullptr),parent(nullptr){
    }*/
 } ;
 using bnode = node*;
 bnode tree_insert(bnode tree_root,int nkey)//第一个是根节点,第二个是字母对应的数值 
 {
    bnode z = new node,y = NULL,x = tree_root;
    z->key = nkey;
    while(x != NULL)
    {
        y = x;
        if(nkey > x->key) x = x->right;
        else x = x->left;
    }
    z->parent = y;
    if(y == NULL) tree_root = z;
    else if(nkey > y->key) y->right = z;
    else y->left = z;
    return tree_root;
 }
 void tree_preorder(bnode k)
 {
    if(k == NULL) return;
    cout << let[k->key];
    tree_preorder(k->left);
    tree_preorder(k->right); 
 }
int main()
{
    bnode root = NULL;
    cin >> mid >> pos;
    for(int i = 0 ; mid[i] != '\0' ; i++) 
    {
        num[mid[i]] = i;
        let[i] = mid[i];
    }
    for(int i = strlen(pos) - 1;i>=0 ; i--)
    {
        root = tree_insert(root,num[pos[i]]);
    }
    tree_preorder(root);
    return 0;
}