二叉树之遍历

二叉树遍历

遍历分类

遍历二叉树的思路有 4 种，分别是：

• 前序遍历二叉树，有递归和非递归两种方式；
• 中序遍历二叉树，有递归和非递归两种方式；
• 后序遍历二叉树，有递归和非递归两种方式；
• 层次遍历二叉树

前序遍历

流程描述

所谓前序遍历二叉树，指的是从根结点出发，按照以下步骤访问二叉树的每个结点：

1. 访问当前结点；
2. 进入当前结点的左子树，以同样的步骤遍历左子树中的结点；
3. 遍历完当前结点的左子树后，再进入它的右子树，以同样的步骤遍历右子树中的结点；

举个简单的例子，下图是一棵二叉树：

前序遍历这棵二叉树的过程是：

访问根节点 1；
进入 1 的左子树，执行同样的步骤：访问结点 2；进入 2 的左子树，执行同样的步骤：访问结点 4；结点 4 没有左子树；结点 4 没有右子树；进入 2 的右子树，执行同样的步骤：访问结点 5；结点 5 没有左子树；结点 5 没有右子树；
进入 1 的右子树，执行同样的步骤：访问结点 3；进入 3 的左子树，执行同样的步骤：访问结点 6；结点 6 没有左子树；结点 6 没有右子树；进入 3 的右子树，执行同样的步骤：访问结点 7；结点 7 没有左子树；结点 7 没有右子树； 

经过以上过程，就访问了二叉树中的各个结点，访问的次序是：

1 2 4 5 3 6 7

代码实现

