JAVA二叉树的几种遍历(递归，非递归)实现

二叉树(Binary Tree)是非常重要的数据结构之一，Java中也提供了各种各样的二叉树实现方式。在学习Java的二叉树时，了解二叉树的三种遍历方式非常必要，包括前序遍历、中序遍历和后序遍历。

二叉树遍历

对于二叉树的遍历方式，可以简单地分为两类：深度优先遍历（Depth-First Traversal），广度优先遍历（Breadth-First Traversal）。其中深度遍历可以进一步细分为前序遍历、中序遍历和后序遍历，广度优先遍历又叫做层次遍历。

前序遍历

前序遍历，顾名思义就是指从根节点开始，每次先遍历节点本身，再遍历左右子树。具体实现可参考代码示例1。

// 前序遍历
public static void preOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.print(root.val + " ");
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}

中序遍历

中序遍历，就是指从根节点开始，先遍历左子树，然后遍历根节点本身，最后遍历右子树。具体实现可参考代码示例2。

// 中序遍历
public static void inOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrderTraversal(root.left);
    System.out.print(root.val + " ");
    inOrderTraversal(root.right);
}

后序遍历

后序遍历，就是指从根节点开始，先遍历左右子树，最后遍历根节点本身。具体实现可参考代码示例3。

// 后序遍历
public static void postOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    postOrderTraversal(root.left);
    postOrderTraversal(root.right);
    System.out.print(root.val + " ");
}

非递归遍历

上面的代码是采用递归方式实现的二叉树遍历，但是在实际开发中，递归方式也许并不是最优解。为了避免递归带来的栈溢出等问题，可以采用非递归方式遍历二叉树。具体实现方式可参考代码示例4、5和6。

// 前序遍历非递归实现
public static void preOrderTraversal2(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            System.out.print(cur.val + " ");
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        cur = cur.right;
    }
}

// 中序遍历非递归实现
public static void inOrderTraversal2(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        System.out.print(cur.val + " ");
        cur = cur.right;
    }
}

// 后序遍历非递归实现
public static void postOrderTraversal2(TreeNode root) {
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    TreeNode cur = root;
    stack1.push(cur);
    while (!stack1.isEmpty()) {
        cur = stack1.pop();
        stack2.push(cur);
        if (cur.left != null) {
            stack1.push(cur.left);
        }
        if (cur.right != null) {
            stack1.push(cur.right);
        }
    }
    while (!stack2.isEmpty()) {
        System.out.print(stack2.pop().val + " ");
    }
}

代码示例

代码示例1

public static void preOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.print(root.val + " ");
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}

代码示例2

public static void inOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrderTraversal(root.left);
    System.out.print(root.val + " ");
    inOrderTraversal(root.right);
}

代码示例3

public static void postOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    postOrderTraversal(root.left);
    postOrderTraversal(root.right);
    System.out.print(root.val + " ");
}

代码示例4

public static void preOrderTraversal2(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            System.out.print(cur.val + " ");
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        cur = cur.right;
    }
}

代码示例5

public static void inOrderTraversal2(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        System.out.print(cur.val + " ");
        cur = cur.right;
    }
}

代码示例6

public static void postOrderTraversal2(TreeNode root) {
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    TreeNode cur = root;
    stack1.push(cur);
    while (!stack1.isEmpty()) {
        cur = stack1.pop();
        stack2.push(cur);
        if (cur.left != null) {
            stack1.push(cur.left);
        }
        if (cur.right != null) {
            stack1.push(cur.right);
        }
    }
    while (!stack2.isEmpty()) {
        System.out.print(stack2.pop().val + " ");
    }
}