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

二叉树的遍历方式分为广度&深度遍历

• 广度：层序遍历
• 深度：前+中+后序遍历

二叉树数据结构

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 + " ");
              }
          }
      }