由中序遍历和后序遍历确定先序遍历的C语言算法

题目描述：

已知一棵二叉树的中序遍历序列和后序遍历序列，求其先序遍历序列。

算法思路：

从后序遍历序列的最后一个结点开始，依次向前扫描，找到第一个出现在中序遍历序列中的结点，它就是根结点。然后，根据中序遍历序列，将该根结点分成左右两部分，分别构造左子树和右子树。接下来，分别对左子树和右子树递归执行上述过程，直到所有结点都被构造出来。

根据先序遍历的定义，先访问根节点，再访问左子树，最后访问右子树。因此，我们可以按照递归构造的顺序，将每个结点的值添加到先序遍历序列中。

C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 100

// 树结点结构体
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 构造树
TreeNode* buildTree(char inOrder[], char postOrder[], int inStart, int inEnd, int postStart, int postEnd) {
    if (inStart > inEnd || postStart > postEnd) {
        return NULL;
    }

    int rootIndex = inStart;
    while (rootIndex <= inEnd && inOrder[rootIndex] != postOrder[postEnd]) {
        rootIndex++;
    }

    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = inOrder[rootIndex];
    root->left = buildTree(inOrder, postOrder, inStart, rootIndex - 1, postStart, postStart + rootIndex - inStart - 1);
    root->right = buildTree(inOrder, postOrder, rootIndex + 1, inEnd, postStart + rootIndex - inStart, postEnd - 1);

    return root;
}

// 前序遍历
void preOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    printf("%c ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

int main() {
    char inOrder[MAX_N], postOrder[MAX_N];
    printf("请输入中序遍历序列：\n");
    scanf("%s", inOrder);
    printf("请输入后序遍历序列：\n");
    scanf("%s", postOrder);

    int len = strlen(inOrder);
    TreeNode *root = buildTree(inOrder, postOrder, 0, len - 1, 0, len - 1);

    printf("先序遍历序列为：\n");
    preOrder(root);
    printf("\n");

    return 0;
}

参考资料：

[1] 程序员小灰. 从中序遍历和后序遍历还原二叉树[CSDN博客]. https://blog.csdn.net/u011026968/article/details/81102733.

[2] 陈启峰. 前中后序遍历的C语言实现[博客园]. https://www.cnblogs.com/qifengshi/p/8663798.html.