java二叉树的非递归遍历

下面我详细讲解一下Java二叉树的非递归遍历的完整攻略。

1. 什么是二叉树？

二叉树(Binary Tree)是一种树型的数据结构，它的每个节点最多只有两个子节点，分别称为左子节点和右子节点。

2. 如何遍历二叉树？

二叉树的遍历有三种方式：前序遍历、中序遍历和后序遍历。

• 前序遍历：先访问根节点，再遍历左子树和右子树。
• 中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。
• 后序遍历：先遍历左子树，再遍历右子树，最后访问根节点。

3. 非递归遍历的思路

非递归遍历深度优先二叉树有两种经典的做法，一种是使用栈来模拟递归过程；另一种是使用线索二叉树的方式来遍历。下面分别进行讲解。

3.1 使用栈来模拟递归过程

采用栈来模拟递归遍历，算法思路如下：

1. 如果当前节点不为空，入栈并将当前节点更新为左子节点，再次判断是否为空。
2. 如果当前节点为空且栈非空，则出栈，并访问出栈节点的右子节点。
3. 重复执行1、2步，直到栈为空。

以下为Java代码示例，实现二叉树的前序、中序、后序非递归遍历。

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BinaryTreeTraversal {
    // 前序遍历
    public static void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        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) {
        if (root == null) {
            return;
        }
        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 postOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);
            if (node.left != null) {
                stack1.push(node.left);
            }
            if (node.right != null) {
                stack1.push(node.right);
            }
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().val + " ");
        }
    }
}

3.2 使用线索二叉树的方式来遍历

线索二叉树是对二叉树进行了改进，把有右孩子的节点的右孩子指针变成指向后继节点，有左孩子的节点的左孩子指针变成指向前驱节点。这样就可以避免使用栈来模拟递归，从而实现二叉树的非递归遍历。

以下是Java代码示例，实现二叉树的中序非递归遍历。

public class ThreadedBinaryTreeTraversal {
    static class ThreadedNode {
        int val;
        ThreadedNode left;
        ThreadedNode right;
        boolean isLeftThread;
        boolean isRightThread;

        ThreadedNode(int val) {
            this.val = val;
            this.isLeftThread = false;
            this.isRightThread = false;
        }
    }

    static ThreadedNode pre = null;

    // 构建线索二叉树
    public static void inOrderThread(ThreadedNode node) {
        if (node == null) {
            return;
        }
        inOrderThread(node.left);
        if (node.left == null) {
            node.left = pre;
            node.isLeftThread = true;
        }
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.isRightThread = true;
        }
        pre = node;
        inOrderThread(node.right);
    }

    // 中序遍历
    public static void inOrderTraversal(ThreadedNode root) {
        ThreadedNode node = root;
        while (node != null) {
            while (!node.isLeftThread && node.left != null) {
                node = node.left;
            }
            System.out.print(node.val + " ");
            while (node.isRightThread) {
                node = node.right;
                System.out.print(node.val + " ");
            }
            node = node.right;
        }
    }

    public static void main(String[] args) {
        ThreadedNode root = new ThreadedNode(1);
        root.left = new ThreadedNode(2);
        root.right = new ThreadedNode(3);
        root.left.left = new ThreadedNode(4);
        root.left.right = new ThreadedNode(5);
        root.right.left = new ThreadedNode(6);
        root.right.right = new ThreadedNode(7);

        inOrderThread(root);
        inOrderTraversal(root);
    }
}

4. 总结

Java二叉树的非递归遍历，可以使用栈来模拟递归过程，也可以采用线索二叉树的方式来实现，两种方式相较于递归遍历，更节省空间，提高效率。其中，栈模拟递归方式适用于前序、中序和后序遍历，线索二叉树方式适用于中序遍历。