[数据结构与算法]二叉树和图的遍历算法详解

在正式介绍本文的内容之前，先回顾一下数据结构的分类情况，以便更好地理解树和图的遍历过程。

数据结构从逻辑上的线性关系来划分，可以分为线性表和非线性表两类。

所谓线性表，指的是数据在存放过程中符合一个接着一个的状态，如果把它画在纸上就像是一条具有一定线性关系的线段。纯粹的线性表结构包括数组和链表，在数组和链表的基础上又定义出了栈和队列，但它们本质上依然属于线性关系。

非线性表结构主要包括树和图，树结构在于一个节点下面挂着多个节点，以父子之间的上下节点关系形式存在，除了父子关系之外，一般不存在同级节点间的一些瓜葛。而图则可以看成是在树的基础上，各同级节点之间也产生了相互关联，甚至于任何两个节点间，不管远近关系如何，都可以产生联系，因此图更像是一个关系网密切的网状结构。此外，树结构重在节点，其节点内包含了数据和父/子指针等一切数据，而图结构除了节点外，边信息也是至关重要的。

除了这两种大的分类，还包括一些衍生出来的其他结构，比如堆结构可以看作是一个由数组或链表实现的二叉树，并查集可以看作是一个包含了节点集合的树等等。

由此可见，线性表可以看成是一对一的关系，树为一对多的关系，而图则是最为复杂的多对多关系。而之所以把树和图放在一起讲解，主要是因为它们都具有一对多的特点，那么在一定程度上，其遍历过程就都可以按照宽度优先和深度优先的形式去进行。

前置知识到此结束，下面正式开始我们的主角：树和图的遍历算法。

一、二叉树的遍历算法

1、二叉树的深度优先遍历

在二叉树中，所谓的深度优先遍历就是指我们熟悉的先序、中序和后序遍历，它们都是从根节点出发，向着树的深度方向扎下去做遍历操作，而这些遍历的实现，本质上都是递归调用的结果，因此这些遍历过程都可以通过在递归序上做不同时机的打印行为得到。
这里先上二叉树的节点结构：

	// binary tree node structure
	public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

(1) 递归序

递归序，顾名思义就是，一棵树上的所有节点在递归过程中如果被遍历到，就记录下来，最终递归过程结束每个节点被遍历的情况所呈现出来的序列，这一序列能够显示出整个递归过程的踪迹，也就是说，通过递归序，能看到递归过程是如何在节点间一步一步走完的。在递归序中，每个节点都会出现三次，即对应下方代码中的：
1位置：递归函数刚刚开始遍历树，假如当前传入树的节点是头节点head(不为空)，这时递归过程第一次遍历到它；
2位置：调用完head节点的左孩子后，递归过程会回到当前的head结点处；
3位置：调用完head节点的右孩子后，递归过程会再次回到当前节点。
经历过三次相遇，递归过程才完整地遍历完head节点。

	// recursive process
	public static void f(Node head) {
        if (head == null) {
            return;
        }
        // 1
        f(head.left);
        // 2
        f(head.right);
        // 3
    }

这里，只进行了递归过程，没有做打印处理。如果把1、2、3处都做打印处理，便能够显式地看到整个递归序的遍历结果。
举例说明：

(2) 先序遍历

先序遍历是在递归序的基础上，在刚来到以当前节点为头结点的位置时，就做打印操作，最终打印结果为：头-左-右。

	// pre-order recursive process
	public static void pre(Node head) {
        if (head == null) {
            return;
        }
        // 第一次遍历到当前节点就打印
        System.out.println(head.value);
        pre(head.left);
        pre(head.right);
    }

我们知道，对于任意一个递归行为，都可以用非递归操作来代替，所以这里我们把先序遍历的非递归版本也放在下面，以供参考：

	// pre-order non-recursive process
	public static void pre2(Node head) {
        if(head != null){
        	// 传入的节点不为空，就创建一个栈，把头节点压栈
        	Stack<Node> stack = new Stack<>();
        	stack.push(head);
        	// 只要栈不为空，就一直弹栈、打印、压栈
        	while(!stack.isEmpty){
        		// 把当前栈顶元素弹出
				Node cur = stack.pop();
				// 弹出即打印
				System.out.print(cur.value + " ");
				// 将当前弹出节点的右孩子、左孩子依次压栈
				// 这里是由于弹栈时会按照逆序来弹，因此要保证弹出顺序为左-右，压栈顺序就得是右-左
				if(cur.right != null){
					stack.push(cur.right);
				}
				if(cur.left != null){
					stack.push(cur.left);
				}
			}
        }
        System.out.println();
    }

(3) 中序遍历

中序遍历是在递归序的基础上，在调用完当前节点的左孩子时，才做打印操作，最终打印结果为：左-头-右。

	// in-order recursive process
	public static void in(Node head) {
        if (head == null) {
            return;
        }
        in(head.left);
        // 第二次遍历到当前节点才打印
        System.out.println(head.value);
        in(head.right);
    }

