1.先序遍历
从递归说起
1.void preOrder(TNode* root)
2.{
3. if (root != NULL)
4. {
5. Visit(root);
6. preOrder(root->left);
7. preOrder(root->right);
8. }
9.}
递归算法非常的简单。先访问跟节点，然后访问左节点，再访问右节点。如果不用递归，那该怎么做呢？仔细看一下递归程序，就会发现，其实每次都是走树的左分支(left)，直到左子树为空，然后开始从递归的最深处返回，然后开始恢复递归现场，访问右子树。
其实过程很简单：一直往左走 root->left->left->left...->null，由于是先序遍历，因此一遇到节点，便需要立即访问；由于一直走到最左边后，需要逐步返回到父节点访问右节点，因此必须有一个措施能够对节点序列回溯。有两个办法：
1.用栈记忆：在访问途中将依次遇到的节点保存下来。由于节点出现次序与恢复次序是反序的，因此是一个先进后出结构，需要用栈。
使用栈记忆的实现有两个版本。第一个版本是模拟递归的实现效果，跟LX讨论的，第二个版本是直接模拟递归。
2.节点增加指向父节点的指针：通过指向父节点的指针来回溯（后来发现还要需要增加一个访问标志，来指示节点是否已经被访问，不知道可不可以不用标志直接实现回溯？想了一下，如果不用这个标志位，回溯的过程会繁琐很多。暂时没有更好的办法。）
(还有其他办法可以回溯么？)
这3个算法伪代码如下，没有测试过。
1.1 先序遍历伪代码：非递归版本，用栈实现，版本1
1.// 先序遍历伪代码：非递归版本，用栈实现，版本1
2.void preOrder1(TNode* root)
3.{
4. Stack S;
5. while ((root != NULL) || !S.empty())
6. {
7. if (root != NULL)
8. {
9. Visit(root);
10. S.push(root); // 先序就体现在这里了，先访问，再入栈 11. root = root->left; // 依次访问左子树
12. }
13. else
14. {
15. root = S.pop(); // 回溯至父亲节点
16. root = root->right;
17. }
18. }
19.}
preOrder1每次都将遇到的节点压入栈，当左子树遍历完毕后才从栈中弹出最后一个访问的节点，访问其右子树。在同一层中，不可能同时有两个节点压入栈，因此栈的大小空间为O(h)，h为二叉树高度。时间方面，每个节点都被压入栈一次，弹出栈一次，访问一次，复杂度为O(n)
1.2 先序遍历伪代码：非递归版本，用栈实现，模拟递归过程，版本2 [
1.
2.// 先序遍历伪代码：非递归版本，用栈实现，模拟递归过程，版本2
3.void preOrder2(TNode* root)
4.{
5. if ( root != NULL)
6. {
7. Stack S;
8. S.push(root);
9. while (!S.empty())
10. {
11. TNode* node = S.pop();
12.
13. Visit(node); // 先访问根节点，然后根节点就无需入栈了 14. S.push(node->right); // 先push的是右节点，再是左节点 15. S.push(node->left);
16. }
17. }
18.}
preOrder2每次将节点压入栈，然后弹出，压右子树，再压入左子树，在遍历过程中，遍历序列的右节点依次被存入栈，左节点逐次被访问。同一时刻，栈中元素为m-1个右节点和1个最左节点，最高为h。所以空间也为O(h)；每个节点同样被压栈一次，弹栈一次，访问一次，时间复杂度O(n)
1.3 先序遍历伪代码：非递归版本，不用栈，增加指向父节点的指针
1.// 先序遍历伪代码：非递归版本，不用栈，增加指向父节点的指针 2.void preOrder3(TNode* root)
3.{
4. while ( root != NULL ) // 回溯到根节点时为NULL，退出
5. {
6. if( !root->bVisited )
7. { // 判定是否已被访问
8. Visit(root);
9. root->bVisited = true;
10. }
11. if ( root->left != NULL && !root->left->bVisited ) // 访问左子树
12. {
13. root = root->left;
14. }
15. else if( root->right != NULL && !root->right->bVisited ) // 访问右子树
16. {
17. root = root->right;
18. }
19. else // 回溯
20. {
21. root = root->parent;
22. }
23. }
24.}
preOrder3的关键在于回溯。为了回溯增加指向父亲节点的指针，以及是否已经访问的标志位，对比preOrder1与preOrder2，但增加的空间复杂度为O(n)。时间方面，每个节点被访问一次。但是，当由叶子节点跳到下一个要访问的节点时，需要先回溯至父亲节点，再判断是否存在没有被访问过的右子树，如果没有，则继续回溯，直至找到一颗没有被访问过的右子树，这个过程需要很多的时间。每个叶子节点的回溯需要O(h)时间复杂度，叶子节点最多为(2^(h-1))，因此回溯花费的上限为O(h*(2^(h-1))。这个上限应该可以缩小。preOrder3唯一的好处是不需要额外的数据结构-栈。
2.中序遍历
根据上面的先序遍历，可以类似的构造出中序遍历的三种方式。仔细想一下，只有第一种方法改过来时最方便的。需要的改动仅仅调换一下节点访问的次序，先序是先访问，再入栈；而中序则是先入栈，弹栈后再访问。伪代码如下。时间复杂度与空间复杂度同先序一致。
2.1 中序遍历伪代码：非递归版本，用栈实现
1.
2.// 中序遍历伪代码：非递归版本，用栈实现，版本1
3.void InOrder1(TNode* root)
4.{
5. Stack S;
6. while ( root != NULL || !S.empty() )
7. {
8. while( root != NULL ) // 左子树入栈
9. {
10. S.push(root);
11. root = root->left;
12. }
13. if ( !S.empty() )
14. {
15. root = S.pop();
16. Visit(root->data); // 访问根结点
17. root = root->right; // 通过下一次循环实现右子树遍历 18. }
19. }
20.}
第二个用栈的版本却并不乐观。preOrder2能够很好的执行的原因是，将左右节点压入栈后，根节点就再也用不着了；而中序和后序却不一样，左右节点入栈后，根节点后面还需要访问。因此三个节点都要入栈，而且入栈的先后顺序必须为：右节点，根节点，左节点。但是，当入栈以后，根节点与其左右子树的节点就分不清楚了。因此必须引入一个标志位，表示 是否已经将该节点的左右子树入栈了。每次入栈时，根节点标志位为true,左右子树标志位为false。
伪代码如下：
2.2 中序遍历伪代码：非递归版本，用栈实现，模拟递归过程
2.// 中序遍历伪代码：非递归版本，用栈实现，模拟递归过程，版本2
3.void InOrder2(TNode* root)
4.{
5. Stack S;
6. if( root != NULL )
7. {
8. S.push(root);
9. }
10. while ( !S.empty() )
11. {
12. TNode* node = S.pop();
13. if ( node->bPushed )
14. { // 如果标识位为true,则表示其左右子树都已经入栈，那么现在就需要访问该节点了
15. Visit(node);
16. }
17. else
18. { // 左右子树尚未入栈，则依次将 右节点，根节点，左节点 入栈 19. if ( node->right != NULL )
20. {
21. node->right->bPushed = false; // 左右子树均设置false
22. S.push(node->right);
23. }
24. node->bPushed = true; // 根节点标志位为true 25. S.push(node);
26. if ( node->left != NULL )
27. {
28. node->left->bPushed = false;
29. S.push(node->left);
30. }
31. }
32. }
33.}
对比先序遍历，这个算法需要额外的增加O(n)的标志位空间。另外，栈空间也扩大，因为每次压栈的时候都压入根节点与左右节点，因此栈空间为O(n)。时间复杂度方面，每个节点压栈两次，作为子节点压栈一次，作为根节点压栈一次，弹栈也是两次。因此无论从哪个方面讲，这个方法效率都不及InOrder1。
至于不用栈来实现中序遍历。头晕了，暂时不想了。后面再来完善。还有后序遍历，貌似更复杂。对了，还有个层序遍历。再写一篇吧。头都大了。
中序遍历的第三个非递归版本：采用指向父节点的指针回溯。这个与先序遍历是非常类似的，不同之处在于，先序遍历只要一遇到节点，那么没有被访问那么立即访问，访问完毕后尝试向左走，如果左孩子补课访问，则尝试右边走，如果左右皆不可访问，则回溯；中序遍历是先尝试向左走，一直到左边不通后访问当前节点，然后尝试向右走，右边不通，则回溯。（这里不通的意思是：节点不为空，且没有被访问过）
2.3 中序遍历伪代码：非递归版本，不用栈，增加指向父节点的指针
2.// 中序遍历伪代码：非递归版本，不用栈，增加指向父节点的指针
3.void InOrder3(TNode* root)
4.{
5. while ( root != NULL ) // 回溯到根节点时为NULL，退出
6. {
7. while ( root->left != NULL && !root->left->bVisited )
8. { // 沿左子树向下搜索当前子树尚未访问的最左节点
9. root = root->left;
10. }
11. if ( !root->bVisited )
12. { // 访问尚未访问的最左节点
13. Visit(root);
14. root->bVisited=true;
15. }
16. if ( root->right != NULL && !root->right->bVisited )
17. { // 遍历当前节点的右子树
18. root = root->right;
19. }
20. else
21. { // 回溯至父节点
22. root = root->parent;
23. }
24. }
25.}这个算法时间复杂度与空间复杂度与第3个先序遍历的版本是一样的。
3.后序遍历
从直觉上来说，后序遍历对比中序遍历难度要增大很多。因为中序遍历节点序列有一点的连续性，而后续遍历则感觉有一定的跳跃性。先左，再右，最后才中间节点；访问左子树后，需要跳转到右子树，右子树访问完毕了再回溯至根节点并访问之。这种序列的不连续造成实现前面先序与中序类似的第1个与第3个版本比较困难。但是按照第2个思想，直接来模拟递归还是非常容易的。如下：
3.1 后序遍历伪代码：非递归版本，用栈实现，模拟递归过程
1.// 后序遍历伪代码：非递归版本，用栈实现，模拟递归过程2.void PostOrder(TNode* root)
3.{
4. Stack S;
5. if( root != NULL )
6. {
7. S.push(root);
8. }
9. while ( !S.empty() )
10. {
11. TNode* node = S.pop();
12. if ( node->bPushed )
13. { // 如果标识位为true,则表示其左右子树都已经入栈，那么现在就需要访问该节点了
14. Visit(node);
15. }
16. else
17. { // 左右子树尚未入栈，则依次将 右节点,左节点,根节点 入栈 18. if ( node->right != NULL )
19. {
20. node->right->bPushed = false; // 左右子树均设置false
21. S.push(node->right);
22. }
23. if ( node->left != NULL )
24. {
25. node->left->bPushed = false;
26. S.push(node->left);
27. }
28. node->bPushed = true; // 根节点标志位为true 29. S.push(node);
30. }
31. }
32.}和中序遍历的第2个版本比较，仅仅只是把左孩子入栈和根节点入栈顺序调换一下（
有错误，应该是右孩子入栈和根结点入栈顺序调换一下）；这种差别就跟递归版本的中序与后序一样。
4.层序遍历
这个很简单，就不说老。
1.// 层序遍历伪代码：非递归版本，用队列完成 2.void LevelOrder(TNode *root)
3.{
4. Queue Q;
5. Q.push(root);
6.
7. while (!Q.empty())
8. {
9. node = Q.front(); // 取出队首值并访问
10. Visit(node);
11.
12. if (NULL != node->left) // 左孩子入队
13. {
14. Q.push(node->left);
15. }
16. if (NULL != node->right) // 右孩子入队
17. {
18. Q.push(node->right);
19. }
20. }
21.}小结一下：
用栈来实现比增加指向父节点指针回溯更方便；
采用第一个思想，就是跟踪指针移动 用栈保存中间结果的实现方式，先序与中序难度一致，后序很困难。先序与中序只需要修改一下访问的位置即可。
采用第二个思想，直接用栈来模拟递归，先序非常简单；而中序与后序难度一致。先序简单是因为节点可以直接访问，访问完毕后无需记录。而中序与后序时，节点在弹栈后还不能立即访问，还需要等其他节点访问完毕后才能访问，因此节点需要设置标志位来判定，因此需要额外的O(n)空间。
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/kofsky/archive/2008/09/05/2886453.aspx
分享到：
相关推荐
二叉树的非递归遍历 二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历
二叉树的非递归遍历，使用C++实现二叉树的非递归遍历，对正在学习算法的同学应该挺有帮助的
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
Java版二叉树遍历非递归程序，里面写的一般，希望大家喜欢！
用C++写的，包括二叉树的构建，二叉树的先序遍历、中序遍历和后序遍历非递归算法。
C语言实现二叉树的前序遍历（非递归），下载下来看看哦！
二叉树遍历的非递归算法分析与实现二叉树遍历的非递归算法分析与实现
二叉树遍历的非递归操作二叉树遍历的非递归操作
二种非递归实现 二叉树中序遍历： 递归实现 非递归实现 二叉树后序遍历： 递归实现 非递归实现 二叉树层次遍历 二叉树层次创建，创建方法遵循卡特兰数 http://write.blog.csdn.net/postedit/17380455
使用C++模板、类的技术实现了二叉树的中序遍历，在BC3.1已经测试成功
基于C语言编写的递归与非递归方法的二叉树先中后序遍历
C语言二叉树遍历前序非递归算法，简单易懂，正确无误
经典的数据结构问题：二叉树非递归遍历算法实现 二叉树递归遍历算法实现
自己写得二叉树的遍历程序，包括递归遍历，栈的非递归遍历和队列的层次遍历，已在VC中运行通过，希望以此与大家交流交流，如有不妥之处希望大家能帮我修正，本着共同进步的目的。
二叉树先序、中序、后序遍历非递归算法，简述了二叉树的基本算法。
//二叉树的二叉链表存储表示 typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; //左右孩子指针 } BiTNode, *BiTree; typedef struct { BiTree *base; BiTree *top; int stacksize; //当前...
这是数据结构中二叉树的后序遍历的非递归算法的源代码。
二叉树递归与非递归遍历
二叉树的中序、前序、后序的递归、非递归遍历算法
二叉树几种遍历方式的非递归版本 先序遍历 中序遍历 后序遍历 层次遍历