#include <bits/stdc++.h>
using namespace std;

// 定义全局变量
char PreOrder[1001]; // 前序遍历序列
char InOrder[1001];  // 中序遍历序列
int n; // 序列的长度

struct node {
    char data;
    int childnodes[10]; // 子节点列表，假设每个节点的子节点数量不超过10个
    int childCount; // 子节点数量
} GenericTree[1001];

int aviliable = 0; // 用于记录当前可用的节点索引
int root = -1; // 用于记录根节点的索引

// 通过前序和中序遍历构建树
int CreateGenericTree(int& preIndex, int left, int right) {
    if (preIndex >= n || left > right) return -1;

    // 获取当前根节点的值
    char rootVal = PreOrder[preIndex++];
    int rootIndex = aviliable++;
    GenericTree[rootIndex].data = rootVal;
    GenericTree[rootIndex].childCount = 0; // 初始化子节点数量

    // 如果当前节点是叶子节点，直接返回
    if (left == right) return rootIndex;

    // 在中序遍历中找到根节点的位置
    int inIndex = left;
    for (int i = left; i <= right; i++) {
        if (InOrder[i] == rootVal) {
            inIndex = i;
            break;
        }
    }

    // 递归构建子树
    for (int i = left; i < inIndex; i++) {
        int childIndex = CreateGenericTree(preIndex, left, inIndex - 1);
        if (childIndex != -1) {
            GenericTree[rootIndex].childnodes[GenericTree[rootIndex].childCount++] = childIndex;
        }
    }
    for (int i = inIndex + 1; i <= right; i++) {
        int childIndex = CreateGenericTree(preIndex, inIndex + 1, right);
        if (childIndex != -1) {
            GenericTree[rootIndex].childnodes[GenericTree[rootIndex].childCount++] = childIndex;
        }
    }

    return rootIndex;
}

// 前序遍历输出
void PreOrderOut(int rootIndex) {
    if (rootIndex == -1) return;
    cout << GenericTree[rootIndex].data << " ";
    for (int i = 0; i < GenericTree[rootIndex].childCount; i++) {
        PreOrderOut(GenericTree[rootIndex].childnodes[i]);
    }
}

// 中序遍历输出
void InOrderOut(int rootIndex) {
    if (rootIndex == -1) return;
    if (GenericTree[rootIndex].childCount > 0) {
        InOrderOut(GenericTree[rootIndex].childnodes[0]);
    }
    cout << GenericTree[rootIndex].data << " ";
    for (int i = 1; i < GenericTree[rootIndex].childCount; i++) {
        InOrderOut(GenericTree[rootIndex].childnodes[i]);
    }
}

// 后序遍历输出
void PostOrderOut(int rootIndex) {
    if (rootIndex == -1) return;
    for (int i = 0; i < GenericTree[rootIndex].childCount; i++) {
        PostOrderOut(GenericTree[rootIndex].childnodes[i]);
    }
    cout << GenericTree[rootIndex].data << " ";
}

// 层次遍历输出
void LevelOrderOut(int rootIndex) {
    if (rootIndex == -1) return;
    queue<int> q;
    q.push(rootIndex);
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << GenericTree[current].data << " ";
        for (int i = 0; i < GenericTree[current].childCount; i++) {
            q.push(GenericTree[current].childnodes[i]);
        }
    }
}

// 输入前序和中序遍历序列
void Input() {
    cin >> PreOrder;
    cin >> InOrder;
    n = strlen(PreOrder); // 获取序列的长度
}

int main() {
    Input(); // 输入前序和中序遍历序列

    int PreIndex = 0; // 初始化前序遍历的索引
    root = CreateGenericTree(PreIndex, 0, n - 1); // n - 1 是 InOrder 数组的长度减一

    cout << "PreOrder: ";
    PreOrderOut(root);
    cout << "\n";

    cout << "InOrder: ";
    InOrderOut(root);
    cout << "\n";

    cout << "PostOrder: ";
    PostOrderOut(root);
    cout << "\n";

    cout << "LevelOrder: ";
    LevelOrderOut(root);
    cout << "\n";

    return 0;
}

自行看注释

顺带提一嘴，childnodes也可以是一个向量，但是我懒得弄了