C语言非递归前序遍历二叉树：已知中序和后序遍历

思路：

后序遍历的最后一个节点一定是根节点，根据这个特点可以得到根节点的值
在中序遍历中找到根节点的位置，这样就可以分别得到左子树和右子树的中序遍历序列
在后序遍历中，左子树的节点都在根节点之前，右子树的节点都在根节点之后，因此也可以得到左子树和右子树的后序遍历序列
分别对左子树和右子树进行递归处理，直到叶子节点为止

具体实现：

创建一个栈用于存储节点
将根节点入栈
从后序遍历中取出下一个节点，创建一个新节点并将其入栈
如果新节点的值等于当前栈顶节点的左子节点的值，则将新节点作为当前节点的左子节点，并将新节点入栈
如果新节点的值等于当前栈顶节点的右子节点的值，则将新节点作为当前节点的右子节点，并将新节点入栈
重复步骤3~5直到后序遍历序列中的所有节点都被处理完毕
最后栈顶节点就是整棵树的根节点，从根节点开始进行前序遍历即可

代码实现如下：

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

#define MAX_SIZE 100

typedef struct TreeNode {
    char val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

typedef struct Stack {
    TreeNode* data[MAX_SIZE];
    int top;
} Stack;

void stack_init(Stack* s) {
    s->top = -1;
}

int stack_is_empty(Stack* s) {
    return s->top == -1;
}

int stack_is_full(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

void stack_push(Stack* s, TreeNode* node) {
    if (stack_is_full(s)) {
        printf("Stack is full\n");
        return;
    }
    s->data[++s->top] = node;
}

TreeNode* stack_pop(Stack* s) {
    if (stack_is_empty(s)) {
        printf("Stack is empty\n");
        return NULL;
    }
    return s->data[s->top--];
}

TreeNode* new_node(char val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

TreeNode* build_tree(char* inorder, char* postorder, int n) {
    if (n <= 0) {
        return NULL;
    }
    // 根节点的值为后序遍历的最后一个节点
    char root_val = postorder[n-1];
    TreeNode* root = new_node(root_val);
    int root_index = 0;
    // 在中序遍历中找到根节点的位置，以此分别得到左子树和右子树的中序遍历序列
    for (int i = 0; i < n; i++) {
        if (inorder[i] == root_val) {
            root_index = i;
            break;
        }
    }
    // 递归处理左子树
    root->left = build_tree(inorder, postorder, root_index);
    // 递归处理右子树
    root->right = build_tree(inorder + root_index + 1, postorder + root_index, n - root_index - 1);
    return root;
}

void preorder_traversal(TreeNode* root) {
    Stack s;
    stack_init(&s);
    TreeNode* cur = root;
    while (cur || !stack_is_empty(&s)) {
        while (cur) {
            printf("%c ", cur->val);
            stack_push(&s, cur);
            cur = cur->left;
        }
        cur = stack_pop(&s);
        cur = cur->right;
    }
}

int main() {
    char inorder[] = "BDCEAFHG";
    char postorder[] = "DECBHGFA";
    int n = sizeof(inorder) / sizeof(inorder[0]);
    TreeNode* root = build_tree(inorder, postorder, n);
    printf("Preorder traversal: ");
    preorder_traversal(root);
    printf("\n");
    return 0;
}

输出结果为：Preorder traversal: ABDECFHG