本文最后编辑于 前，其中的内容可能需要更新。
1. 基本概念
树的遍历在实际使用中有非常重要的作用。对于二叉树来说，遍历可以分为深度优先和广度优先；其中深度优先可分为前序，中序，后序遍历；广度优先即层次遍历。
由于树的定义本身就是递归定义，因此采用递归的方法去实现树的前序，中序，后序三种遍历不仅容易理解而且代码简洁；而对于广度遍历来说，则须要其他数据结构如队列的辅助。
2 四种遍历详解
四种基本的遍历思想为：
- 前序遍历：根结点 —> 左子树 —> 右子树
- 中序遍历：左子树—> 根结点 —> 右子树
- 后序遍历：左子树 —> 右子树 —> 根结点
- 层次遍历：按层次逐层遍历即可
1
2
3
4
5
|
struct TreeNode {
int val;
TreeNode* left, right;
};
|
2.1 前序遍历
依据上文提到的遍历思路：根结点 —> 左子树 —> 右子树，前序遍历的递归形式非常容易给出：
1
2
3
4
5
6
7
| void preOrderTraverse1(TreeNode* root) {
if (root != NULL) {
cout << root->val << " ";
preOrderTraverse1(root->left);
preOrderTraverse1(root->right);
}
}
|
如果考虑前序遍历的非递归形式，则考虑对任意节点，访问该节点后，先访问其左子树，之后再访问右子树；则在访问左子树时需要将该节点暂存；需要的用到的数据结构是栈。示例代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void preOrderTraverse2(TreeNode* root) {
stack<TreeNode*> ts;
TreeNode* cur = root;
while(!!cur || !ts.empty()) {
if(!!cur) {
cout << cur->val << " ";
ts.push(cur);
cur = cur->left;
} else {
cur = ts.pop();
cur = cur->right;
}
}
}
|
2.2 中序遍历
依据上文提到的遍历思路：左子树 —> 根结点 —> 右子树，中序遍历的递归形式也非常容易给出：
1
2
3
4
5
6
7
| void inOrderTraverse1(TreeNode* root) {
if (root != NULL) {
inOrderTraverse1(root->left);
cout << root->val << " ";
inOrderTraverse1(root->right);
}
}
|
非递归形式的中序遍历和前序类似，只是将访问节点放到了出栈后；即对于任意节点，先将其入栈暂存，再访问其左子树，然后出栈时先访问该节点，再访问右子树。示例代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void inOrderTraverse2(TreeNode* root) {
stack<TreeNode*> ts;
TreeNode* cur = root;
while(!!cur || !ts.empty()) {
if(!!cur) {
ts.push(cur);
cur = cur->left;
} else {
cur = ts.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
}
|
2.3 后序遍历
依据上文提到的遍历思路：左子树 —> 右子树 —> 根结点，后序遍历的递归形式也很简单：
1
2
3
4
5
6
7
| void postOrderTraverse1(TreeNode* root) {
if (root != NULL) {
inOrderTraverse1(root->left);
inOrderTraverse1(root->right);
cout << root->val << " ";
}
}
|
后序遍历的非递归实现是三种遍历方式中最难的一种。对任意节点P，为保证访问顺序，需要对将节点P，右孩子，左孩子按顺序入栈；假设先将节点P入栈，对于任意栈顶节点P，假设P不存在子节点，则能够直接訪问它；若是P存在子节点，但是其子节点都已被訪问过了，则也能够直接訪问该结点；若非上述两种情况，则将P的右孩子和左孩子依次入栈。这样就保证了后序遍历的顺序访问节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void postOrderTraverse2(TreeNode *root) {
stack<TreeNode*> ts;
TreeNode* cur = root;
TreeNode* pre=NULL;
ts.push(cur);
while(!ts.empty()) {
cur = ts.top();
if((!cur->left && !cur->right) || (!!pre && (pre==cur->left || pre==cur->right))) {
cout << cur->val << " ";
ts.pop();
pre=cur;
} else {
if(cur->right)
ts.push(cur->right);
if(cur->left)
ts.push(cur->left);
}
}
}
|
2.4 层序遍历
借助队列数据结构，层次遍历的实现比較简单。先在队列中增加根结点，之后对于出队的任意节点，先访问它，同时若有子节点，则将子节点入队列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void levelTraverse(TreeNode* root) {
if (!root) {
return;
}
queue<TreeNode*> q;
TreeNode* cur = root;
q.push(cur);
while (!q.empty()) {
cur = q.pop();
cout << cur->val << " ";
if (cur->left) {
q.push(cur->left);
}
if (cur->right) {
q.push(cur->right);
}
}
}
|