使用C语言非递归实现二叉树前序遍历 - 从中序和后序遍历构建二叉树

思路：

1. 后序遍历的最后一个元素为根节点，根据根节点在中序遍历中的位置，可以将中序遍历的序列分为左子树和右子树两个部分；
2. 根据左右子树的长度，可以将后序遍历的序列分为左子树和右子树两个部分；
3. 递归处理左右子树，直到序列长度为1，输出该节点；
4. 按照根节点、左子树、右子树的顺序输出节点，即为前序遍历。

具体实现：

1. 定义一个栈结构，用于存储节点；
2. 将后序遍历的最后一个节点入栈；
3. 从后序遍历的倒数第二个节点开始倒序遍历，对于每个节点，判断其是否为当前栈顶节点的子节点（即其在中序遍历中是否在当前栈顶节点的左子树中），如果是，则将其入栈，并继续向左子树递归；如果不是，则说明当前节点是当前栈顶节点的右子节点，需要将当前栈顶节点出栈，并将其右子节点入栈，并继续向右子树递归；
4. 重复步骤3，直到遍历完整个序列；
5. 依次将栈中元素出栈，即为前序遍历的结果。

代码实现：

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

#define MAX_SIZE 100

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

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

void push(Stack *stack, TreeNode *node) {
    if (stack->top == MAX_SIZE - 1) {
        printf("Stack is full!
");
        return;
    }
    stack->data[++stack->top] = node;
}

TreeNode *pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack is empty!
");
        return NULL;
    }
    return stack->data[stack->top--];
}

TreeNode *buildTree(char *inOrder, char *postOrder, int length) {
    Stack stack;
    stack.top = -1;

    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->data = postOrder[length - 1];
    root->left = NULL;
    root->right = NULL;

    push(&stack, root);

    int i = length - 2;
    while (i >= 0) {
        TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
        node->data = postOrder[i];
        node->left = NULL;
        node->right = NULL;

        int flag = 0;
        while (stack.top != -1 && stack.data[stack.top]->data == inOrder[length - 1 - i]) {
            flag = 1;
            length--;
            node = pop(&stack);
        }
        if (flag == 0) {
            stack.data[stack.top]->right = node;
        } else {
            stack.data[stack.top]->left = node;
        }

        push(&stack, node);
        i--;
    }

    return root;
}

void preOrderTraversal(TreeNode *root) {
    Stack stack;
    stack.top = -1;

    TreeNode *node = root;
    while (node != NULL || stack.top != -1) {
        while (node != NULL) {
            printf("%c ", node->data);
            push(&stack, node);
            node = node->left;
        }
        if (stack.top != -1) {
            node = pop(&stack);
            node = node->right;
        }
    }
}

int main() {
    char inOrder[] = {'B', 'D', 'C', 'E', 'A', 'F', 'H', 'G'};
    char postOrder[] = {'D', 'E', 'C', 'B', 'H', 'G', 'F', 'A'};
    int length = sizeof(inOrder) / sizeof(char);

    TreeNode *root = buildTree(inOrder, postOrder, length);
    printf("Pre-order traversal: ");
    preOrderTraversal(root);
    printf("\n");
    return 0;
}

输出结果为：A B D C E F H G