如何用栈对二叉树进行前序、中序、后序遍历

在前序、中序、后序遍历中可以用以下步骤进行

1. 前序遍历：
   1. 创建一个空栈，并将根节点压入栈中。
   2. 当栈不为空时：
      1. 弹出栈顶节点并处理（例如，打印）其值。
      2. 如果弹出的节点有右子节点，将其压入栈中。
      3. 如果弹出的节点有左子节点，将其压入栈中。
   3. 继续此过程，直到栈为空。
2. 中序遍历：
   1. 初始化一个空栈，并将当前节点设置为根节点。
   2. 当栈不为空或当前节点不为空时：
      1. 如果当前节点不为空，将其压入栈中并移动到其左子节点。
      2. 如果当前节点为空，从栈中弹出顶部节点，处理其值，并将当前节点设置为其右子节点。
   3. 重复此过程，直到栈为空且当前节点为空。
3. 后序遍历：
   1. 创建两个栈，stack1 和 stack2。
   2. 将根节点压入 stack1。
   3. 当 stack1 不为空时：
      1. 从 stack1 中弹出顶部节点并将其压入 stack2。
      2. 如果弹出的节点有左子节点，将其压入 stack1。
      3. 如果弹出的节点有右子节点，将其压入 stack1。
   4. 当 stack2 不为空时，弹出并处理其节点的值。

在二叉树遍历中，用栈对二叉树进行前序、中序、后序遍历代码如下

import java.io.Serializable;
import java.util.Stack;class TreeNode implements Serializable {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}public class BinaryTreeTraversal {public static void main(String[] args) {/*              1*         /        \\*        2           3*       /  \\        /   \\*      4    5      6     7*     / \\  / \\    / \\   / \\*    8  9 10 11 12 13  14 15*/// 构建一个简单的二叉树TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.right.left = new TreeNode(6);root.right.right = new TreeNode(7);root.left.left.left = new TreeNode(8);root.left.left.right = new TreeNode(9);root.left.right.left = new TreeNode(10);root.left.right.right = new TreeNode(11);root.right.left.left = new TreeNode(12);root.right.left.right = new TreeNode(13);root.right.right.left = new TreeNode(14);root.right.right.right = new TreeNode(15);System.out.println("前序遍历：");preOrderTraversal(root);System.out.println("\\n中序遍历：");inOrderTraversal(root);System.out.println("\\n后序遍历：");postOrderTraversal(root);}// 前序遍历public static void preOrderTraversal(TreeNode root) {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);}}}// 中序遍历public static void inOrderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>(); // 初始化一个空栈TreeNode current = root; // 将当前节点设置为根节点while (!stack.isEmpty() || current != null) { // 当栈不为空或当前节点不为空时if (current != null) { // 如果当前节点不为空，将其压入栈中并移动到其左子节点stack.push(current);current = current.left;} else { // 如果当前节点为空，从栈中弹出顶部节点，处理其值，并将当前节点设置为其右子节点TreeNode node = stack.pop();System.out.print(node.val + " ");current = node.right;}}}// 后序遍历public static void postOrderTraversal(TreeNode root) {Stack<TreeNode> stack1 = new Stack<>(); // 创建两个栈，stack1 和 stack2Stack<TreeNode> stack2 = new Stack<>();stack1.push(root); // 将根节点压入 stack1while (!stack1.isEmpty()) { // 当 stack1 不为空时TreeNode node = stack1.pop(); // 从 stack1 中弹出顶部节点并将其压入 stack2stack2.push(node);if (node.left != null) { // 如果弹出的节点有左子节点，将其压入 stack1stack1.push(node.left);}if (node.right != null) { // 如果弹出的节点有右子节点，将其压入 stack1stack1.push(node.right);}}while (!stack2.isEmpty()) { // 当 stack2 不为空时，弹出并处理其节点的值TreeNode node = stack2.pop();System.out.print(node.val + " ");}}}

结果输出

前序遍历：
1 2 4 8 9 5 10 11 3 6 12 13 7 14 15 
中序遍历：
8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 
后序遍历：
8 9 4 10 11 5 2 12 13 6 14 15 7 3 1 

安全期在线查询