非递归版本实现：

	// in-order non-recursive process
	public static void in2(Node head) {
        if(head != null){
        	// 传入的节点不为空，就创建一个栈，把头节点压栈
        	Stack<Node> stack = new Stack<>();
        	stack.push(head);
        	// 只要当前节点存在左孩子或者栈不为空，就持续该循环
        	while(head.left != null || !stack.isEmpty){
        		// 如果当前节点的左孩子存在，就先把左孩子压栈，然后head来到左孩子处，再重新进入外层循环
        		// 也就是说，如果head节点有很多个左孩子，那这个过程就会一直把所有的左孩子压进去
				if(head.left != null){
					stack.push(head.left);
					head = head.left;
				}else{
					//如果进入当前条件，说明，当前节点head已经没有左孩子了，此时要把栈顶元素弹出并打印，然后去看cur有没有右孩子
					Node cur = stack.pop();
					// 弹出即打印
					System.out.print(cur.value + " ");
					// 如果cur节点有右孩子，就让head指向右孩子，然后head会重新进入外层循环，去看它所指的这个右孩子是否有左孩子
					// 如果有，就进行同样的压左孩子最后弹出打印并判断有无右孩子这一系列过程
					head = cur.right;
				}
			}
        }
        System.out.println();
    }

(4) 后序遍历

后序遍历是在递归序的基础上，在调用完当前节点的左孩子和后孩子后，才做打印操作，最终打印结果为：左-右-头。

	// pos-order recursive process
	public static void pos(Node head) {
        if (head == null) {
            return;
        }
        pos(head.left);
        pos(head.right);
        // 第三次遍历到当前节点才打印
        System.out.println(head.value);
    }

后序遍历的结果为左-右-头，我们观察到它的逆序为头-右-左，这和先序遍历的非递归版本非常相似，因此在后序遍历的非递归版本中，只需要对先序遍历非递归版本中的压栈过程调换顺序，先压左孩子，再压右孩子，便能得到头-右-左的遍历结果，再将这一结果压入一个新的栈，然后弹出，便能得到后序遍历的结果左-右-头。
非递归版本实现：

	// pos-order non-recursive process
	public static void pos2(Node head) {
        if(head != null){
        	// 传入的节点不为空，就创建一个栈，把头节点压栈
        	Stack<Node> stack = new Stack<>();
        	stack.push(head);
        	// 只要栈不为空，就一直循环下去
        	while(!stack.isEmpty){
        		// 把当前栈顶元素弹出
				Node cur = stack.pop();
				// 这里弹出不打印，而是把结果压入一个新的栈res中，等整个流程操作完，再把res中的元素依次弹出打印
				Stack<Node> res = new Stack<>();
				res.push(cur);
				// 将当前弹出节点的左孩子、右孩子依次压栈
				// 这里对先序遍历中的压栈顺序做了调换，先压左孩子，再压右孩子，由于便能得到弹出顺序右-左
				if(cur.left != null){
					stack.push(cur.left);
				}
				if(cur.right != null){
					stack.push(cur.right);
				}
			}
        }
        // 代码运行到这里，说明已经按照头-右-左的顺序把结果放进res中了，接下来把res中的元素依弹出打印
        while(!res.isEmpty()){
        	System.out.print(res.pop().value + " ");
        }
        System.out.println();
    }

2、二叉树的宽度优先遍历

所谓二叉树的宽度优先遍历，就是指二叉树的层序遍历过程。不同于前面几种深度优先的遍历方法的压栈操作，层序遍历是一层一层的扫描，只要某个节点先被扫描到，就先打印，所以对于层序来说，通常采用队列的结构来进行操作。

// level traversal binary tree
public static void level(Node head){
	if(head == null){
		return;
	}
	Queue<Node> queue = new Queue<>(); // 创建一个队列
	queue.add(head); // 将传进来的头结点入队
	while(!queue.isEmpty){ // 只要队列不为空，就一直弹出节点
		Node cur = queue.poll(); 
		System.out.print(cur.value + " "); // 出队即打印
		if(cur.left != null){
			queue.add(cur.left); // 如果左孩子不为空，就让左孩子入队
		}
		if(cur.right != null){
			queue.add(cur.right); // 如果右孩子不为空，就让右孩子入队
		}
	}
	System.out.println();
}

可以看出，层序遍历的过程代码和先序遍历非常相似，都是在节点被弹出时打印，也都是要依次把左右孩子压入。不同点在于，先序遍历使用栈结构，并且由于栈的先进后出，所以要先压右孩子，再压左孩子；而层序遍历则采用队列结构，因此先压左孩子，再压右孩子。

二、图的遍历算法

在遍历图之前，首先需要对一张图的整体结构有个了解，这里专门创建了一个万能的图结构，下面所介绍的遍历过程都是根据这张图结构来的。

