C语言实现二叉树前序遍历（非递归）

问题描述：

已知二叉树的中序遍历为'BDCEAFHG'，后序遍历为'DECBHGFA'，要求使用C语言编写程序输出该二叉树的前序遍历结果，并使用非递归方法实现。

思路分析：

创建二叉树: 根据中序遍历和后序遍历的结果，我们可以构建二叉树。后序遍历的最后一个元素是根节点，在中序遍历中找到根节点的位置，将其左边的部分作为左子树，右边的部分作为右子树，递归地进行构建。
非递归前序遍历: 前序遍历的顺序是根节点、左子树、右子树。我们可以使用栈来实现非递归遍历。首先将根节点入栈，然后循环遍历栈，每次取出栈顶节点并访问，再将该节点的右子树和左子树入栈（注意顺序，先右子树再左子树），直到栈为空为止。

代码实现：

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

#define MAX_SIZE 100

// 定义二叉树的结构体
typedef struct TreeNode {
    char data; // 节点数据
    struct TreeNode *left; // 左子树指针
    struct TreeNode *right; // 右子树指针
} TreeNode;

// 创建二叉树
TreeNode *createTree(char inorder[], char postorder[], int n) {
    if (n <= 0) {
        return NULL;
    }

    // 创建根节点
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->data = postorder[n - 1];
    root->left = NULL;
    root->right = NULL;

    // 查找根节点在中序遍历中的位置
    int i = 0;
    while (inorder[i] != root->data) {
        i++;
    }

    // 创建左子树和右子树
    root->left = createTree(inorder, postorder, i);
    root->right = createTree(inorder + i + 1, postorder + i, n - i - 1);

    return root;
}

// 前序遍历二叉树（非递归实现）
void preorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    // 定义栈，存储待访问节点
    TreeNode *stack[MAX_SIZE];
    int top = -1;

    // 将根节点入栈
    stack[++top] = root;

    while (top >= 0) {
        // 访问栈顶节点，并出栈
        TreeNode *node = stack[top--];
        printf('%c ', node->data);

        // 将右子树和左子树入栈，注意顺序
        if (node->right != NULL) {
            stack[++top] = node->right;
        }
        if (node->left != NULL) {
            stack[++top] = node->left;
        }
    }
}

int main() {
    char inorder[MAX_SIZE];
    char postorder[MAX_SIZE];
    int n;

    // 输入中序遍历和后序遍历的结果
    printf("请输入中序遍历结果：");
    scanf("%s", inorder);
    printf("请输入后序遍历结果：");
    scanf("%s", postorder);
    n = strlen(inorder);

    // 创建二叉树
    TreeNode *root = createTree(inorder, postorder, n);

    // 前序遍历二叉树（非递归实现）
    printf("前序遍历结果为：");
    preorderTraversal(root);

    return 0;
}

代码解释：

createTree() 函数根据中序遍历和后序遍历构建二叉树，使用递归方法实现，核心思路是找到后序遍历中最后一个节点作为根节点，在中序遍历中找到根节点的位置，将根节点左边的部分作为左子树，右边的部分作为右子树，递归地构建子树。
preorderTraversal() 函数使用非递归方法实现前序遍历，使用栈存储待访问节点。首先将根节点入栈，然后循环遍历栈，每次取出栈顶节点并访问，再将该节点的右子树和左子树入栈（注意顺序，先右子树再左子树），直到栈为空为止。
main() 函数负责接收用户输入的中序遍历和后序遍历结果，调用 createTree() 函数创建二叉树，然后调用 preorderTraversal() 函数进行前序遍历，并将结果输出。

为什么要使用 scanf 函数？

scanf 函数用于接收用户从键盘输入的字符串。在本例中，我们需要用户手动输入中序遍历和后序遍历的结果，才能创建二叉树并进行遍历。如果没有 scanf 函数，我们就无法输入数据，程序也就无法正常运行。

总结：

本代码展示了如何使用 C 语言非递归方法实现二叉树的前序遍历，并附带详细的代码注释和思路解释，希望能帮助您更好地理解二叉树的遍历算法。