二叉树的遍历：
先序，中序，后序；
二叉树的遍历有三种常见的方法，
最简单的实现就是递归调用，
另外就是飞递归的迭代调用，
最后还有O(1)空间的morris遍历；
二叉树的结构定义：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
1.先序遍历：
递归：
void preOrderRecursive(TreeNode *root) {
if (!root)
return;
cout << root->val << " ";
preOrderRecursive(root->left);
preOrderRecursive(root->right);
}
迭代：
迭代要用到栈来保存父亲结点，
先序遍历，所有访问过的结点都先输出，
先遍历当前结点和当前结点的左子树，一直到左子树的最左边的结点，
遍历过的这些结点都入栈，左孩子为空时，栈顶元素设为当前结点，出栈，
然后把当前结点设为该节点的右孩子，循环一直到当前结点为空且栈也为空。
void preOrderIterative(TreeNode *root) {
if (!root)
return;
stack<TreeNode*> stk;
TreeNode *cur = root;
while (cur || !stk.empty()) {
while (cur) {
cout << cur->val << " ";
stk.push(cur);
cur = cur->left;
}
if (!stk.empty()) {
cur = stk.top();
stk.pop();
cur = cur->right;
}
}
}
/*
* 模拟递归
* */
void preOrderIterative1(TreeNode *root) {
if (!root)
return;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* tp = stk.top();
stk.pop();
cout << tp->val << " ";
if (tp->right)
stk.push(tp->right);
if (tp->left)
stk.push(tp->left);
}
}
Morris方法：
1.当前结点的左孩子为空，输出当前结点，并设置当前结点的右孩子为当前结点；
2.当前结点的左孩子不为空：
a.找到当前结点中序遍历的前驱结点，即为该节点的左孩子的最右边的结点，前驱结点的右孩子为空，则设置前驱结点的右孩子为当前结点，并输出当前结点，设当前结点的左孩子为当前结点；
b.前驱结点的右孩子为当前结点，则恢复前驱结点的右孩子为NULL，设当前结点的右孩子为当前结点；
void preOrderMorris(TreeNode *root) {
if (!root)
return;
TreeNode* cur = root;
TreeNode* pre = NULL;
while (cur) {
if (cur->left == NULL) {
cout << cur->val << " ";
cur = cur->right;
}
else {
pre = cur->left;
while (pre->right != NULL && pre->right != cur)
pre = pre->right;
if (pre->right == NULL) {
cout << cur->val << " ";
pre->right = cur;
cur = cur->left;
}
else {
pre->right = NULL;
cur = cur->right;
}
}
}
}
2.中序遍历：
递归：
void inOrderRecursive(TreeNode *root) {
if (!root)
return;
inOrderRecursive(root->left);
cout << root->val << " ";
inOrderRecursive(root->right);
}
迭代：
1.如果当前结点的左孩子不为空，则把当前结点的左孩子入栈，知道当前结点的左孩子为空；
2.如果栈不为空，则出栈，栈顶元素为当前结点，输出当前结点，并把当前结点的右孩子设为当前结点；
重复1，2直到当前结点为NULL且栈也为空；
void inOrderIterative(TreeNode *root) {
if (!root)
return;
stack<TreeNode*> stk;
TreeNode *cur = root;
while (cur || !stk.empty()) {
while (cur) {
stk.push(cur);
cur = cur->left;
}
if (!stk.empty()) {
cur = stk.top();
stk.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
}
Morris方法：
和先序遍历的过程类似，只不过输出结点的位置不一样，中序遍历是在2.b中，也就是前驱结点的右孩子为当前结点时，即当前结点的左子树都已经遍历完成时，输出当前结点；
void inOrderMorris(TreeNode *root) {
if (!root)
return;
TreeNode* cur = root;
TreeNode* pre = NULL;
while (cur) {
if (cur->left == NULL) {
cout << cur->val << " ";
cur = cur->right;
}
else {
pre = cur->left;
while (pre->right != NULL && pre->right != cur)
pre = pre->right;
if (pre->right == NULL) {
pre->right = cur;
cur = cur->left;
}
else {
cout << cur->val << " ";
pre->right = NULL;
cur = cur->right;
}
}
}
}
3.后序遍历：
递归：
void postOrderRecursive(TreeNode *root) {
if (!root)
return;
postOrderRecursive(root->left);
postOrderRecursive(root->right);
cout << root->val << " ";
}
迭代：
后序遍历比先序、中序都要复杂，
第一种迭代方法，可以用两个栈来模拟递归的遍历；
栈1初始化时把根节点入栈，
1.栈1出栈，把出栈的元素加入栈2，然后把该元素的左孩子（如果不为空），右孩子（如果不为空）加入栈1，知道栈1为空；
2.栈2出栈直到空，每次出栈时输出栈顶元素；
通过两个栈，保证了栈2中的元素顺序，
第二种迭代方法，
用一个结点保存访问过的最后一个结点pre，如果pre为栈顶元素的右孩子，则说明栈顶元素的右子树已经遍历过了，直接输出栈顶元素，并把当前结点设为NULL，并更新pre为出栈的元素；
1.如果当前结点存在，则一直向左遍历，入栈遍历的元素，直到结点为空；
2.栈不为空时，出栈，当前结点为栈顶元素，
如果当前结点的右孩子不为空且不为pre，说明当前结点的右子树没有遍历过，设置当前结点为该节点的右孩子，
如果右孩子为空或者为pre，直接输出当前结点，更新pre为当前结点，并设当前结点为NULL，
重复1，2直到当前结点为NULL并且栈为空；
void postOrderIterative(TreeNode *root) {
if (!root)
return;
stack<TreeNode*> stk;
TreeNode *cur = root;
TreeNode *pre = NULL;
while (cur || !stk.empty()) {
while (cur) {
stk.push(cur);
cur = cur->left;
}
if (!stk.empty()) {
cur = stk.top();
if (cur->right != NULL && cur->right != pre) {
cur = cur->right;
}
else {
cout << cur->val << " ";
pre = cur;
stk.pop();
cur = NULL;
}
}
}
}
/*
* 双栈法
*/
void postOrderIterative1(TreeNode *root) {
if (!root)
return;
stack<TreeNode*> stk1, stk2;
TreeNode *cur;
stk1.push(root);
while (!stk1.empty()) {
cur = stk1.top();
stk1.pop();
stk2.push(cur);
if (cur->left)
stk1.push(cur->left);
if (cur->right)
stk1.push(cur->right);
}
while (!stk2.empty()) {
cout << stk2.top()->val << " ";
stk2.pop();
}
}
Morris方法：
morris方法的后序遍历较为复杂，因为需要逆序输出右孩子到父亲结点；
遍历过程与先序与中序类似，
当前驱结点的右孩子为当前结点时，左子树已经遍历完成，逆序输出当前结点的左孩子到前驱结点；
类似于链表的反转，不过反转输出之后，记得要反转回来。
void reverse(TreeNode *begin, TreeNode *end) {
if (begin == end)
return;
TreeNode *pre = begin;
TreeNode *cur = begin->right;
TreeNode *next;
while (pre != end) {
temp = cur->right;
cur->right = pre;
pre = cur;
cur = temp;
}
}
void traversalReversal(TreeNode *begin, TreeNode *end) {
reverse(begin, end);
TreeNode *it = end;
while (true) {
cout << it->val << " ";
if (it == begin)
break;
it = it->right;
}
reverse(end, begin);
}
void postOrderMorris(TreeNode *root) {
if (!root)
return;
TreeNode dump();
dump.left = root;
TreeNode *cur = &dump;
TreeNode *pre = NULL;
while (cur) {
if (cur->left == NULL) {
cur = cur->right;
}
else {
pre = cur->left;
while (pre->right != NULL && pre->right != cur)
pre = pre->right;
if (pre->right == NULL) {
pre->right = cur;
cur = cur->left;
}
else {
traversalReverse(cur->left, pre);
pre->right = NULL;
cur = cur->right;
}
}
}
}
参考：
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html