二叉树遍历全面总结（先，中，后序，层序，递归及非递归版本，如何利用遍历方法解决实际问题）_二叉树遍历前序中序后序实验总结

什么叫对二叉树的遍历

在具体阐述二叉树的遍历之前，我觉得有必要先认清两个事实：即什么叫二叉树的遍历，以及我们为什么要对二叉树进行遍历。

数据结构中，二叉树是一种层级结构，一个结点对应两个子结点，它描述了一种父子关系。每个结点中储存中我们需要的数据，并且通过了这种层级的父子关系组织了起来。

既然将数据通过上述的形式进行组织，我们必将需要从这个组织中提取所需要的数据。
对于一个链表来说，除首尾结点外，都有前驱后继的数据联系，使得我们能够沿着这种关系，逐个不重复的访问每个结点。

比如，需要从链表中找到数据域为整型3的结点，那么沿着头结点，通过结点前驱后继关系，必然能够准确且毫无遗漏的找到每个满足的结点。

那么？二叉树（物理结构是用链表实现）如何能够逐个不重复的访问每一个结点呢？解决这个问题就是二叉树遍历的关键。

二叉树遍历的实质就是将二叉树的层级结构（非线性的）转换成像单链表一样的线性结构。这个二叉树的结点也有了前驱和后继，沿着前驱后继，便能逐个不重复的访问每一个结点。

为什么要对二叉树进行遍历

至此，已经阐述清楚什么叫二叉树的遍历了，那么又为何需要对二叉树进行遍历?
上面其实已经提到了这个问题的答案，数据被二叉树这种逻辑结构所组织，肯定在某个时刻找出问题所需要的数据。

上述是个普通的二叉树，如果让你找出每个数据域中整型值 < 5的结点你会怎么去做？
答案是，遍历！
也就是说对二叉树遍历的实质是为了让我们能够应用自己的逻辑来找出所需要的结点。

如何对二叉树进行遍历

理解了什么叫遍历，也明白了为什么要遍历，并且遍历也十分的重要，下面就开始真正的重点内容: 如何对二叉树进行遍历。

首先分析一下每个二叉树结点的结构:

typedef int ElemType;
typedef struct TreeNode{
	ElemType data;
	struct TreeNode *left,*right;
}TreeNode;
1
2
3
4
5

每个结点拥有一个数据域存储数据，有两个指针域，一个指向自己的左子树，另一个指向自己的右子树。
很多文章和教材都没有强调这一点：不要把left和right理解成左孩子结点，右孩子结点，尤其是在对二叉树进行遍历的时候，一定要把理解为左子树和右子树，本身的这个结点代表的当前子树的根结点。
好，理解了上述这一点以后，我们可以把一棵二叉树进行拆分了

一棵二叉树就包括三部分，根结点root，左子树left，右子树right。
那么如果要对二叉树进行遍历，是不是只要遍历访问了，root ，left ，right这三个部分就可以了？
这个怎么这么简单，woc这是假的吧？

本质问题就是这样，这也就引出了关于二叉树定义的一个重要性质——递归性。二叉树是具有递归意义的，二叉树根结点的左右孩子结点也是一棵二叉树（所以也就不难理解二叉树为什么可以为空了），在解决二叉树的很多问题都可以利用这种递归分治的思想来解决，这里就不展开叙述了。

回到遍历这个问题，我们已经了解到遍历一棵二叉树只需要访问三个部分，那么访问这三个部分的顺序不同也就引出了先序，中序，后序遍历三种遍历方法。

先序，中序，后序遍历的递归方法及其实质

先序遍历是先访问根结点，再访问左子树，最后访问右子树。

中序遍历是先访问左子树，再访问根结点，最后访问右子树。

后序遍历是先访问左子树，再访问右子树，最后访问根结点。

看到以上遍历方法的定义，可以提取两点重要的信息：

• 先，中，后，是根据根结点在三个部分的相对位置来确定的。
• 左子树一定在右子树之前访问。（划重点，需要牢记！）

三种遍历的递归版本

解释了这么多，来看一下这三种遍历递归版本的版本（千万不要因为简单或者知道了就跳过）；

