用非递归实现二叉树的前序、中序、后序遍历算法c语言代码

下面是用非递归实现二叉树的前序、中序、后序遍历算法的C语言代码：

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

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

/* 前序遍历 */
void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    TreeNode* stack[100];
    int top = -1;
    stack[++top] = root;
    while (top != -1) {
        TreeNode* node = stack[top--];
        printf("%d ", node->val);
        if (node->right != NULL) stack[++top] = node->right;
        if (node->left != NULL) stack[++top] = node->left;
    }
}

/* 中序遍历 */
void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    TreeNode* stack[100];
    int top = -1;
    TreeNode* node = root;
    while (top != -1 || node != NULL) {
        while (node != NULL) {
            stack[++top] = node;
            node = node->left;
        }
        node = stack[top--];
        printf("%d ", node->val);
        node = node->right;
    }
}

/* 后序遍历 */
void postorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    TreeNode* stack1[100];
    TreeNode* stack2[100];
    int top1 = -1, top2 = -1;
    stack1[++top1] = root;
    while (top1 != -1) {
        TreeNode* node = stack1[top1--];
        stack2[++top2] = node;
        if (node->left != NULL) stack1[++top1] = node->left;
        if (node->right != NULL) stack1[++top1] = node->right;
    }
    while (top2 != -1) {
        printf("%d ", stack2[top2--]->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("前序遍历：");
    preorderTraversal(root);
    printf("\n中序遍历：");
    inorderTraversal(root);
    printf("\n后序遍历：");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

在这个代码中，我们使用了栈来实现非递归遍历二叉树。对于前序遍历，我们先将根节点入栈，然后每次取出栈顶元素，并将其右子节点和左子节点入栈；对于中序遍历，我们先将左子节点全部入栈，再取出栈顶元素，并将其右子节点入栈；对于后序遍历，我们使用两个栈，先将根节点入栈1，然后每次取出栈1的栈顶元素，并将其左子节点和右子节点入栈1，同时将该元素入栈2，最后将栈2中的元素依次出栈即可。