二叉树的非递归遍历

二叉树的非递归遍历也是采用的是递归的思想，拿前序遍历为例：先通过找到最左下角的节点，然后将其输出，并且对此节点的右子树再进行下一步的操作。代码如下

前序遍历：

 public void pre_iteration(Node p) {
        if (p == null) return;
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                System.out.println(p.val);
                stack.push(p);
                p = p.left;
            }
            if (!stack.isEmpty()) {
                p = stack.pop();
                p = p.right;
            }
        }
    }

中序遍历：

public void in_iteration(Node p) {
        if (p == null) return;
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            if (!stack.isEmpty()) {
                p = stack.pop();
                System.out.println(p.val);
                p = p.right;
            }
        }
    }

后序遍历：（stack2是用来记载当前节点的右子树是否已经被遍历过）

public static void post_iteration(Node p) {
        if (p == null) return;
        Stack<Node> stack = new Stack<>();
        Stack<Boolean> stack2 = new Stack<>();
        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                stack.push(p);
                stack2.push(false);
                p = p.left;
            }
            while (!stack.isEmpty() && stack2.peek()) {
                System.out.println(stack.pop().val);
                stack2.pop();
            }
            if (!stack.isEmpty()) {
                p = stack.peek().right;
                stack2.pop();
                stack2.push(true);
            }
        }
    }

JAVA学习网

分类

二叉树的非递归遍历