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

本文介绍如何使用C语言非递归方法实现二叉树的前序遍历，并提供详细代码示例和解释。给定二叉树的中序遍历和后序遍历结果，利用栈数据结构，通过遍历中序和后序序列，构建二叉树并输出其前序遍历结果。

思路

1. 后序遍历的最后一个元素即为根节点，在中序遍历中找到根节点的位置，将其分为左子树和右子树。
2. 递归处理左子树和右子树，直到只有一个节点时返回。
3. 每次处理完左子树后，将左子树的根节点入栈，以备后续处理右子树时使用。
4. 最后输出栈中的元素，即为前序遍历结果。

代码实现

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

#define MAX_SIZE 10

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

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

void push(Stack *s, TreeNode *node) {
    if (s->top == MAX_SIZE - 1) {
        printf("栈满，无法入栈\n");
        return;
    }
    s->data[++(s->top)] = node;
}

TreeNode *pop(Stack *s) {
    if (s->top == -1) {
        printf("栈空，无法出栈\n");
        return NULL;
    }
    return s->data[(s->top)--];
}

TreeNode *buildTree(char *inOrder, char *postOrder, int n) {
    if (n <= 0) {
        return NULL;
    }
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->data = postOrder[n-1];
    int i;
    for (i = 0; i < n; i++) {
        if (inOrder[i] == postOrder[n-1]) {
            break;
        }
    }
    root->left = buildTree(inOrder, postOrder, i);
    root->right = buildTree(inOrder+i+1, postOrder+i, n-i-1);
    return root;
}

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

int main() {
    char inOrder[] = "BDCEAFHG";
    char postOrder[] = "DECBHGFA";
    TreeNode *root = buildTree(inOrder, postOrder, sizeof(inOrder)/sizeof(char));
    printf("前序遍历结果为：");
    preOrder(root);
    printf("\n");
    return 0;
}

代码解释

1. buildTree 函数：
   • 递归构建二叉树，根据后序遍历的最后一个元素作为根节点，在中序遍历中找到根节点的位置，将其分为左子树和右子树，分别递归构建左子树和右子树。
2. preOrder 函数：
   • 利用栈数据结构，实现非递归前序遍历。
   • 将根节点入栈。
   • 循环弹出栈顶元素，并输出其值。
   • 若该节点有右子树，则将右子树根节点入栈。
   • 若该节点有左子树，则将左子树根节点入栈。
   • 循环直到栈空。

总结

本文介绍了如何使用C语言非递归方法实现二叉树的前序遍历，利用栈数据结构，通过遍历中序和后序序列，构建二叉树并输出其前序遍历结果。该方法避免了递归的调用，可以有效地解决递归深度过深的问题。