用C语言实现非递归二叉树先序遍历、中序遍历和后序遍历

下面是用C语言实现非递归二叉树先序遍历、中序遍历和后序遍历的代码示例：

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

#define MAX_STACK_SIZE 100

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

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

void push(Stack *stack, TreeNode *node) {
    if (stack->top == MAX_STACK_SIZE - 1) {
        printf("Stack overflow.\n");
        return;
    }
    stack->data[++stack->top] = node;
}

TreeNode *pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack underflow.\n");
        exit(1);
    }
    return stack->data[stack->top--];
}

int is_empty(Stack *stack) {
    return stack->top == -1;
}

void preorder_traversal(TreeNode *root) {
    if (!root) {
        return;
    }
    Stack stack = { .top = -1 };
    push(&stack, root);
    while (!is_empty(&stack)) {
        TreeNode *node = pop(&stack);
        printf("%d ", node->val);
        if (node->right) {
            push(&stack, node->right);
        }
        if (node->left) {
            push(&stack, node->left);
        }
    }
    printf("\n");
}

void inorder_traversal(TreeNode *root) {
    if (!root) {
        return;
    }
    Stack stack = { .top = -1 };
    TreeNode *node = root;
    while (node || !is_empty(&stack)) {
        if (node) {
            push(&stack, node);
            node = node->left;
        } else {
            node = pop(&stack);
            printf("%d ", node->val);
            node = node->right;
        }
    }
    printf("\n");
}

void postorder_traversal(TreeNode *root) {
    if (!root) {
        return;
    }
    Stack stack = { .top = -1 };
    TreeNode *node = root, *prev = NULL;
    while (node || !is_empty(&stack)) {
        if (node) {
            push(&stack, node);
            node = node->left;
        } else {
            node = stack.data[stack.top];
            if (node->right && node->right != prev) {
                node = node->right;
            } else {
                printf("%d ", node->val);
                prev = node;
                node = NULL;
                pop(&stack);
            }
        }
    }
    printf("\n");
}

int main() {
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->right->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->left->val = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->right->val = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    printf("Preorder traversal: ");
    preorder_traversal(root);

    printf("Inorder traversal: ");
    inorder_traversal(root);

    printf("Postorder traversal: ");
    postorder_traversal(root);

    return 0;
}

这个代码示例中，我们使用了栈来实现非递归遍历二叉树。对于先序遍历，我们先将根节点入栈，然后弹出栈顶元素，先访问该节点，再将其右子节点和左子节点依次入栈。对于中序遍历，我们从根节点开始，先将所有左子节点入栈，然后弹出栈顶元素，访问该节点，再将其右子节点入栈。对于后序遍历，我们需要记录上一个访问的节点，以便在访问完右子节点后，再访问父节点。具体实现可以参考代码示例。