二叉树是最常考也最常用的树形结构，而遍历又是一切操作的地基。查找节点、打印整棵树、把树序列化存进文件，本质上都是先定一个顺序，把每个节点访问一遍。二叉树遍历分先序、中序、后序三种递归顺序，还有一种一层一层来的层序。

这一节我们拿一棵具体的树，把递归写法、借助栈的非递归写法、借助队列的层序写法都在同一棵树上走一遍，最后把四种访问顺序列成表对照。读之前只需要知道二叉树用左右孩子指针表示就行。

1. 一棵示例树

我们先把树建出来，后面所有遍历都在它上面演示。这棵树有 A 到 H 共 8 个节点，父子关系是这样的。A 是根，A 的左孩子是 B，右孩子是 F。B 没有左孩子，右孩子是 C。C 的左孩子是 D，右孩子是 E。F 没有左孩子，右孩子是 G。G 的左孩子是 H，没有右孩子。其余节点都没有孩子。

建这棵树的代码如下，指针指向谁就是谁的父子关系，对照上面的描述看一遍就清楚了。

#include <iostream>

struct BiNode
{
	char ch;
	BiNode* lchild;
	BiNode* rchild;
};

int main()
{
	//创建结点
	BiNode node1, node2, node3, node4, node5, node6, node7, node8;
	node1.ch = 'A'; node1.lchild = nullptr; node1.rchild = nullptr;
	node2.ch = 'B'; node2.lchild = nullptr; node2.rchild = nullptr;
	node3.ch = 'C';	node3.lchild = nullptr; node3.rchild = nullptr;
	node4.ch = 'D';	node4.lchild = nullptr; node4.rchild = nullptr;
	node5.ch = 'E';	node5.lchild = nullptr; node5.rchild = nullptr;
	node6.ch = 'F';	node6.lchild = nullptr; node6.rchild = nullptr;
	node7.ch = 'G';	node7.lchild = nullptr; node7.rchild = nullptr;
	node8.ch = 'H';	node8.lchild = nullptr; node8.rchild = nullptr;

	//建立结点关系
	node1.lchild = &node2;
	node1.rchild = &node6;
	node2.rchild = &node3;
	node3.lchild = &node4;
	node3.rchild = &node5;
	node6.rchild = &node7;
	node7.lchild = &node8;

	return 0;
}

2. 递归怎么写

树建好了，我们先看最自然的递归写法。递归的思路是把一棵大树拆成根、左子树、右子树三部分，区别只在于访问根节点那一句放在什么位置。放在最前面就是先序，放在左子树之后、右子树之前就是中序，放在最后面就是后序。三个版本除了打印那一行的位置不同，其余代码完全一样。

// 先序遍历：先访问根，再左右
void recursion_traversal(BiNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%c", root->ch);
	recursion_traversal(root->lchild);
	recursion_traversal(root->rchild);
}

// 中序遍历：先左，再访问根，再右
void recursion_traversal(BiNode* root)
{
	if (root == NULL)
	{
		return;
	}
	recursion_traversal(root->lchild);
	printf("%c", root->ch);
	recursion_traversal(root->rchild);
}

// 后序遍历：先左右，再访问根
void recursion_traversal(BiNode* root)
{
	if (root == NULL)
	{
		return;
	}

	recursion_traversal(root->lchild);
	recursion_traversal(root->rchild);
	printf("%c", root->ch);
}

我们拿这棵树手算一遍先序。从 A 出发，先访问 A，再钻进左子树。访问 B，B 没有左孩子，就去右子树。访问 C，再去 C 的左孩子，访问 D，D 的两个孩子都空，退回 C 再去右孩子，访问 E。左子树走完回到 A，钻右子树。访问 F，F 没有左孩子，去右孩子。访问 G，再去左孩子，访问 H。整条先序就是 A B C D E F G H。

中序和后序照着同样的规矩换打印位置就行，不用重新发明思路。中序是左子树走完才轮到根，后序是左右子树都走完才轮到根。三种顺序在这棵树上的完整结果放到后面表格里一起对照。

3. 栈上的迭代

递归写起来简单，但函数调用会用到系统栈，树很深的时候有栈溢出的风险，中途也没法停下看一眼状态。把递归改成迭代，就得自己拿一个栈把现场存下来。

这里的关键技巧，是给每个入栈的节点配一个标记位。第一次碰到一个节点，说明它还没处理过，先把它重新压回栈里，这次标记为 true，再按逆序把它的右孩子、左孩子压进去。等以后这个标记为 true 的节点再弹出来，就直接输出。因为栈是后进先出，压栈顺序反过来，弹出来的顺序正好是想要的访问顺序。

