二叉树的遍历

遍历二叉树一共有四种方式：前序遍历，中序遍历，后序遍历，层序遍历（广度优先）

准备

先定义一个结点类（后续代码需要使用）

public class Node { public V value; public Node left; public Node right; public Node(V value) { this.value = value; }}

一 、前序遍历

操作步骤如下：

1. 访问根结点

2. 递归遍历左子树

3. 递归遍历右子树

假设一个二叉树的结构如下图所示：

则遍历结果为：1 2 4 5 3 6

实现方式：

* 递归方式

public class PreOrderRecursivelyVisitor { public void visit(Node root) { if (root == null) { return; } System.out.println(node.value + " "); visit(root.left, output); visit(root.right, output); }}

* 非递归方式

借助栈（先进后出）来实现

代码如下：

public class PreOrderVisitor { public void visit(Node root) { if (root == null) { return; } Stack help = new Stack(); // 1. 根结点入栈 help.push(root); while (!help.isEmpty()) { // 2. 栈顶结点出栈 Node node = help.pop(); // 3. 访问出栈结点 System.out.println(node.value + " "); // 4. 依次将该结点的右，左孩子入栈 if (node.right != null) { help.push(node.right); } if (node.left != null) { help.push(node.left); } } }}

二、中序遍历

操作步骤如下：

1. 递归遍历左子树

2. 访问根结点

3. 递归遍历右子树

假设一个二叉树的结构如下图所示：

则遍历结果为：4 2 5 1 3 6

实现方式：

* 递归方式

public class InOrderRecursivelyVisitor { public void visit(Node root) { if (root == null) { return; } visit(root.left, output); System.out.println(node.value + " "); visit(root.right, output); }}

* 非递归方式

public class InOrderVisitor { public void visit(Node root) { if (root == null) { return; } Stack help = new Stack(); // 定义一个当前结点遍历并指向根结点 Node current = root; while (current != null || !help.isEmpty()) { if (current != null) { // 若当前结点不为空，则入栈 help.push(current); // 将当前结点指向该结点的左孩子 current = current.left; } else { // 若当前结点为空（即当前已经没有可访问的左子树了），则出栈 current = help.pop(); // 访问出栈结点 System.out.println(current.value + " "); // 将当前结点指向出栈结点的右孩子 current = current.right; // （若该结点存在，则重复执行上面的if分支将该结点的左子树依次入栈） } } }}

三、后序遍历

操作步骤如下：

1. 递归遍历左子树

2. 递归遍历右子树

3. 访问根结点

假设一个二叉树的结构如下图所示：

则遍历结果为：4 5 2 6 3 1

实现方式：

* 递归方式

public class PostOrderRecursivelyVisitor { public void visit(Node root) { if (root == null) { return; } visit(root.left, output); visit(root.right, output); System.out.println(node.value + " "); }}

* 非递归方式

这种方式稍微复杂一点，因为要先遍历完左右子树，再访问根结点，所以需要知道左右子树的访问状态。

public class PostOrderVisitor { public void visit(Node root) { if (root == null) { return; } Stack help = new Stack(); // 根结点入栈 help.push(root); // top指向栈顶元素 Node top = null; // visited表示刚刚访问过的结点（初始指向根结点） Node visited = root; while (!help.isEmpty()) { // 获取栈顶元素，但是不进行出栈操作 top = help.peek(); if (top.left != null && top.left != visited && top.right != visited) { // 若栈顶元素的左孩子结点存在，且左右孩子都未被访问过，则左孩子入栈 help.push(top.left); } else if (top.right != null && top.right != visited) { // 若栈顶元素的右孩子结点存在，且右孩子未被访问过，则右孩子入栈 help.push(top.right); } else { // 栈顶元素出栈，并访问该结点 System.out.println(help.pop().value + " "); // 记录已访问过的结点 visited = top; } } }}

四、层序遍历

也可称为广度优先遍历

操作步骤如下：

从上往下，从左至右依次访问每层的结点

假设一个二叉树的结构如下图所示：

则遍历结果为：1 2 3 4 5 6

实现方式：

借助队列（先进先出）来实现

代码如下：

public class LevelOrderVisitor { public void visit(Node root) { if (root == null) { return; } Queue queue = new LinkedList(); // 根结点进入队尾 queue.offer(root); while (!queue.isEmpty()) { // 出队列 Node node = queue.poll(); // 访问该结点 System.out.println(node.value + " "); // 依次将该结点的左右孩子入队列 if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } }}

以上就是遍历二叉树的几种方式。如有错误，请指正，谢谢。