前言
在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。在学习和面试中，我们经常会遇到对二叉树的遍历，在此做一个总结：假设现在存在着一棵二叉树：（如下）
节点的结构
节点拥有值，左子节点和右子节点。
public class Node{
private int value;
private Node left;
private Node roght;
public Node(int value){
this.value = value;
}
public Node(int value, Node left, Node right){
this.value = value;
this.left = left;
this.right = right;
}
} 构建树
构建如图的一棵二叉树：
private static Node initTree(){
Node root = new Node(1);
Node node1 = new Node(2);
Node node2 = new Node(3);
Node node3 = new Node(4);
Node node4 = new Node(5);
Node node5 = new Node(6);
Node node6 = new Node(7);
Node node7 = new Node(8);
Node node8 = new Node(9);
Node node9 = new Node(10);
Node node10 = new Node(11);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
node3.left= node7;
node3.right = node8;
node4.left = node9;
node4.right = node10;
return root;
} 广度优先遍历（BFS）
其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。对于上面的例子来说，广度优先遍历的 结果是：1，2，3，4，5，6，7，8，9，10，11(假设每层节点从左到右访问)。我们可以通过使用队列这种数据结构来完成对二叉树的广度优先遍历。首先将根节点入队,某个节点出队时将其左右子节点入队，依次遍历。
public class TreeBFS{
public static void main(String[] args){
Node tree = initTree();
List<Integer> bfs = bfs(tree);
bfs.stream().forEach(System.out::println);
}
public static List<Integer> bfs(Node tree){
// 存储遍历的结果
List<Integer> list = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
// 如果根节点为空，直接返回空的list
if (tree == null){
return list;
}
// 根节点入队
queue.offer(tree);
// 当队列不为空时
while (!queue.isEmpty()) {
// 将队首的节点出队
Node poll = queue.poll();
// 如果该节点的左子节点不为空，则将其左子节点入队
if (poll.left != null) {
queue.offer(poll.left);
}
// 如果该节点的右子节点不为空，则将其右子节点入队
if (poll.right != null) {
queue.offer(poll.right);
}
// 将出队的节点的值保存到list中
list.add(poll.value);
}
// 返回遍历结果
return list;
}
} 深度优先遍历（DFS）
深度优先遍历与广度优先遍历截然相反，我们使用栈这种数据结构来遍历，首先从根节点向下寻找，我们将根节点入栈，再将其出栈，判断出栈元素的右子节点是否为空，如果为空，则将右子节点入栈，并继续判断左子节点是否为空，如果其左子节点不为空，则将左子节点入栈（此处先将右子节点入栈，后将左子节点入栈是为了在出栈时左子节点的遍历在右子节点之前），对其左右子节点判断完成后，再将栈顶的元素出栈，依次循环，直到栈为空，遍历结束。深度优先遍历的结果为：1，2，4，8，9，5，10，11，3，6，7
public class TreeDFS{
public static void main(String[] args){
Node tree = initTree();
List<Integer> dfs = dfs(tree);
dfs.stream().forEach(System.out::println);
}
public static List<Integer> bfs(Node tree){
// 存储遍历的结果
List<Integer> list = new ArrayList<>();
Stack<Node> stack = new Stack<>();
// 如果根节点为空，直接返回空的list
if (tree == null){
return list;
}
// 根节点入栈
stack.push(tree);
// 当栈不为空时
while (!stack.isEmpty()) {
// 将栈顶的元素出栈
Node pop = stack.pop();
// 如果该节点的右子节点不为空，则将其右子节点入栈
if (pop.right != null) {
stack.push(pop.right);
}
// 如果该节点的左子节点不为空，则将其左子节点入栈
if (pop.left!= null) {
stack.push(pop.left);
}
// 将出栈的节点的值保存到list中
list.add(pop.value);
}
// 返回遍历结果
return list;
}
} 先序遍历
递归实现
二叉树的先序遍历含义就是：首先二叉树的根节点，再遍历其左子节点和右子节点，对其左子节点和右子节点的遍历是类似的。先序遍历的结果为：1，2，4，8，9，5，10，11，3，6，7
public class TreeFirstOrder {
public static void main(String[] args) {
Node tree = initTree();
firstOrderWithRecursive(tree);
}
public static void firstOrderWithRecursive(Node tree){
if (tree != null) {
System.out.println(tree.value);
firstOrderWithRecursive(tree.left);
firstOrderWithRecursive(tree.right);
}
}
} 非递归实现
借用栈来实现，先序遍历和深度优先遍历很类似，都是先打印节点，再打印节点的左子节点，如果左子节点为空，则打印其右子节点，若左子节点不为空，依次向下寻找。
public static void firstOrder(Node tree){
// 此处的stack主要是用于回溯上一个节点
Stack<Node> stack = new Stack<>();
Node node = tree;
while (node != null || !stack.isEmpty()){
if (node != null){
System.out.println(node.value);
stack.push(node);
node = node.left;
} else {
Node temp = stack.pop();
node = temp.right;
}
}
}中序遍历
中序遍历就是先打印某个节点的左子节点，在打印该节点，最后打印其右子节点，依次类推。故可以使用递归进行实现。遍历结果为：8，4，9，2，10，5，11，1，6，3，7
递归实现
public static void midOrderWithRecursive(Node tree){
if (tree != null) {
midOrderWithRecursive(tree.left);
System.out.println(tree.value);
midOrderWithRecursive(tree.right);
}
} 非递归实现
借用栈来记录前一个节点
public static void midOrder(Node tree){
Stack<Node> stack = new Stack<>();
Node node = tree;
while (node != null || !stack.isEmpty()){
if (node != null){
stack.push(node);
node = node.left;
} else {
Node temp = stack.pop();
System.out.println(temp.value);
node = temp.right;
}
}
} 后序遍历
后序遍历就是先打印某个节点的左子节点，在打印其右子节点，最后打印该节点，其他节点以此类推，故也可以使用递归实现。遍历结果为：
递归实现
public static void afterOrderWithRecursive(Node tree){
if (tree != null) {
afterOrderWithRecursive(tree.left);
afterOrderWithRecursive(tree.right);
System.out.println(tree.value);
}
} 非递归实现
public static void afterOrder(Node tree){
Node cur, pre = null;
Stack<Node> stack = new Stack<>();
stack.push(tree);
while (!stack.isEmpty()){
cur = stack.peek();
if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))) {
System.out.println(cur.value);
stack.pop();
pre = cur;
} else {
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}
} 
京公网安备 11010502036488号