二叉树的遍历
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。遍历是二叉树最重要的运算之一，是二叉树上进行其它运算的基础。
根据访问结点操作发生位置命名：
- 前序遍历(Preorder Traversal)，访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)，访问根结点的操作发生在遍历其左右子树之中。
- 后序遍历(Postorder Traversal)，访问根结点的操作发生在遍历其左右子树之后。
- 层序遍历(Level-order Traversal)，所有深度为d的结点要在深度为d+1的节点之前处理。由于它用的较少，所以本文不对它进行讨论。
注：由于先左后右和先右后左对称，故本文只讨论先左后右的三种次序。
二叉树节点定义
二叉树节点使用以下数据结构进行表示，包括关键字、左儿子、右儿子属性和一个带默认参数的构造函数。
struct TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int v = 0, TreeNode *l = NULL, TreeNode *r = NULL)
:val(v), left(l), right(r) { }
};
二叉树的遍历
二叉树遍历的实现方式主要有三种：递归遍历，非递归遍历和Morris遍历。
递归遍历
递归遍历的实现非常简单，按照遍历的次序，对当前结点分别调用左子树和右子树即可。此时每个结点只需遍历一次，故时间复杂度为O(n)。最差情况下递归调用的深度为O(n)，所以空间复杂度为O(n)。
前序遍历
void preOrder(TreeNode *root) {
if(root == NULL) {
return;
}
cout << root->val <<endl;
preOrder(root->left);
preOrder(root->right);
}
/*void函数如果想在它们的中间位置提前退出，可以使用return语句，此时return有点类似break；
只要函数的返回类型不是void，则每条return语句必须返回一个值。*/
中序遍历
void inOrder(TreeNode *root) {
if(root == NULL) {
return;
}
inOrder(root->left);
cout << root->val <<endl;
inOrder(root->right);
}
后序遍历
void postOrder(TreeNode *root) {
if(root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val <<endl;
}
非递归遍历
递归算法的本质是利用函数的调用栈进行，实际上我们可以自行使用栈来进行模拟，实现二叉树遍历的非递归实现。此时每个结点只需遍历一次，故时间复杂度为O(n)，空间复杂度为O(h),h为二叉树的高度。
前序遍历
首先把根节点入栈，然后在每次循环中执行以下操作：
此时栈顶元素即为当前的根节点，弹出并打印当前的根节点；
把当前根节点的右儿子入栈；
把当前根节点的左儿子入栈。
void preOrder2(TreeNode *root) { if(root == NULL) { return; } stack<TreeNode *> stk; stk.push(root); while(!stk.empty()) { TreeNode *pNode = stk.top(); stk.pop(); cout << pNode->val << endl; if(pNode->left) { stk.push(pNode->left); } if(pNode->right) { stk.push(pNode->right); } } }
中序遍历
初始化一个二叉树结点pNode指向根结点；
若pNode非空，那么就把pNode入栈，并把pNode变为其左儿子，直到最左边的结点；
若pNode为空，弹出栈顶的结点，并访问该结点，将pNode指向其右儿子。
void inOrder2(TreeNode *root) { if(root == NULL) { return; } stack<TreeNode *> stk; TreeNode *pNode = root; while(pNode || !stk.empty()) { if(pNode) { stk.push(pNode); pNode = pNode->left; } else { pNode = stk.top(); stk.pop(); cout << pNode->val << endl; pNode = pNode->right; } } }
后序遍历
因为后序遍历的顺序是：左子树->右子树->根节点，于是我们在前序遍历的代码中，当访问完当前节点后，先把当前节点的左子树入栈，再把右子树入栈，这样最终得到的顺序为：根节点->右子树->左子树，刚好是后序遍历倒过来的版本，于是把这个结果做一次翻转即为真正的后序遍历。而翻转可以通过使用另外一个栈简单完成，这样的代价是需要两个栈，但就复杂度而言，空间复杂度仍然是O(h)。
void postOrder2(TreeNode *root) {
if(root == NULL) {
return;
}
stack<TreeNode *> stk1,stk2;
stk1.push(root);
while(!stk1.empty()) {
TreeNode *pNode = stk1.top();
stk1.pop();
stk2.push(pNode);
if(pNode->right) {
stk1.push(pNode->right);
}
if(pNode->left) {
stk1.push(pNode->left);
}
}
while(!stk2.empty()) {
cout << stk2.top()->val << endl;
stk2.pop();
}
}
Morris遍历
Morris遍历的神奇之处在于它是非递归的算法，且不需要额外的O(h)的空间，而且复杂度仍然是线性的。这样的算法最关键的问题是当访问完一棵子树后，如何回到其对于的根节点再继续访问右子树呢？Morris是通过修改二叉树某些节点的指针来做到的。
中序遍历
按照定义，在中序遍历中，对于一棵以root为根的二叉树，当访问完root的前驱节点后，需要回到root节点进行访问，然后再到root的右儿子进行访问。于是我们可以每次访问到一棵子树时，找到它的前驱节点，把前驱节点的右儿子变为当前的根节点root，这样当遍历完前驱节点后，可以顺着这个右儿子回到根节点root。但问题是修改了该前驱节点的右儿子后什么时候再改回来呢？
- 当第一次访问以root为根的子树时，找到它的前驱pre，此时pre的右儿子必定为空，于是把这个右儿子设置为root，以便以后根据这个指针回到root节点。
- 当第二次回到以root为根的子树时，再找到它的前驱pre，此时pre的右儿子已经被设置成了当前的root，这时把该右儿子重新设置成NULL，然后继续进行root的右儿子的遍历。于是完成了指针的修改。
在这样的情景下，寻找当前节点的前驱节点时，不仅需要判断其是否有右儿子，而且还要判断右儿子是否为当前的root节点，跟普通情况下的寻址前驱节点稍微多了一个条件。由于在每次遍历一个节点的时候都需要寻找其前驱节点，而寻找前驱节点的时间一般与树的高度相关，这样看上去算法的复杂度应该为O(nlogn)才对。但由于其只需要对有左儿子的节点才寻找前驱，于是所有寻找前驱时走过的路加起来至多为一棵树的节点数，例如在下文的例子中，只需要对以下节点寻找前驱：
4
/ \
2 6
/ \ / \
1 3 5 7
- 节点4：寻找路径为：2-3
- 节点2：寻找路径为：1
- 节点6：寻找路径为：5
于是寻找前驱加上遍历的运算量之和至多为2*n，n为节点个数，于是算法的复杂度为仍然为O(n)。
void inOrder3(TreeNode *root) {
if(root == NULL) {
return;
}
TreeNode *pNode = root;
while(pNode) {
if(pNode->left == NULL) {
cout << pNode->val << endl;
pNode = pNode->right;
} else {
TreeNode *pPre = pNode->left;
while(pPre->right != NULL && pPre->right != pNode) {
pPre = pPre->right;
}
if(pPre->right == NULL) {
pPre->right = pNode;
pNode = pNode->left;
} else {
pPre->right = NULL;
cout << pNode->val << endl;
pNode = pNode->right;
}
}
}
}
前序遍历
前序遍历和中序遍历类似，只是在遍历过程中访问节点的顺序稍有不同。即在第一次访问一棵子树时，就要先对根节点进行访问，于是cout输出语句被放到了if判断中第一次访问的分支中。
void preOrder3(TreeNode *root) {
if(root == NULL) {
return;
}
TreeNode *pNode = root;
while(pNode) {
if(pNode->left == NULL) {
cout << pNode->val << endl;
pNode = pNode->right;
} else {
TreeNode *pPre = pNode->left;
while(pPre->right && pPre->right != pNode) {
pPre = pPre->right;
}
if(pPre->right == NULL) {
pPre->right = pNode;
cout << pNode->val << endl; //先输出左结点
pNode = pNode->left;
} else {
pPre->right = NULL;
pNode = pNode->right;
}
}
}
}
后序遍历
后序遍历稍微复杂，但其遍历的基本顺序也是和前/中序遍历类似，只是在打印的时候做了一个翻转。考虑下文例子中的后序遍历结果：1 3 2 5 7 6 4。其可以这样进行拆分并进行解释：
4
/ \
2 6
/ \ / \
1 3 5 7
- 1：最左下角的结果节点
- 3 2：节点2、3的倒序
- 5：右儿子的最左下角的节点
- 7 6 4：右边一列节点4、6、7的倒序
于是我们可以在中序遍历过程中，当第二次访问到一个节点时，把它的左儿子到它的前驱节点的路径上的节点进行翻转打印，即可得到后序遍历的结果。但这样的话根节点到最右下角那一列会访问不到，增加一个辅助节点作为新的根节点，把原有根节点作为其左儿子即可。
void reverse(TreeNode *p1, TreeNode *p2) {
if(p1 == p2)
return;
TreeNode *x = p1;
TreeNode *y = p1->right;
while(true) {
TreeNode *temp = y->right;
y->right = x;
x = y;
y = temp;
if(x == p2)
break;
}
}
void printReverse(TreeNode *p1, TreeNode *p2) {
reverse(p1, p2);
TreeNode *pNode = p2;
while(true) {
cout << pNode->val << endl;
if(pNode == p1)
break;
pNode = pNode->right;
}
reverse(p2, p1);
}
void postOrder3(TreeNode *root) {
if(root == NULL) {
return;
}
TreeNode *dummy = new TreeNode(-1);
dummy->left = root;
TreeNode *pNode = dummy;
while(pNode) {
if(pNode->left == NULL)
pNode = pNode->right;
else {
TreeNode *pPrev = pNode->left;
while(pPrev->right && pPrev->right != pNode){
pPrev = pPrev->right;
}
if(pPrev->right == NULL) {
pPrev->right = pNode;
pNode = pNode->left;
}
else {
printReverse(pNode->left, pPrev);
pPrev->right = NULL;
pNode = pNode->right;
}
}
}
}
代码测试
我们对以下简单的二叉树进行测试。
4
/ \
2 6
/ \ / \
1 3 5 7
测试代码
int main() {
TreeNode a1(1), a3(3), a5(5), a7(7);
TreeNode a2(2, &a1, &a3), a6(6, &a5, &a7);
TreeNode a4(4, &a2, &a6);
//前序遍历：4 2 1 3 6 5 7 5
preOrder(&a4);
preOrder2(&a4);
preOrder3(&a4);
cout << endl;
//中序遍历：1 2 3 4 5 6 7
inOrder(&a4);
inOrder2(&a4);
inOrder3(&a4);
cout << endl;
//后序遍历：1 3 2 5 7 6 4
postOrder(&a4);
postOrder2(&a4);
postOrder3(&a4);
}
参考链接：
  二叉树遍历
  二叉树遍历（递归、非递归、Morris遍历）
  二叉树的三种遍历方式