/*** 前序遍历- 递归实现* 访问当前结点；* 进入当前结点的左子树，以同样的步骤遍历左子树中的结点；* 遍历完当前结点的左子树后，再进入它的右子树，以同样的步骤遍历右子树中的结点；* @param treeNode*/public static void preTraverseForRecursion(TreeNode treeNode){if (treeNode != null){// 访问当前节点printTreeNode(treeNode);// 访问当前节点的左子节点preTraverseForRecursion(treeNode.left);// 访问当前节点的右子节点preTraverseForRecursion(treeNode.right);}}/*** 前序遍历- 非递归实现* 众所周知：递归实现无非是使用了栈结构来实现的，压栈，出栈，所以非是递归实现前序遍历就是自己实现栈* 访问当前结点；* 进入当前结点的左子树，以同样的步骤遍历左子树中的结点；* 遍历完当前结点的左子树后，再进入它的右子树，以同样的步骤遍历右子树中的结点；* @param treeNode*/public static void preTraverseForNoRecursion(TreeNode treeNode){TreeNode curr = treeNode;TreeNodeStack stack = new TreeNodeStack();while (curr != null || !stack.isEmpty()){if (curr != null){// 访问当前节点printTreeNode(curr);stack.push(curr);curr = curr.left;}else {TreeNode pop = stack.pop();curr = pop.right;}}}

/*** 树节点栈*/
@Data
public class TreeNodeStack {private int top = -1;private TreeNode[] stack = new TreeNode[10];public boolean isEmpty(){return top < 0;}/*** 入栈* @param treeNode*/public void push(TreeNode treeNode){top++;stack[top] = treeNode;}/*** 出栈* @return*/public TreeNode pop(){if (top < 0){return null;}TreeNode treeNode = stack[top];top--;return treeNode;}
}

中序遍历

流程描述

二叉树的中序遍历，指的是从根结点出发，按照以下步骤访问二叉树中的每个结点：

1. 先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；
2. 访问当前结点；
3. 最后进入当前结点的右子树，以同样的步骤遍历右子树中的结点。

中序遍历这棵二叉树的过程是：

进入结点 1 的左子树，访问左子树中的结点；进入结点 2 的左子树，访问左子树中的结点；试图进入结点 4 的左子树，但该结点没有左子树；访问结点 4；试图进入结点 4 的右子树，但该结点没有右子树；访问结点 2；进入结点 2 的右子树，访问右子树中的结点；试图进入结点 5 的左子树，但该结点没有左子树；访问结点 5；试图进入结点 5 的右子树，但该结点没有右子树；
访问结点 1；
进入结点 1 的右子树，访问右子树中的结点；进入结点 3 的左子树，访问左子树中的结点；试图进入结点 6 的左子树，但该结点没有左子树；访问结点 6；试图进入结点 6 的右子树，但该结点没有右子树；访问结点 3；进入结点 3 的右子树，访问右子树中的结点；试图进入结点 7 的左子树，但该结点没有左子树；访问结点 7；试图进入结点 7 的右子树，但该结点没有右子树；

最终，中序遍历图 1 中的二叉树，访问各个结点的顺序是：

4 2 5 1 6 3 7

代码实现

/*** 中序遍历-递归实现* 二叉树的中序遍历，指的是从根结点出发，按照以下步骤访问二叉树中的每个结点：* 1. 先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；* 2. 访问当前结点；* 3. 最后进入当前结点的右子树，以同样的步骤遍历右子树中的结点。* @param treeNode*/public static void inTraverseForRecursion(TreeNode treeNode){if (treeNode != null){// 递归-当问当前节点的左子节点inTraverseForRecursion(treeNode.left);// 访问当前节点printTreeNode(treeNode);// 递归-访问当前节点的右子节点inTraverseForRecursion(treeNode.right);}}/*** 中序遍历-非递归实现* 二叉树的中序遍历，指的是从根结点出发，按照以下步骤访问二叉树中的每个结点：* 1. 先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；* 2. 访问当前结点；* 3. 最后进入当前结点的右子树，以同样的步骤遍历右子树中的结点。* @param treeNode*/public static void inTraverseForNoRecursion(TreeNode treeNode){TreeNode curr = treeNode;TreeNodeStack stack = new TreeNodeStack();while (curr != null || !stack.isEmpty()){if (curr != null){// 入栈顺序：1, 2, 4,stack.push(curr);curr = curr.left;}else {// 出栈顺序：4， 2， 1TreeNode pop = stack.pop();printTreeNode(pop);// 然后访问右节点curr = pop.right;}}}

后序遍历

流程描述

后序遍历二叉树，指的是从根结点出发，按照以下步骤访问树中的每个结点：

1. 优先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；
2. 如果当前结点没有左子树，则进入它的右子树，以同样的步骤遍历右子树中的结点；
3. 直到当前结点的左子树和右子树都遍历完后，才访问该结点。

以下图所示的二叉树为例：

后序遍历这棵二叉树的过程是：

从根节点 1 出发，进入该结点的左子树；进入结点 2 的左子树，遍历左子树中的结点：进入结点 4 的左子树，但该结点没有左孩子；进入结点 4 的右子树，但该结点没有右子树；访问结点 4；进入结点 2 的右子树，遍历右子树中的结点：进入结点 5 的左子树，但该结点没有左孩子；进入结点 5 的右子树，但该结点没有右孩子；访问结点 5；访问结点 2；
进入结点 1 的右子树，遍历右子树中的结点：进入结点 3 的左子树，遍历左子树中的结点：进入结点 6 的左子树，但该结点没有左孩子；进入结点 6 的右子树，但该结点没有右子树；访问结点 6；进入结点 3 的右子树，遍历右子树中的结点：进入结点 7 的左子树，但该结点没有左孩子；进入结点 7 的右子树，但该结点没有右孩子；访问结点 7；访问结点 3；
访问结点 1。

最终，后序遍历图 1 中的二叉树，访问各个结点的顺序是：

4 5 2 6 7 3 1

代码实现

 /*** 后序遍历-递归实现* 后序遍历二叉树，指的是从根结点出发，按照以下步骤访问树中的每个结点：* 1. 优先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；* 2. 如果当前结点没有左子树，则进入它的右子树，以同样的步骤遍历右子树中的结点；* 3. 直到当前结点的左子树和右子树都遍历完后，才访问该结点。* @param treeNode*/public static void postTraverseForRecursion(TreeNode treeNode){if (treeNode != null){// 递归-当问当前节点的左子节点postTraverseForRecursion(treeNode.left);// 递归-访问当前节点的右子节点postTraverseForRecursion(treeNode.right);// 访问当前节点printTreeNode(treeNode);}}/*** 后序遍历-非递归实现* 后序遍历二叉树，指的是从根结点出发，按照以下步骤访问树中的每个结点：* 1. 优先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；* 2. 如果当前结点没有左子树，则进入它的右子树，以同样的步骤遍历右子树中的结点；* 3. 直到当前结点的左子树和右子树都遍历完后，才访问该结点。** 4, 5, 2, 6, 7, 3, 1* @param treeNode*/public static void postTraverseForNoRecursion(TreeNode treeNode){TreeNode curr = treeNode;LinkedList<TreeNode> stack = new LinkedList<>();// 定义最后一次出栈节点，防止陷入重复执行TreeNode pop = null;while (curr != null || !stack.isEmpty()){if (curr != null){stack.push(curr);curr = curr.left;}else {// peek方法是查询栈顶数据，但是不弹出TreeNode last = stack.peek();// last.right == pop 如果相等，那就说明已经执行过该右子节点了，这个条件是防止有右子节点的数据陷入死循环中if (last.right == null || last.right == pop){pop = stack.pop();printTreeNode(pop);}else {curr = last.right;}}}}

层次遍历

流程描述

上面这棵树一共有 3 层，根结点位于第一层，以此类推。

所谓层次遍历二叉树，就是从树的根结点开始，一层一层按照从左往右的次序依次访问树中的结点。

层次遍历用阻塞队列存储的二叉树，可以借助队列存储结构实现，具体方案是：

1. 将根结点入队；
2. 从队列的头部提取一个结点并访问它，将该结点的左孩子和右孩子依次入队；
3. 重复执行第 2 步，直至队列为空；

假设将图 1 中的二叉树存储到链表中，那么层次遍历的过程是：

根结点 1 入队（1）；
根结点 1 出队并访问它，然后将 1 的左孩子 2 和右孩子 3 依次入队（3, 2）；
将结点 2 出队并访问它，然后将 2 的左孩子 4 和右孩子 5 依次入队（5,4,3）；
将结点 3 出队并访问它，然后将 3 的左孩子 6 和右孩子 7 依次入队（7,6,5,4）；
根结点 4 出队并访问它，然后将 4 的左孩子（无）和右孩子（无）依次入队（7,6,5）；
将结点 5 出队并访问它，然后将 5 的左孩子（无）和右孩子（无）依次入队（7,6）；
将结点 6 出队并访问它，然后将 6 的左孩子（无）和右孩子（无）依次入队（7）；  
将结点 7 出队并访问它，然后将 6 的左孩子（无）和右孩子（无）依次入队（）；
队列为空，层次遍历结束

最终，后序遍历图 1 中的二叉树，访问各个结点的顺序是：

1 2 3 4 5 6 7

代码实现

 /*** 层次遍历* 所谓层次遍历二叉树，就是从树的根结点开始，一层一层按照从左往右的次序依次访问树中的结点。* 1. 将根结点入队；* 2. 从队列的头部提取一个结点并访问它，将该结点的左孩子和右孩子依次入队；* 3. 重复执行第 2 步，直至队列为空；* @param treeNode*/public static void levelTraverseForRecursion(TreeNode treeNode){if (treeNode != null){LinkedBlockingQueue<TreeNode> queue = new LinkedBlockingQueue<>(10);queue.offer(treeNode);doPushQueue(queue);}}/*** 使用阻塞队列实现二叉树层次遍历* 阻塞队列的特点就是先进先出* @param nowQueue*/private static void doPushQueue(LinkedBlockingQueue<TreeNode> nowQueue){if (nowQueue.isEmpty()){return;}// 从阻塞队列中弹出TreeNode poll = nowQueue.poll();while (poll != null){printTreeNode(poll);// 如果左子节点不为null, 则入队列if (poll.left != null){nowQueue.offer(poll.left);}// 如果右子节点不为null, 则入队列if (poll.right != null){nowQueue.offer(poll.right);}// 从阻塞队列中弹出poll = nowQueue.poll();}}

总结

总结各个遍历类型的流程

前序遍历：根节点 - 左节点 - 右节点
中序遍历：左节点 - 根节点 - 右节点
后序遍历：左节点 - 右节点 - 根节点
层次遍历：从根节点开始一层一层的遍历（左节点-右节点）