c二叉树的后序遍历(非递归)

使用非递归方法进行C语言中二叉树的后序遍历可以借助栈来实现。以下是一个简单的示例代码：

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

#define MAX_STACK_SIZE 100

// 二叉树节点的结构体
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 栈的结构体
struct Stack {
    int top;
    struct TreeNode* array[MAX_STACK_SIZE];
};

// 创建一个栈
struct Stack* createStack() {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->top = -1;
    return stack;
}

// 判断栈是否为空
int isEmpty(struct Stack* stack) {
    return (stack->top == -1);
}

// 入栈操作
void push(struct Stack* stack, struct TreeNode* item) {
    if (stack->top >= MAX_STACK_SIZE - 1) {
        printf("Stack Overflow\\n");
        return;
    }
    stack->array[++stack->top] = item;
}

// 出栈操作
struct TreeNode* pop(struct Stack* stack) {
    if (isEmpty(stack))
        return NULL;
    return stack->array[stack->top--];
}

// 获取栈顶元素
struct TreeNode* peek(struct Stack* stack) {
    if (isEmpty(stack))
        return NULL;
    return stack->array[stack->top];
}

// 后序遍历二叉树的非递归实现
void postOrderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;

    struct Stack* stack1 = createStack();
    struct Stack* stack2 = createStack();

    push(stack1, root);

    while (!isEmpty(stack1)) {
        struct TreeNode* current = pop(stack1);
        push(stack2, current);

        if (current->left)
            push(stack1, current->left);
        if (current->right)
            push(stack1, current->right);
    }

    while (!isEmpty(stack2)) {
        struct TreeNode* current = pop(stack2);
        printf("%d ", current->data);
    }
}

// 测试
int main() {
    // 构造一个简单的二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->data = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->data = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->data = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    // 执行后序遍历
    printf("后序遍历结果: ");
    postOrderTraversal(root);

    return 0;
}

请注意，上述代码中的结构体TreeNode表示二叉树的节点，而结构体Stack表示栈。postOrderTraversal函数实现了二叉树的后序遍历。