Java非递归实现之二叉树的前中后序遍历详解

1、概述

在程序设计中，二叉树是一种常用的数据结构，而对二叉树进行遍历则是非常基础和重要的操作。二叉树的遍历分为三种：前序遍历、中序遍历和后序遍历。

常规的二叉树遍历算法使用递归完成，但是递归算法的效率比较低，同时深度过深还会导致调用栈溢出，因此我们可以采用非递归的方式来实现二叉树的遍历。

本文将通过Java代码，详细说明如何使用非递归的方式来实现二叉树的前、中、后序遍历。

2、前序遍历实现

前序遍历的顺序是：根节点、左子树、右子树。下面是非递归实现的前序遍历方法。

/**
 * 非递归前序遍历
 * @param root 二叉树的根节点
 */
public void preOrderTraversal(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root); // 根节点入栈
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        // 先将右子树入栈
        if (node.right != null) stack.push(node.right);
        // 再将左子树入栈
        if (node.left != null) stack.push(node.left);
    }
}

我们使用栈来模拟递归的过程，但是和递归不同的是，在入栈的时候，先将右子树入栈，然后再将左子树入栈，这是因为节点出栈的顺序是先左子树，然后右子树，最后根节点，使用这样的顺序保证了节点出栈的顺序符合前序遍历的规则。

例如，对于下面的二叉树：

         1
        / \
       2   3
      / \   \
     4   5   6

我们非递归前序遍历的结果是：1 2 4 5 3 6

3、中序遍历实现

中序遍历的顺序是：左子树、根节点、右子树。下面是非递归实现的中序遍历方法。

/**
 * 非递归中序遍历
 * @param root 二叉树的根节点
 */
public void inOrderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        cur = node.right;
    }
}

我们使用栈来模拟递归的过程，首先将根节点入栈，然后将当前节点设置为左子树，直到没有左子树了，此时节点出栈，然后将当前节点设置为右子树，再开始新一轮的遍历。

例如，对于下面的二叉树：

         1
        / \
       2   3
      / \   \
     4   5   6

我们非递归中序遍历的结果是：4 2 5 1 3 6

4、后序遍历实现

后序遍历的顺序是：左子树、右子树、根节点。下面是非递归实现的后序遍历方法。

/**
 * 非递归后序遍历
 * @param root 二叉树的根节点
 */
public void postOrderTraversal(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        if (node.left != null) stack1.push(node.left);
        if (node.right != null) stack1.push(node.right);
    }
    while (!stack2.isEmpty()) {
        TreeNode node = stack2.pop();
        System.out.print(node.val + " ");
    }
}

我们使用两个栈来实现后序遍历，首先将根节点入栈1，然后将节点依次出栈放入栈2，同时将左右子树入栈1，当栈1为空时，栈2中的节点就是按照后序遍历的顺序排列的。

例如，对于下面的二叉树：

         1
        / \
       2   3
      / \   \
     4   5   6

我们非递归后续遍历的结果是：4 5 2 6 3 1

5、总结

使用非递归的方式实现二叉树的遍历操作，可以避免递归带来的调用栈过深的问题，提高算法的效率。本文介绍了使用Java代码实现二叉树的前序、中序、后序遍历的非递归方法，希望对你有所帮助。