C语言非递归实现二叉树前序遍历：中序遍历为BDCEAFHG，后序遍历为DECBHGFA

问题描述： 已知二叉树的中序遍历为'BDCEAFHG'，后序遍历为'DECBHGFA'，要求使用C语言编写程序输出该二叉树的前序遍历结果，并且不能使用递归的方法。

思路分析：

构建二叉树： 由于题目已知中序遍历和后序遍历，我们可以利用它们来构建二叉树。
- 中序遍历：遍历顺序为左子树 - 根节点 - 右子树。
- 后序遍历：遍历顺序为左子树 - 右子树 - 根节点。
- 因此，后序遍历的最后一个元素一定是根节点。
- 在中序遍历中，根节点左边部分对应左子树，右边部分对应右子树。
- 利用上述信息，我们可以递归地构建二叉树。
非递归前序遍历： 前序遍历的顺序为根节点 - 左子树 - 右子树。
- 由于不能使用递归，我们可以使用栈来模拟递归过程。
- 将当前节点入栈，并输出该节点。
- 如果当前节点有右子树，则将右子树的根节点入栈。
- 如果当前节点有左子树，则将左子树的根节点入栈。
- 重复上述过程，直到栈为空。

代码实现：

#include <stdio.h>
#define MAXN 50
int n, L[MAXN], R[MAXN];
char s[MAXN];

int build(int l1, int r1, int l2, int r2) { // 根据中序遍历和后序遍历建树
    if (l1 > r1) return 0; // 递归边界：中序遍历的左右边界交叉，表示当前子树为空
    int root = L[n++]; // 从后序遍历中获取根节点，并用n记录当前节点编号
    int p = l2; // 从后序遍历中查找根节点
    while (s[p] != root) p++; // 找到根节点的位置
    if (p != r2) { // 如果根节点不是后序遍历的最后一个元素，则有右子树
        R[root] = build(l1 + p - l2 + 1, r1, p + 1, r2); // 递归构建右子树
    }
    if (p != l2) { // 如果根节点不是后序遍历的第一个元素，则有左子树
        L[root] = build(l1, l1 + p - l2 - 1, l2, p - 1); // 递归构建左子树
    }
    return root; // 返回根节点
}

void pre(int u) { // 前序遍历，使用栈模拟递归的过程
    int stack[MAXN], top = 0; // 栈
    while (u || top) { // 当当前节点不为空或者栈不为空时，循环遍历
        while (u) { // 当当前节点不为空时
            printf("%d ", u); // 输出当前节点
            stack[top++] = u; // 将当前节点入栈
            u = R[u]; // 访问右子树
        }
        u = stack[--top]; // 出栈，访问左子树
        u = L[u]; // 访问左子树
    }
}

int main() {
    scanf("%s", s); // 输入中序遍历和后序遍历字符串
    int l1 = 0, r1 = 0, l2 = 0, r2 = 0;
    while (s[r1]) r1++; // 遍历中序遍历字符串，获取长度
    while (s[r2]) r2++; // 遍历后序遍历字符串，获取长度
    for (int i = 0; i < r1; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') { // 初始化每个节点的左右儿子为空
            L[s[i]] = R[s[i]] = 0;
            if (!l1) l1 = s[i]; // 记录根节点
        }
    }
    build(l1, r1 - 1, 0, r2 - 1); // 构建二叉树
    pre(l1); // 前序遍历
    return 0;
}

代码解释：

build()函数：
- 递归构建二叉树，根据中序遍历和后序遍历的左右边界来确定当前子树的根节点、左子树和右子树。
- 使用n来记录当前节点的编号。
pre()函数：
- 使用栈模拟递归，将当前节点入栈，并输出该节点。
- 优先访问右子树，然后访问左子树。
- 当栈为空时，遍历结束。
main()函数：
- 输入中序遍历和后序遍历字符串。
- 初始化每个节点的左右儿子为空。
- 调用build()函数构建二叉树。
- 调用pre()函数输出前序遍历结果。

总结： 本文详细讲解了如何利用C语言非递归算法，根据已知的二叉树中序遍历和后序遍历，构建二叉树并输出其前序遍历结果。代码附详细注释，帮助读者理解非递归实现的思路和具体步骤。希望本文能够帮助读者更好地理解二叉树的遍历算法。

C语言非递归实现二叉树前序遍历：中序遍历为BDCEAFHG，后序遍历为DECBHGFA