转自：http://blog.csdn.net/ssjhust123/article/details/7773103
在前一篇文章二叉树遍历递归算法对二叉树遍历的递归算法做了总结，这篇文章就来对二叉树遍历的非递归算法做个汇总。还是与上一篇文章一样的顺序，一一汇总先序、中序、后序以及层序遍历的非递归算法。
1、先序遍历（非递归算法）
先序遍历非递归访问，使用栈即可实现。先序遍历的非递归访问在所有的遍历中算是最简单的了。主要思想就是先将根结点压入栈，然后根结点出栈并访问根结点，而后依次将根结点的右孩子、左孩子入栈，直到栈为空为止。代码如下：
- void preOrderIter(struct node *root)
- {
- if (root == NULL) return;
- stack<struct node *> s;
- s.push(root);
- while (!s.empty()) {
- struct node *nd = s.top();
- cout << nd->data << " ";
- s.pop();
- if (nd->right != NULL)
- s.push(nd->right);
- if (nd->left != NULL)
- s.push(nd->left);
- }
- cout << endl;
- }
先序遍历的非递归算法另一算法，也是用的栈，只是稍微复杂点，当左子树遍历完后，需要回溯并遍历右子树。
- void preOrderIter2(struct node *root)
- {
- stack<struct node *> s;
- while (root != NULL || !s.empty()) {
- if (root != NULL) {
- cout << root->data << " "; //访问结点并入栈
- s.push(root);
- root = root->left; //访问左子树
- } else {
- root = s.top(); //回溯至父亲结点
- s.pop();
- root = root->right; //访问右子树
- }
- }
- cout << endl;
- }
本算法有一个地方要注意的是，每次从栈中pop出结点时，表示该结点以及该的左子树已经访问完了，接下来访问其右子树。
2、中序遍历（非递归算法）
中序遍历非递归算法也是采用栈实现，与上面的先序遍历算法2类似，只是访问根结点的时机不同。
- void inOrderIter(struct node *root)
- {
- stack<struct node *> s;