如何遍历一棵二叉树？

二叉树的遍历分为前序遍历、中序遍历、后序遍历和层次遍历。本文将详细梳理这四种二叉树的遍历方法。

我们给定一棵二叉树，结构如下：

先给出二叉树的数据结构：

class TreeNode
{
	public TreeNode(string value)
	{
		Value = value;
	}
	public string Value;
	public TreeNode Left;
	public TreeNode Right;
}

然后构建出如上图所示的二叉树：

var node = new TreeNode("A");
node.Left = new TreeNode("B");
node.Right = new TreeNode("F");

node.Left.Left = new TreeNode("C");
node.Left.Right = new TreeNode("D");
node.Left.Right.Left = new TreeNode("E");

node.Right.Left = new TreeNode("G");
node.Right.Right = new TreeNode("I");
node.Right.Left.Left = new TreeNode("H");

先序遍历、中序遍历、后序遍历代码如下：

public void Traverse(TreeNode treeNode)
{
	if (treeNode == null) return;
	//Console.Write(treeNode.Value + " ");先序遍历
	Traverse(treeNode.Left);
	//Console.Write(treeNode.Value + " ");//中序遍历
	Traverse(treeNode.Right);
	//Console.Write(treeNode.Value + " "); 后续遍历
}

可以看到，前中后序遍历的区别在于在哪个地方使用node。我在学习二叉树的遍历时这地方着实让我困惑了一会儿，其实主要还是对递归思维的理解不够透彻。

我们结合文初给出的二叉树，当第一次调用Traverse(A)时，treeNode !=null，调用Traverse(B)，在调用Traverse(B)之前，需要把Traverse(A)压栈，以便Traverse(B)返回时继续执行Traverse(A)。以此类推，在执行Traverse(C)的时候把Traverse(B)压栈，在执行Traverse(C.Left)时把Traverse(C)压栈。此时栈内地结构如下：

栈底	操作
traverse(A)	执行traverse(B)，压栈
traverse(B)	执行traverse(C)
traverse(C)	执行traverse(C.Ledt)

因为C.Left==null,Traverse(C.Left);返回，弹出traverse(C)，执行Traverse(C.Right)，C.Right == null，又返回，此时把traverse(B)弹出来，执行traverse(B.Right)，也就是traverse(D)，此时又要把traverse(B)压进去，依次递归，压栈和弹栈顺序如下：

栈底	操作	先序	中序	后续
	执行traverse(A)	A
traverse(A)	执行traverse(A.Left = B)，压栈A，栈内A	B
traverse(B)	执行traverse(B.Left = C)，压栈B，栈内A-B	C
traverse(C)	执行traverse(C.Ledt = null)，压栈C，栈内A-B-C
traverse(C)	traverse(C.Left = null)返回，弹栈C，栈内A-B		C
traverse(C)	执行traverse(C.Right = null)，压栈C，栈内A-B-C
traverse(C)	traverse(C.Right = null )返回，弹栈C，栈内A-B			C
traverse(B)	traverse(B.Left= C)返回，弹栈B，栈内A		B
traverse(B)	执行traverse(B.Right = D)，压栈B，栈内A-B	D
traverse(D)	执行traverse(D.Left = E)，压栈D，栈内A-B-D	E
traverse(E)	执行traverse(E.Left = null)，压栈E，栈内A-B-D-E
traverse(E)	traverse(E.Left = null)返回，弹栈E，栈内A-B-D		E
traverse(E)	执行traverse(E.Right = null)，压栈E，栈内A-B-D-E
traverse(E)	traverse(E.Right = null)返回，弹栈E，栈内A-B-D			E
traverse(D)	traverse(D.Left = E)返回，弹栈D，栈内A-B		D
traverse(D)	执行traverse(D.Right = null)，压栈D，栈内A-B-D
traverse(D)	traverse((D.Right = null)返回，弹栈D，栈内A-B			D
traverse(B)	traverse(B.Right = D)返回，弹栈B，栈内A			B
traverse(A)	traverse(A.Left = B)返回，弹栈A，栈内空 #此时根节点的左子树遍历完毕		A
traverse(A)	执行traverse(A.Right = F)，压栈A，栈内A	F
traverse(F)	执行traverse(F.Left = G)，压栈F，栈内A-F	G
traverse(G)	执行traverse(G.Left = null)，压栈G，栈内A-F-G
traverse(G)	raverse(G.Left = null)返回，弹栈G，栈内A-F		G
traverse(G)	执行traverse(G.Right = H)，压栈G，栈内A-F-G	H
traverse(H)	执行traverse(H.Left = null)，压栈H，栈内A-F-G-H
traverse(H)	traverse(H.Left = null)返回，弹栈H，栈内A-F-G		H
traverse(H)	执行traverse(H.Right = null)，压栈H，栈内A-F-G-H
traverse(H)	traverse(H.Right = null)返回，弹栈H，栈内A-F-G			H
traverse(G)	traverse(G.Right = H)返回，弹栈G，栈内A-F			G
traverse(F)	traverse(F.Left = G)返回，弹栈F，栈内A		F
traverse(F)	执行traverse(F.Right = I)，压栈F，栈内A-F	I
traverse(I)	执行traverse(I.Left = null)，压栈I，栈内A-F-I
traverse(I)	traverse(I.Left = null) 返回，弹栈I，栈内A-F		I
traverse(I)	执行traverse(I.Right = null)，压栈I，栈内A-F-I
traverse(I)	traverse(I.Right = null)返回，弹栈I，栈内A-F			I
traverse(F)	traverse(F.Right = I)返回，弹栈F，栈内A			F
traverse(A)	traverse(A.Right = F)返回，弹栈A，栈内无，此时根节点的右子树遍历完吧			A

从上表中可以看出，在一个二叉树中一个节点的遍历需要以下几个步骤：

1. 把当前执行环境压入栈中，遍历左子树。
2. 等待左子树遍历完成，弹出当前执行环境，继续执行。对应上表的（X.Left = Y返回）
3. 把当前环境压入栈中，遍历右子树。
4. 等待右子树遍历完成，弹出当前执行环境，继续执行。对应上表的（XRight = Y返回）

先序遍历在步骤1之前执行，也就是只要碰到这个节点，不遍历子节点，立即执行。

中序遍历在步骤2和步骤3之间执行，也就是遍历完当前节点的左子节点后执行。

后序遍历是在步骤4之后执行，也就是当前节点的左右子节点全部遍历完成后执行。

看完了二叉树的前中后序遍历，那么如何对二叉树进行分层遍历呢？

其实也很简单，主要利用队列的先进先出思想：

public void TraverseByLayer(TreeNode treeNode)
{
	var queue = new Queue<TreeNode>();
	queue.Enqueue(treeNode);
	while(queue.Count > 0)
	{
		var q = queue.Dequeue();
		Console.WriteLine(q.Value+" ");
		if(q.Left!=null)
			queue.Enqueue(q.Left);
		if(q.Right!=null)
			queue.Enqueue(q.Right);
	}
}

二叉树的遍历主要用到栈的先进后出和队列的先进先出特点，在大厂的算法面试题中较为常见。