先序遍历
void PreOrder(Node * root){
	if(root == nullptr)return;
	cout<<root->data;
	preOrder(root->left);
	preOrder(root->right);
}
中序遍历
void MidOrder(Node * root){
	if(root == nullptr)return;
	MidOrder(root->left);
	cout<<root->data;
	MidOrder(root->right);
}
后序遍历
void BackOrder(Node * root){
	if(root == nullptr)return;
	BackOrder(root->left);
	BackOrder(root->right);
	cout<<root->data;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

代码就和思路一样异常的简单，三种不同遍历方式不同的地方也仅仅是打印语句位置的不一样。
正是因为代码这么简单，让很多人忽略了这种递归遍历的实质。

这是一棵普通的二叉树，我们用后序遍历对他进行访问（主要关注以2为根结点的子树每个结点被访问的过程）：
首先来到 1 ，需要先访问它的左子树，所来到2。
2有左子树7，所以又来到7.
访问7的左子树，为空返回7
访问7的右子树，为空返回7
打印7的值，返回它的双亲2.
2有右子树4，来到了4
访问4的左子树，为空返回4
访问4的右子树，为空返回4
打印7的值，返回它的双亲2.
打印2的值，并继续下面的过程。

仔细观察上面访问的过程可以发现，会有三次机会到达一个结点，2，7，4这三个结点都被访问了三次（其他结点必然符合同样的规律）。
第一次为首次执行以2根结点的函数，第二次为从左子树访问完毕退回的时候，第三次为从右子树访问完毕退回的时候。
一棵子树可以被访问三次，所以才能够依次打印根结点，左子树，右子树这三个部分啊！！！
先进入的数据后被访问到，这种先入后出的数据结构可以用栈来实现。系统函数调用栈为我们完成了这一项工作 ，递归函数的调用被一层层的压入栈中，使得三次访问一个结点成为了一种可能，以上就是三种遍历递归算法的实质。

三种遍历的非递归版本

上面谈及，三种遍历的递归算法主要依靠的是系统调用栈，那么要想实现三种遍历的非递归算法一般需要自己构建一个栈。
具体探究非递归算法之前，不知道读者心中有没有这样一个疑虑：非递归算法比递归算法有没有优势呢？要知道递归算法的写法非常简单，复杂度提高的同时，有没有带来一些好处呢？
第一点，肯定是时间空间效率的提高，系统函数调用栈中保存函数执行的所有信息，会有较多的浪费。
第二点，非递归算法在解决某些问题的时候会较为便利，如找到某一个结点到自己祖先结点的路径，用后序的非递归算法就很简单，而用递归算法就有些难以下手。递归算法都可以改成非递归算法，从这点上出发，非递归算法的通用性更好，适合的问题范围也更广。

先序遍历的非递归算法

思路：先序算法先打印根结点，其次左子树，最后右子树。
所以一开始时访问根结点，如果有右子树先将右子树压入栈，然后将左子树压入栈。

所以下次访问的时候 将栈顶弹出并访问，继续压入它的右子树和左子树，直至栈为空。

#include<stack>
using namespace std;
void PreOrder(Node * root){
	if(root == nullptr)return;
	stack<Node *>helper;//所要用到的辅助栈
	helper.push(root);//首先根结点入栈
	//跳出循环的条件是栈为空
	while(!helper.empty()){
		root = helper.top();//注意这里是复用了变量，获得栈顶元素
		helper.pop();//弹出栈顶元素
		visit(root);//对根结点进行你想要进行的逻辑操作
		if(root->right)helper.push(root->right);//压入左子树
		if(root->left)helper.push(root->left);//压入右子树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

中序遍历的非递归算法

思路：先访问左子树，再访问根结点，最后访问右子树
根结点首先入栈，根结点如果有左孩子就一直压栈，直到当前结点没有左孩子，例子如下

此时的结点指针指向了7的左孩子null，从栈顶弹出一个元素，对它进行访问操作，此时当前结点如果有右孩子结点，右孩子入栈，并且继续一直压左孩子。当前结点如果没有右孩子结点，继续循环。从栈顶弹出元素，访问，判断是否有右孩子。。。。一直到当前的结点指针为null并且栈已经为空结束遍历。
下面结合代码体会这个过程：

#include<stack>
using namespace std;
void MidOrder(Node * root){
	if(root == nullptr)return;
	stack<Node *>helper;//所要用到的辅助栈
	while(root || !helper.empty()){
	if(root){
		helper.push(root);//当前根结点入栈
		root = root->left;//把当前指针指向左孩子，如果左孩子不为空下次循环继续压栈
	  }else{
		root = helper.top();//当前结点指向空，获得栈顶元素
		visit(root);//对当前结点进行逻辑操作
		helper.pop();//将栈顶元素弹出
		root = root->right;//将当前结点指向右孩子，如果不为空，那么下次循环的时候会被压栈
	  }
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

后序遍历的非递归算法

思路：先访问左子树，再访问右子树，最后访问根结点。
后序遍历的较难，就需要使用一些小技巧。

1. 把根结点压入栈中，沿着最左边的路径压栈到底，这与中序遍历是一样的。
2. 当前结点指向为空了，获取栈顶的元素
3. 如果栈顶元素有右子树，并且上一个弹出的元素不是该右子树，把右子树压到栈里面
4. 如果栈顶元素没有右子树或者右子树已被访问过，弹出栈顶元素,并且记录此次弹出的元素
5. 直到栈为空并且当前指针也为空，结束循环

#include<stack>
using namespace std;
void BackOrder(Node * root){
	if(root == nullptr)return;
	Node * pre = nullptr;//用于记录上个被弹出的结点
	stack<Node *>helper;
	while(!stack.empty()){
	if(root){
		helper.push(root);
		root = root->left;
	}else{
		root = helper.top();//获取栈顶元素
		if(root->right){
			if(!pre || (pre && pre != root->right) ){
				//如果上个被弹出的结点不存在，或者上个结点时存在的
				//但上个弹出的结点不是当前结点的右孩子
				root = root->right;//当前结点指向右孩子
				continue;
			}
		}
			helper.pop();//弹出栈顶元素
			pre = root;
			visit(root);//访问当前结点
			root = nullptr;//当前指针重置
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

另一种遍历算法——层序遍历

相比于前三种遍历算法，我觉得层次遍历算法出现的频率较高。二叉树除了递归的性质较为明显以外，还有一个重要的特征就是具有层级结构。所以层序遍历的思路就是从上到下从左到右的遍历每一个结点。
准备一个队列，先入队列的元素先被访问。代码实现如下：

#include<queue>
void LayerOrder(Node * root){
	if(root == nullptr)return;//当没有结点的时候直接返回
	queue<Node *>helper;
	helper.push(root);//根结点先入队，待会儿被第一个访问
	while(!helper.empty()){
		root = helper.front();//每次获取队头
		helper.pop();
		visit(root);
		if(root->left)helper.push(root->left);
		if(root->right)helper.push(root->right);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

层序遍历算法的应用场景

层序算法可以遍历每一层的结点，所以就有一些很重要的特征

1. 当你需要判断每一个结点是否具有一项特征时可以用层序遍历：如判断一棵树是不是一棵完全二叉树，获取一棵树中所有的叶子节点。
2. 需要获得每一层的具体信息：如获得二叉树的宽度。获得二叉树的高度等等，下面具体举两个例子。

题目：

1. 设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针是head，二叉树按照二叉链表方式存储，链接时用叶结点的右指针域来存放单链表指针。

Node* GetLeaf(Node * root){
	if(root == nullptr)return nullptr;
	queue<Node *>helper;
	Node * head = nullptr,*rear = nullptr;//head是队头结点,rear是队尾结点
	helper.push(root);
	while(!helper.empty()){
	root = helper.front();
	helper.pop();
	if(!root->right && !root->left){
		if(!head){
			head = rear = root;
			}else{
			rear->right = root;
			rear = root;
			}
		}
	if(root->left)helper.push(root->left);
	if(root->right)helper.push(root->right);
	}
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2. 假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树b的宽度（即具有结点数最多的那一层的结点个数）

#define MAXSIZE 20
int GetWidth(Node * root){
	Node* queue[MAXSIZE];//准备一个数组队列
	int front,rear;//队头和队尾指针
	front = rear = -1;
	int width = 0;//当前层的宽度
	int maxWidth = 0;//目前最宽层的宽度
	int last = 0;//记录上一层最后的结点的序号
	queue[++rear] = root;
	while(front < rear){
		root = queue[++front];
		if(root->left){
			queue[++rear] = root->left;
			width++;
		}
		if(root->right){
			queue[++rear] = root->right;
			width++;
		}
		if(front == last){
			last = rear;
			maxWidth = maxWidth >= width ? maxWidth : width;
			width = 0;
		}
	}
	return maxWidth;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27