Java实现对二叉树前序/中序/后序的递归与非递归算法

二叉树遍历定义

二叉树的遍历是指按照某种顺序访问树中的每个节点，确保每个节点被访问且仅被访问一次。常见的遍历方式包括前序、中序和后序遍历，其定义如下：

前序遍历 (Pre-order Traversal)：对任一子树，先访问根节点，然后遍历其左子树，最后遍历其右子树。
中序遍历 (In-order Traversal)：对任一子树，先遍历其左子树，然后访问根节点，最后遍历其右子树。
后序遍历 (Post-order Traversal)：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根节点。

二叉树节点类定义

首先定义二叉树的节点类 Node。该类包含节点值、左子节点引用和右子节点引用。为了方便测试，类中还提供了一个静态方法 createTree，用于构建一个包含 7 个节点的固定二叉树结构。

public class Node {
    // 节点值
    public int value;

    // 左子节点
    public Node left;

    // 右子节点
    public Node right;

    Node(int va) {
        value = va;
    }

    Node(int va, Node le, Node ri) {
        value = va;
        left = le;
        right = ri;
    }

    /**
     * 创建一颗二叉树
     *
     * @return 根节点
     */
    public static Node createTree() {
        Node root = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node3.left = node7;
        return root;
    }
}

遍历算法实现

创建遍历类 Traverse，在该类中分别实现前序、中序、后序的递归与非递归算法。非递归实现通常借助栈（Stack）数据结构来完成。在本示例中，为了演示原理，使用 ArrayList 模拟栈的行为。

import java.util.ArrayList;

public class Traverse {

    /**
     * 递归前序遍历
     *
     * @param root 根节点
     */
    public void recursiveProOrder(Node root) {
        if (root != null) {
            System.out.print(root.value);
            // 遍历左子树
            if (root.left != null) {
                recursiveProOrder(root.left);
            }
            // 遍历右子树
            if (root.right != null) {
                recursiveProOrder(root.right);
            }
        }
    }

    /**
     * 非递归前序遍历
     *
     * @param root 根节点
     */
    public void proOrder(Node root) {
        // 使用 ArrayList 作为堆栈
        ArrayList<Node> stack = new ArrayList<Node>();
        // 栈指针
        int top = -1;
        Node current = root;
        while (true) {
            if (current != null) {
                System.out.print(current.value);
            }
            // 右子节点进栈
            if (current.right != null) {
                stack.add(current.right);
                top++;
            }
            // 左子节点进栈
            if (current.left != null) {
                stack.add(current.left);
                top++;
            }
            // 如果栈内还有节点，栈顶节点出栈
            if (top > -1) {
                current = stack.get(top);
                stack.remove(top--);
            } else {
                break;
            }
        }
    }

    /**
     * 递归中序遍历
     *
     * @param root 根节点
     */
    public void recursiveInOrder(Node root) {
        if (root != null) {
            if (root.left != null) {
                recursiveInOrder(root.left);
            }
            System.out.print(root.value);
            if (root.right != null) {
                recursiveInOrder(root.right);
            }
        }
    }

    /**
     * 非递归中序遍历
     *
     * @param root 根节点
     */
    public void inOrder(Node root) {
        if (root != null) {
            ArrayList<Node> stack = new ArrayList<Node>();
            int top = -1;
            Node current = root;
            while (current != null || top > -1) {
                if (current != null) {
                    // 一直深入地寻找左子节点，并将路上的节点都进栈
                    stack.add(current);
                    top++;
                    current = current.left;
                } else {
                    // 取出栈顶节点，并继续遍历右子树
                    current = stack.get(top);
                    stack.remove(top--);
                    System.out.print(current.value);
                    current = current.right;
                }
            }
        }
    }

    /**
     * 递归后序遍历
     *
     * @param root 根节点
     */
    public void recursivePostOrder(Node root) {
        if (root != null) {
            if (root.left != null) {
                recursivePostOrder(root.left);
            }
            if (root.right != null) {
                recursivePostOrder(root.right);
            }
            System.out.print(root.value);
        }
    }

    /**
     * 非递归后序遍历
     * 说明：可以被遍历的节点都要进栈出栈两次，所以添加第二个栈用来标示进栈次数
     *
     * @param root 根节点
     */
    public void postOrder(Node root) {
        if (root != null) {
            // 用来保存节点的栈
            ArrayList<Node> stack = new ArrayList<Node>();
            // 用来保存标志位的栈
            ArrayList<Integer> stack2 = new ArrayList<Integer>();
            // 两个栈共用的栈指针
            int top = -1;
            int tag;
            Node current = root;
            do {
                // 将所有左子节点进栈
                while (current != null) {
                    stack.add(current);
                    stack2.add(0);
                    top++;
                    current = current.left;
                }
                // 取出栈顶节点，并判断其标志位
                current = stack.get(top);
                tag = stack2.get(top);
                stack2.remove(top);
                if (tag == 0) {
                    // tag 为 0，表明该节点第一次进栈，还需要进栈一次，同时修改标志位
                    current = current.right;
                    stack2.add(1);
                } else {
                    // tag 不为 0，表明非首次进栈，可以遍历了
                    stack.remove(top);
                    top--;
                    System.out.print(current.value);
                    current = null;
                }
            } while (current != null || top != -1);
        }
    }
}

测试与运行结果

实例化遍历类并调用各个遍历方法，验证算法的正确性。

public class Algorithm {

    public static void main(String[] args) {
        Node root = Node.createTree();
        
        System.out.print("前序遍历： ");
        new Traverse().proOrder(root);
        System.out.println();
        
        System.out.print("前序递归遍历： ");
        new Traverse().recursiveProOrder(root);
        System.out.println();
        
        System.out.print("中序遍历： ");
        new Traverse().inOrder(root);
        System.out.println();
        
        System.out.print("中序递归遍历： ");
        new Traverse().recursiveInOrder(root);
        System.out.println();
        
        System.out.print("后序遍历： ");
        new Traverse().postOrder(root);
        System.out.println();
        
        System.out.print("后序递归遍历： ");
        new Traverse().recursivePostOrder(root);
    }
}

控制台输出结果：

前序遍历：        01374256
前序递归遍历：    01374256
中序遍历：        73140526
中序递归遍历：    73140526
后序遍历：        73415620
后序递归遍历：    73415620

说明

代码版本：本文代码基于标准 Java 语法，适用于 Java 8 及以上版本。
栈的实现：为了清晰展示非递归算法中栈的操作逻辑（如指针移动、进出栈时机），示例代码中使用 ArrayList 配合手动维护的 top 指针来模拟栈。在实际生产环境中，建议直接使用 Java 集合框架提供的 Stack 类或 Deque 接口（如 ArrayDeque）以获得更好的性能和安全性。
术语修正：原文中部分术语（如“跟”、“后续”）已修正为标准的“根”、“后序”。

本文地址：https://1diff.fun/archives/java-shi-xian-dui-er-cha-shu-qian-xu--zhong-xu--hou-xu-de-di-gui-yu-fei-di-gui-suan-fa.html

如果对本文有什么问题或疑问都可以在评论区留言，我看到后会尽量解答。

Java实现对二叉树前序/中序/后序的递归与非递归算法

二叉树遍历定义

二叉树节点类定义

遍历算法实现

测试与运行结果

说明

发表评论

表情类型

目录