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

绝地灬酷狼 2024-04-22 07:10 15阅读 0赞

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

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 和 stack2
            Stack<TreeNode> stack2 = new Stack<>();
            stack1.push(root); // 将根节点压入 stack1
    
            while (!stack1.isEmpty()) {
         // 当 stack1 不为空时
                TreeNode node = stack1.pop(); // 从 stack1 中弹出顶部节点并将其压入 stack2
                stack2.push(node);
    
                if (node.left != null) {
         // 如果弹出的节点有左子节点，将其压入 stack1
                    stack1.push(node.left);
                }
    
                if (node.right != null) {
         // 如果弹出的节点有右子节点，将其压入 stack1
                    stack1.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