阅读 18

二叉树的前序&中序&后序&层序遍历

二叉树的遍历方式分为广度&深度遍历
  • 广度:层序遍历
  • 深度:前+中+后序遍历
二叉树数据结构
public class BinaryTree {
    public int val;
    public BinaryTree left = null;
    public BinaryTree right = null;
  	// 默认为没有遍历
    public boolean flag = false;
}
复制代码
宽度优先遍历:
  • 层序遍历:利用队列进行实现
    // 层序遍历--宽度优先遍历
    public static void layerOrder(BinaryTree head) {
        if (head == null) return;
        Queue<BinaryTree> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(head);
        while (!queue.isEmpty()) {
            BinaryTree cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
复制代码
深度优先遍历的递归实现:
    // 前序+递归实现
    public static void prePrint(BinaryTree head) {
        // 参数检查
        if (head == null) return;
        System.out.print(head.val + " ");
        prePrint(head.left);
        prePrint(head.right);
    }
    // 中序遍历 + 递归实现
    public static void middlePrint(BinaryTree head) {
        if (head == null) return;
        prePrint(head.left);
        System.out.print(head.val + " ");
        prePrint(head.right);
    }
    // 后序遍历 + 递归实现
    public static void endPrint(BinaryTree head) {
        if (head == null) return;
        prePrint(head.left);
        prePrint(head.right);
        System.out.print(head.val + " ");
    }
复制代码
深度优先遍历的非递归实现:递归的拆解
  • 前序非递归实现:

    	 public static void prePrint2(BinaryTree head) {
            if (head == null) return;
            // 辅助栈
            Stack<BinaryTree> stack1 = new Stack<>();
            BinaryTree cur = head;
            BinaryTree temp = null;
            // 左节点处理完之后, 再处理右节点
            while (true) {
                // 如果存在左节点, 则处理&入栈
                while (cur != null) {
                    System.out.print(cur.val + " ");
                    stack1.push(cur);
                    cur = cur.left;
                }
              	// 当队列为null的时候, 说明二叉树遍历完毕
                if (stack1.isEmpty()) break;
                // 处理右节点
                temp = stack1.pop();
                cur = temp.right;
            }
        }
    复制代码
  • 中序遍历非递归实现:与前序的处理方式有点不同

    • while (cur != null || !stack1.isEmpty())中的cur != null主要处理cur为非空节点的情况, 当cur = null的时候,!stack1.isEmpty()条件生效。
    • 那么时候cur = null ? 在上文定义的二叉树数据结构中,可以看出叶子节点的左右子树,都为null。
        public static void middlePrint2(BinaryTree head) {
            if (head == null) return;
            Stack<BinaryTree> stack1 = new Stack<>();
            BinaryTree cur = head;
            BinaryTree temp = null;
            // cur != null处理左节点, 遇到左节点则直接入栈
            // !stack1.isEmpty()处理右节点
            while (cur != null || !stack1.isEmpty()) {
                while (cur != null) {
                    stack1.push(cur);
                    cur = cur.left;
                }
                if (!stack1.isEmpty()) {
                    temp = stack1.pop();
                    System.out.print(temp.val + " ");
                    cur = temp.right;
                }
            }
        }
    复制代码
  • 后序遍历的非递归实现:借助遍历flag,标记当前节点cur的右子树是否被遍历过。

        public static void endPrint2(BinaryTree head) {
            if (head == null) return;
            Stack<BinaryTree> stack1 = new Stack<>();
            BinaryTree cur = head;
            BinaryTree temp = null;
            while (true) {
                while (cur != null) {
                    stack1.push(cur);
                    cur = cur.left;
                }
                if (!stack1.isEmpty()) break;
                // peek()并不弹出, 仅是获取栈顶的值。
                // 根据标志, 判断右子树是否已经处理
                temp = stack1.peek();
                if (!temp.flag) {
                    temp.flag = true;
                    // 处理右子树
                    cur = cur.right;
                } else {
                    temp = stack1.pop();
                    System.out.print(temp.val + " ");
                }
            }
        }
    复制代码