Java实现二叉树非递归遍历：前序、中序、后序

"这篇文档详细阐述了如何在Java中使用非递归方法遍历二叉树，主要包括前序遍历、中序遍历和后序遍历三种方式，所有方法都借助栈作为辅助数据结构来实现。" 在二叉树遍历中，非递归方法是一种常见的优化策略，它可以避免递归带来的调用栈开销，尤其对于深度较大的树，性能优势更为明显。以下是三种非递归遍历方法的具体介绍： ### 前序遍历 前序遍历的顺序是根-左-右。其基本思路是： 1. 将根节点入栈。 2. 当栈不为空时，循环执行以下操作：弹出栈顶元素，打印该节点值，然后依次将右子节点、左子节点入栈（如果它们非空）。这样可以确保每次打印的节点都是当前子树的根节点。 对应的Java代码如下： ```java public static ArrayList<Integer> preOrder(TreeNode root) { ArrayList<Integer> list = new ArrayList<>(); ArrayDeque<TreeNode> stack = new ArrayDeque<>(); if (root != null) { stack.push(root); while (!stack.isEmpty()) { root = stack.pop(); list.add(root.val); if (root.right != null) { stack.push(root.right); } if (root.left != null) { stack.push(root.left); } } } return list; } ``` ### 中序遍历 中序遍历的顺序是左-根-右。中序遍历需要一直找到左子树的最底层，然后访问节点，再访问右子树。具体做法是： 1. 如果根节点非空，将根节点入栈，然后不断将当前节点设为其左子节点，直到左子节点为空。 2. 弹出栈顶元素，打印节点值，并将右子节点入栈。 3. 重复以上步骤，直至栈为空。 对应的Java代码如下： ```java public static ArrayList<Integer> inorder(TreeNode root) { ArrayList<Integer> list = new ArrayList<>(); ArrayDeque<TreeNode> stack = new ArrayDeque<>(); while (root != null || !stack.isEmpty()) { if (root != null) { stack.push(root); root = root.left; } else { root = stack.pop(); list.add(root.val); root = root.right; } } return list; } ``` ### 后序遍历 后序遍历的顺序是左-右-根，这是最难实现的一种遍历方式。通常需要两个栈来完成： 1. 使用栈S1按照层次顺序压入节点（根-左-右），形成一个“倒树”结构。 2. 使用栈S2记录每次从S1弹出的节点，当S1为空或弹出节点的右子节点为空且左子节点也为空时，将节点值加入结果列表，并将该节点的父节点压入S2。 3. 当S1为空，S2中的最后一个节点就是根节点，将其值加入结果列表，并从S2中移除。 由于Java代码较为复杂，这里不再给出具体实现，但大致思路如上所述。在实际编程中，可以结合具体的题目需求，调整代码以满足后序遍历的要求。 总结来说，非递归遍历二叉树的方法虽然比递归方式复杂一些，但通过合理地利用栈的数据结构，我们可以有效地控制遍历的顺序，实现前序、中序和后序遍历。这种方法不仅节省了内存，而且在处理大规模数据时效率更高。