【算法】二叉树的先序，中序，后序，层级遍历---MapleYe

1、二叉树

一个树最多只有左孩子和右孩子的树，叫做二叉树。其结构为：

public static class Node { public Node left; public Node right; public int value; public Node(int data) { value = data; } }2、先序，中序，后序递归版本

对于二叉树先序，中序，后序遍历，其递归版本都非常相似，唯一区别就是打印的时机。因此根据打印时机分为先序，中序，后序。

先序遍历 /// 先序遍历，递归版本 public static void preOrder1(Node head) { if (head == null) { return; } System.out.print(head.value + " "); preOrder1(head.left); preOrder1(head.right); }中序遍历 /// 中序遍历，递归版本 public static void inOrder1(Node head) { if (head == null) { return; } inOrder1(head.left); System.out.print(head.value + " "); inOrder1(head.right); }后序遍历 /// 后序遍历，递归版本 public static void posOrder1(Node head) { if (head == null) { return; } posOrder1(head.left); posOrder1(head.right); System.out.print(head.value + " "); }3、先序，中序，后序非递归版本先序遍历

为了实现非递归，我们需要通过栈来辅助，模拟栈的操作。由于先序遍历的顺序是，先中，再左，再右。那么我们对于每一个节点，先打印其节点，然后压入右子树，再压入左子树，就可以实现先中，再左，再右的顺序。

代码实现：

/// 先序遍历，非递归 public static void preOrder2(Node head) { Stack<Node> stack = new Stack<Node>(); if(head != null) { // 先打印，再入栈 stack.push(head); while(!stack.isEmpty()) { // 模拟系统栈操作 head = stack.pop(); System.out.print(head.value + " "); // 由于是先遍历左子树，因此入栈顺序是先右，再左 if (head.right != null) { stack.push(head.right); } if (head.left != null) { stack.push(head.left); } } } }中序遍历

同样地，我们需要一个栈辅助。由于中序遍历的打印顺序是先左，再中，再右。因此，我们需要先将一个节点的左子树全部入栈后，取出栈顶节点打印后，再将该节点的右子树入栈。

代码实现:

/// 中序遍历，非递归 public static void inOrder2(Node head) { Stack<Node> stack = new Stack<Node>(); if (head != null) { while(!stack.isEmpty() || head != null) { // 先压左子树 if (head != null) { stack.push(head); head = head.left; }else { // 左子树压完后，就打印栈顶元素，然后压右子树 head = stack.pop(); System.out.print(head.value + " "); head = head.right; } } } }后序遍历

后序遍历的非递归版本的有许多实现方法，有标记该树的入栈次数等方法。但最简单的方法是通过两个栈的方式，我们知道后序遍历的顺序是 左右中，那么我们先实现一个改进的先序遍历，其顺序是 中右左，然后将打印操作改为入栈操作。待以中右左的打印的节点全部入栈后，一一出栈，就实现了 左右中的后序遍历了。

代码如下：

/// 后序遍历，非递归 public static void posOrder2(Node head) { if (head != null) { // 由于后续遍历的顺序是 左右打印，因此构造一个先序遍历（打印右左） // 的非递归版，然后通过栈2逆序输出即可得到 左右打印 的顺序 Stack<Node> s1 = new Stack<Node>(); Stack<Node> s2 = new Stack<Node>(); s1.push(head); while (!s1.isEmpty()) { head = s1.pop(); s2.push(head); if (head.left != null) { s1.push(head.left); } if (head.right != null) { s1.push(head.right); } } while(!s2.isEmpty()) { System.out.print(s2.pop().value + " "); } } }4、层级遍历

层级遍历就是从根节点开始逐层打印。因此，每打印一个节点，我们都要对其左孩子，右孩子进行打印，那么我们可以通过队实现层次遍历

代码如下:

/// 层级遍历 public static void levelOrder(Node head) { if (head == null) { return; } Queue<Node> queue = new LinkedList<Node>(); queue.offer(head); System.out.print(head.value + " "); while(!queue.isEmpty()) { head = queue.poll(); if (head.left != null) { System.out.print(head.left.value + " "); queue.offer(head.left); } if (head.right != null) { System.out.print(head.right.value + " "); queue.offer(head.right); } } } ---来自腾讯云社区的---MapleYe