通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式

本文将讲解C语言和Java中二叉树的三种非递归遍历方式：先序遍历、中序遍历和后序遍历。这三种遍历方式分别可以使用栈来实现非递归遍历。下面将详细讲解这三种遍历方式的实现过程。

先序遍历

先序遍历的遍历顺序是中->左->右。实现的过程如下：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
struct Stack {
    struct TreeNode** arr;
    int top;
};
struct Stack* createStack(int size) {
    struct Stack* s = (struct Stack*)malloc(sizeof(struct Stack));
    s->arr = (struct TreeNode**)malloc(size * sizeof(struct TreeNode*));
    s->top = -1;
    return s;
}
void push(struct Stack* s, struct TreeNode* node) {
    s->top++;
    s->arr[s->top] = node;
}
struct TreeNode* pop(struct Stack* s) {
    struct TreeNode* node = s->arr[s->top];
    s->top--;
    return node;
}
void preorderTraversal(struct TreeNode* root) {
    if (!root) {
        return;
    }
    struct Stack* s = createStack(1000);
    push(s, root);
    while (s->top >= 0) {
        struct TreeNode* node = pop(s);
        printf("%d->", node->val);
        if (node->right) {
            push(s, node->right);
        }
        if (node->left) {
            push(s, node->left);
        }
    }
}

该函数中的createStack函数为创建一个栈，push函数为入栈操作，pop函数为出栈操作。该函数使用了preorderTraversal函数来实现树的先序遍历。我们首先使用栈将根节点入栈，之后在循环中，每次将栈的顶部节点弹出并打印，如果弹出 node 的右子树不为空，将右节点先入栈，如果弹出 node 的左子树不为空，将左节点后入栈。需要注意的是，我们需要先将右节点入栈，该操作是由栈的特性决定的。

示例：假定创建一个二叉树，根节点为1，左子树为2和3，右子树为4和5。通过前序遍历，输出的结果为1->2->3->4->5->。

中序遍历

中序遍历的遍历顺序是左->中->右。实现的过程如下：

void inorderTraversal(struct TreeNode* root) {
    struct Stack* s = createStack(1000);
    while (root || s->top >= 0) {
        while (root) {
            push(s, root);
            root = root->left;
        }
        root = pop(s);
        printf("%d->", root->val);
        root = root->right;
    }
}

该函数使用了inorderTraversal函数来实现树的中序遍历。递归实现是先访问左子树，再访问根节点，最后访问右子树。非递归实现类似于递归，需要用到一个栈来模拟递归过程，首先将根节点入栈，之后在循环中，当树的左子树不为空时，将左子树入栈，对于每个弹出来的节点，先访问该节点，之后将该节点的右子树入栈。需要注意的是，当树的左子树为空时，需要将栈顶元素弹出并打印，之后访问该弹出元素的右子树。

示例：假定创建一个二叉树，根节点为1，左子树为2和3，右子树为4和5。通过中序遍历，输出的结果为2->1->3->4->5->。

后序遍历

后序遍历的遍历顺序是左->右->中。实现的过程如下：

void postorderTraversal(struct TreeNode* root) {
    struct Stack* s1 = createStack(1000);
    struct Stack* s2 = createStack(1000);
    push(s1, root);
    while (s1->top >= 0) {
        struct TreeNode* node = pop(s1);
        push(s2, node);
        if (node->left) {
            push(s1, node->left);
        }
        if (node->right) {
            push(s1, node->right);
        }
    }
    while (s2->top >= 0) {
        struct TreeNode* node = pop(s2);
        printf("%d->", node->val);
    }
}

该函数使用了postorderTraversal函数来实现树的后序遍历，使用了两个栈。首先将根节点入栈，之后在循环中，每次将栈的顶部节点弹出并入栈s2，如果弹出 node 的左子树不为空，将左节点先入栈，如果弹出 node 的右子树不为空，将右节点后入栈。需要注意的是，栈s2存储的是处理后的节点，所以需要存储两次。

示例：假定创建一个二叉树，根节点为1，左子树为2和3，右子树为4和5。通过后序遍历，输出的结果为2->3->5->4->1->。