void non_recursion_traversal(BiNode* root)
{

	// 根节点入栈
	std::stack<std::pair<bool, BiNode*>> stack;
	stack.push(std::make_pair(false, root));

	while (!stack.empty())
	{
		// 弹出栈顶元素
		auto element = stack.top();
		stack.pop();

		// 如果栈顶元素标记为 true 则直接输出
		if (element.first)
		{
			std::cout << element.second->ch << " ";
			continue;
		}

		// 如果栈顶元素标记为 false, 则按下面的规则再次进行入栈操作
		/*
		* 如果先序遍历，则入栈顺序为：右、左、根
		* 如果中序遍历，则入栈顺序为：右、根、左
		* 如果后序遍历，则入栈顺序为：根、右、左
		* 注意: 根节点第二次入栈时，需要将其 first 属性修改为 true
		*/

		// 右结点
		if (element.second->rchild != nullptr)
		{
			stack.push(std::make_pair(false, element.second->rchild));
		}

		// 左结点
		if (element.second->lchild != nullptr)
		{
			stack.push(std::make_pair(false, element.second->lchild));
		}

		// 根节点
		element.first = true;
		stack.push(element);
	}
}

代码里现在压栈的顺序是右孩子、左孩子、根。弹出来先碰到被标成 true 的根，处理完再展开左子树、右子树，这就是先序。想换成中序就把压栈顺序改成右、根、左，想换成后序就改成根、右、左，根那一次都要标成 true。这段跑出来和递归先序完全一致，输出 A B C D E F G H。

4. 队列做层序

前面三种都是一条路扎到底，层序换个思路，不钻到底，而是从上到下、从左到右一层一层扫过去。

一层一层扫，先进先出才对路，所以用队列。根先入队，每次从队头取出一个节点访问，再把它的左右孩子依次入队。先入队的先被处理，同一层的节点就自然按从左到右的顺序排好了。

void level_traversal(BiNode* root)
{

	// 根节点入队
	std::queue<BiNode *> queue;
	queue.push(root);

	while (!queue.empty())
	{
		// 弹出队头元素
		auto element = queue.front();
		queue.pop();

		// 打印队头元素
		std::cout << element->ch << " ";

		// 将当前根节点的左右子结点入队列
		if (element->lchild != nullptr)
		{
			queue.push(element->lchild);
		}

		// 右结点
		if (element->rchild != nullptr)
		{
			queue.push(element->rchild);
		}
	}
}

我们在这棵树上走一遍。第一层 A 出队访问，把 B、F 入队。第二层 B 出队访问，B 没有左孩子，把 C 入队，接着 F 出队访问，把 G 入队。第三层 C 出队访问，入队 D、E，然后 G 出队访问，入队 H。第四层 D、E、H 依次出队，队列空了。层序结果是 A B F C G D E H。

5. 四序结果对照

我们把四种顺序在这棵树上的结果放在一起对比，每种顺序的脾气就一目了然了。

遍历方式	访问顺序	典型用途
先序	A B C D E F G H	最先见到根，适合复制树、导出前缀表达式
中序	B D C E A F H G	二叉搜索树上得到升序序列
后序	D E C B H G F A	最后才见根，适合释放树、删除节点
层序	A B F C G D E H	按层从左到右，适合按层打印、找最近公共祖先

中序那一行值得多看一眼。如果这棵树是二叉搜索树，左子树都比根小、右子树都比根大，那中序遍历天然就是排好序的序列，这也是二叉搜索树最常被利用的性质。

6. 常见的误区

第一个误区，是把先序和层序搞混。先序是一根筋扎到底，访问完 A 立刻钻 B，根本不管旁边的 F。层序是把整层排齐，A 访问完下一个是和 B 同层的 F，不是 B 的孩子 C。

第二个误区，是以为非递归遍历一定要手写一套复杂的栈状态机。用这里的标记位技巧，先序、中序、后序三套逻辑共用一段代码，只改压栈顺序，这是最省心的写法。

第三个误区，是以为遍历只能递归。栈和队列都能模拟，递归本质上就是系统帮你管了一个栈而已，换成手写容器只是把控制权拿回到自己手里。

回到这棵树。先序、中序、后序靠的是访问根的时机不同，递归三行代码换个打印位置就出来，非递归用一个带标记的栈把现场存住，层序换成队列按层排队。四种顺序各有用处，中序在搜索树上出有序序列，后序适合删除和释放，层序适合按层处理。把上面的代码在这棵树上跑一遍，输出和表格对得上，遍历这一节就算过关了。