用C语言写二叉树的非递归遍历

二叉树的非递归遍历可以使用栈来实现。以下是C语言实现二叉树非递归遍历的示例代码：

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

// 定义二叉树结点类型
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 定义栈结点类型
typedef struct StackNode {
    TreeNode *node;
    struct StackNode *next;
} StackNode;

// 创建栈
StackNode* createStack() {
    return NULL;
}

// 判断栈是否为空
int isStackEmpty(StackNode *stack) {
    return stack == NULL;
}

// 将结点压入栈中
void push(StackNode **stack, TreeNode *node) {
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->node = node;
    newNode->next = *stack;
    *stack = newNode;
}

// 从栈中弹出结点
TreeNode* pop(StackNode **stack) {
    if (isStackEmpty(*stack)) {
        return NULL;
    }
    StackNode *top = *stack;
    TreeNode *node = top->node;
    *stack = top->next;
    free(top);
    return node;
}

// 非递归前序遍历
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    StackNode *stack = createStack();
    push(&stack, root);
    while (!isStackEmpty(stack)) {
        TreeNode *node = pop(&stack);
        printf("%d ", node->val);
        if (node->right != NULL) {
            push(&stack, node->right);
        }
        if (node->left != NULL) {
            push(&stack, node->left);
        }
    }
}

// 非递归中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    StackNode *stack = createStack();
    TreeNode *node = root;
    while (node != NULL || !isStackEmpty(stack)) {
        while (node != NULL) {
            push(&stack, node);
            node = node->left;
        }
        node = pop(&stack);
        printf("%d ", node->val);
        node = node->right;
    }
}

// 非递归后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    StackNode *stack1 = createStack();
    StackNode *stack2 = createStack();
    push(&stack1, root);
    while (!isStackEmpty(stack1)) {
        TreeNode *node = pop(&stack1);
        push(&stack2, node);
        if (node->left != NULL) {
            push(&stack1, node->left);
        }
        if (node->right != NULL) {
            push(&stack1, node->right);
        }
    }
    while (!isStackEmpty(stack2)) {
        TreeNode *node = pop(&stack2);
        printf("%d ", node->val);
    }
}

// 测试代码
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: ");
    preorderTraversal(root);
    printf("\n");

    // 非递归中序遍历
    printf("Inorder Traversal: ");
    inorderTraversal(root);
    printf("\n");

    // 非递归后序遍历
    printf("Postorder Traversal: ");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

输出结果：

Preorder Traversal: 1 2 3 4 5 
Inorder Traversal: 2 1 4 3 5 
Postorder Traversal: 2 4 5 3 1