Java语言实现非递归实现树的前中后序遍历总结

为什么要用非递归实现树的遍历？

树的遍历可以使用递归实现，但是递归实现有可能导致栈溢出的问题，尤其是当树的层数比较深时。因此，使用非递归实现树的遍历可以避免这个问题。

非递归实现树的前序遍历

前序遍历的顺序是：根节点 --> 左子树 --> 右子树

public void preorder(Node root) {
    if (root == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        visit(node);
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

非递归实现树的中序遍历

中序遍历的顺序是：左子树 --> 根节点 --> 右子树

public void inorder(Node root) {
    if (root == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    Node node = root;
    while (node != null || !stack.isEmpty()) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            visit(node);
            node = node.right;
        }
    }
}

非递归实现树的后序遍历

后序遍历的顺序是：左子树 --> 右子树 --> 根节点

public void postorder(Node root) {
    if (root == null) {
        return;
    }
    Stack<Node> stack1 = new Stack<>();
    Stack<Node> stack2 = new Stack<>();
    stack1.push(root);
    while (!stack1.isEmpty()) {
        Node 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()) {
        Node node = stack2.pop();
        visit(node);
    }
}

示例说明

假设有如下一棵二叉树：

    1
   / \
  2   3
 / \   \
4   5   6

使用以上三个方法进行遍历的结果分别为：

前序遍历：1 2 4 5 3 6

中序遍历：4 2 5 1 3 6

后序遍历：4 5 2 6 3 1