这里也放上节点类Node的相关结构：

// Node class
public class Node {
    public int value; // 节点的值
    public int in; // 入度
    public int out; // 出度
    public ArrayList<Node> nexts; // 存放所有直接邻居
    public ArrayList<Edge> edges; // 存放由此节点出发往下的所有边

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

1、图的深度优先遍历

图的深度优先遍历通常被称为Depth First Search，即DFS。由于图有多条连通路，因此规定图的深度优先遍历过程为：沿着根节点的某一条路一直走下去，直到这个节点下方再也没有节点或者来到重复节点为止，然后回退去看当前节点的上一个节点是否有另一条通路，如果有就去这条通路遍历到底，如果没有就继续返回上一个节点去查看。直到把根节点下面所有节点的通路都走一遍，遍历过程才停止。对于深度优先遍历，通常采用栈来实现，为了防止出现重复遍历，还需要借助一个set注册表，在遍历时只有没注册过的节点才能入栈，如果表中已经存在该节点，就不做处理。具体实现如下：

// DFS
public void dfs(Node start){
	if(start == null){
		return;
	}
	Stack<Node> stack = new Stack<>(); // 用栈来实现深度优先遍历
	Set<Node> set=new HashSet<>(); // 用一张set表来表示当前节点是否被注册过
	stack.push(start);
	set.push(start); // 在往栈中压入新结点时，将其同步压入注册表中
	System.out.println(start.value); // 压入即打印
	while(!stack.isEmpty){
		Node cur = stack.pop();
		for(Node next : cur.nexts){ // 遍历当前被弹出节点的next节点们
			// 如果这些next节点没有被注册过，就执行下面的程序
			// 如果被注册过，就不执行
			if(!set.contains(next)){ 
				stack.push(cur); // 将弹出的节点再压回去
				stack.push(next); // 将next节点压栈
				set.push(next); // 将next节点注册上
				System.out.println(next.value); // 注册(压入)即打印
				//这里，只要有一个next节点压栈了 那其他的next节点就都不再继续遍历了 回到循环最上面 去弹出节点
				break;
			}
		}
	}
}

需要注意的是，在DFS中，只要压入了新节点就打印，而且在压入新节点之前，还需要把它的父节点重新压回栈中去，如此一来，相当于栈中每时每刻都保留了当前的整个遍历路径。此外，在遍历当前节点的直接邻居时，是只遍历其中的一个，把他压栈之后就立即停止，然后弹出当前压入的节点，去看顺着他是否还能找到更深一层的节点，这个处理过程是深度优先遍历的特征所在。

2、图的宽度优先遍历

图的宽度优先遍历算法又叫广度优先算法 Breadth First Search，简称BFS。宽度优先遍历是在遍历的过程中，只要某一个节点有直接邻居，就先把它的所有直接邻居遍历完，然后再依次遍历这些直接邻居的直接邻居，类似于二叉树的层序遍历过程。在进行宽度优先遍历的时候，通常需要用到队列结构，保证先遍历到的先弹出打印，另外和深度优先遍历一样，依然需要一个注册表set，来保证不会出现重复遍历的情况。具体过程如下：

// BFS
public void bfs(Node start){
	if(start == null){
		return;
	}
	Queue<Node> queue = new Queue<>(); // 准备一个队列
	HashSet<Node> set = new HashSet<>(); // 准备一个注册表
	queue.add(start);
	set.add(start);
	while(!queue.isEmpty){
		Node cur = queue.poll(); // 只要队列不空，就一直往外弹
		System.out.println(cur.value); // 弹出即打印
		for(Node next : cur.nexts){ // 遍历当前弹出节点的直接邻居
			if(!set.contains(next)){ // 如果直接邻居没有被注册过
				queue.add(next); // 就将邻居放进队列
				set.add(next); // 放进队列后在set中注册上
			}
		}
	}
}

相比图的深度优先遍历，其宽度优先遍历同样要借助一张注册表来防止重复遍历的问题，这是图结构本身各节点间相同联通的属性所造成的。但不同点在于，首先宽度优先不是采用栈结构，而是采用队列的方式，再者宽度优先也并不是只遍历当前节点的某一个直接邻居就停止，然后往下去找更深层次的节点。与之相反，宽度优先要先找到当前节点的所有直接邻居，而后才往下去找。

另外，相比二叉树的层序遍历来说，图的宽度优先基本上与树的层序相一致，都要用队列来实现，也都要先把相同层次的节点处理完了才去处理下一层的节点。两者的区别在于，二叉树只有两个叉，并且各相同层次的节点间不构成联通关系，而图相当于是多叉树并且同一层次甚至任意层次的节点间都能相互联通在一起，所以树只需要关注左右两个孩子，而图需要关注所有的直接邻居；另外为了遍历的节点不重复，图还需要用一张注册表来过滤重复节点。