二叉树非递归遍历

二叉树非递归遍历收藏1. 先序遍历从递归说起void preOrder(TNode* root)if (root != NULL)Visit(root);preOrder(root->left); preOrder(root->right); 递归算法非常的简单。先访问跟节点，然后访问左节点，再访问右节点。如果不 用递归，那该怎么做呢？仔细看一下递归程序，就会发现，其实每次都是走树的 左分支(left),直到左子树为空，然后开始从递归的最深处返回，然后开始恢复 递归现场，访问右子树。其实过程很简单：一直往左走root->left->left->left->null，由于是先序 遍历，因此一遇到节点，便需要立即访问；由于一直走到最左边后，需要逐步返 回到父节点访问右节点，因此必须有一个措施能够对节点序列回溯。有两个办法：1. 用栈记忆：在访问途中将依次遇到的节点保存下来。由于节点出现次序与恢复 次序是反序的，因此是一个先进后出结构，需要用栈。使用栈记忆的实现有两个版本。第一个版本是模拟递归的实现效果，跟LX讨论 的，第二个版本是直接模拟递归。2. 节点增加指向父节点的指针：通过指向父节点的指针来回溯(后来发现还要需 要增加一个访问标志，来指示节点是否已经被访问，不知道可不可以不用标志直 接实现回溯？想了一下，如果不用这个标志位，回溯的过程会繁琐很多。暂时没 有更好的办法。)(还有其他办法可以回溯么？)这3 个算法伪代码如下，没有测试过。 先序遍历伪代码：非递归版本，用栈实现，版本 1/ 先序遍历伪代码：非递归版本，用栈实现，版本 1void preOrder1(TNode* root)Stack S;while (root != NULL) | !S.empty()if (root != NULL)Visit(root);S.push(root); / 先序就体现在这里了，先访问，再入栈root = root->left; / 依次访问左子树elseroot = S.pop(); / 回溯至父亲节点root = root->right;preOrder1 每次都将遇到的节点压入栈，当左子树遍历完毕后才从栈中弹出最 后一个访问的节点，访问其右子树。在同一层中，不可能同时有两个节点压入栈， 因此栈的大小空间为 O(h)，h 为二叉树高度。时间方面，每个节点都被压入栈 一次，弹出栈一次，访问一次，复杂度为 O(n)先序遍历伪代码：非递归版本，用栈实现，版本2/ 先序遍历伪代码：非递归版本，用栈实现，版本 2void preOrder2(TNode* root)if ( root != NULL)Stack S;S.push(root);while (!S.empty()TNode* node = S.pop();Visit(node); / 先访问根节点，然后根节点就无需入栈了 S.push(node->right); / 先 push 的是右节点，再是左节点 S.push(node->left);preOrder2 每次将节点压入栈，然后弹出，压右子树，再压入左子树，在遍历 过程中，遍历序列的右节点依次被存入栈，左节点逐次被访问。同一时刻，栈中 元素为m-1个右节点和1个最左节点，最高为h。所以空间也为0(h)；每个 节点同样被压栈一次，弹栈一次，访问一次，时间复杂度 O(n) 先序遍历伪代码：非递归版本，不用栈，增加指向父节点的指针/ 先序遍历伪代码：非递归版本，不用栈，增加指向父节点的指针void pre0rder3(TNode* root)while ( root != NULL ) /回溯到根节点时为NULL，退出if( !root->bVisited ) / 判定是否已被访问Visit(root);root->bVisited = true;if ( root->left != NULL && !root->left->bVisited ) / 访问左 子树root = root->left;else if( root->right != NULL && !root->right->bVisited ) / 访问 右子树root = root->right;else / 回溯root = root->parent;preOrder3 的关键在于回溯。为了回溯增加指向父亲节点的指针，以及是否已经访问的标志位，对比preOrderl与preOrder2，但增加的空间复杂度为 0( n)。时间方面，每个节点被访问一次。但是，当由叶子节点跳到下一个要访 问的节点时，需要先回溯至父亲节点，再判断是否存在没有被访问过的右子树， 如果没有，则继续回溯，直至找到一颗没有被访问过的右子树，这个过程需要很 多的时间。每个叶子节点的回溯需要0(h)时间复杂度，叶子节点最多为 (2人(h-1),因此回溯花费的上限为0(h*(2人(h-1)。这个上限应该可以缩小。 preOrder3 唯一的好处是不需要额外的数据结构-栈。2. 中序遍历 根据上面的先序遍历，可以类似的构造出中序遍历的三种方式。仔细想一下，只 有第一种方法改过来时最方便的。需要的改动仅仅调换一下节点访问的次序，先 序是先访问，再入栈；而中序则是先入栈，弹栈后再访问。伪代码如下。时间复 杂度与空间复杂度同先序一致。/ 中序遍历伪代码：非递归版本，用栈实现，版本 1void InOrder1(TNode* root)Stack S;while ( root != NULL | !S.empty() )while( root != NULL )/ 左子树入栈S.push(root);root = root->left;if ( !S.empty() )root = S.pop();Visit(root->data); / 访问根结点root = root->right; / 通过下一次循环实现右子树遍历第二个用栈的版本却并不乐观。preOrder2能够很好的执行的原因是，将左右 节点压入栈后，根节点就再也用不着了；而中序和后序却不一样，左右节点入栈 后，根节点后面还需要访问。因此三个节点都要入栈，而且入栈的先后顺序必须 为：右节点，根节点，左节点。但是，当入栈以后，根节点与其左右子树的节点 就分不清楚了。因此必须引入一个标志位，表示是否已经将该节点的左右子树入 栈了。每次入栈时，根节点标志位为true,左右子树标志位为false。伪代码如下：/ 中序遍历伪代码：非递归版本，用栈实现，版本2void InOrder2(TNode* root)Stack S;if( root != NULL )S.push(root);while ( !S.empty() )TNode* node = S.pop();if ( node->bPushed )/如果标识位为true,则表示其左右子树都已经入栈，那么现在就需要访问该节点了Visit(node);else/ 左右子树尚未入栈，则依次将 右节点，根节点，左节点 入栈if ( node->right != NULL )node->right->bPushed = false; / 左右子树均设置为 falseS.push(node->right);node->bPushed = true; / 根节点标志位为 trueS.push(node);if ( node->left != NULL )node->left->bPushed = false;S.push(node->left);对比先序遍历，这个算法需要额外的增加0(n)的标志位空间。另外，栈空间也 扩大，因为每次压栈的时候都压入根节点与左右节点，因此栈空间为0(n)。时 间复杂度方面，每个节点压栈两次，作为子节点压栈一次，作为根节点压栈一次， 弹栈也是两次。因此无论从哪个方面讲，这个方法效率都不及 In0rder1。至于不用栈来实现中序遍历。头晕了，暂时不想了。后面再来完善。还有后序遍 历，貌似更复杂。对了，还有个层序遍历。再写一篇吧。头都大了。9.8续 中序遍历的第三个非递归版本：采用指向父节点的指针回溯。这个与先序遍历是 非常类似的，不同之处在于，先序遍历只要一遇到节点，那么没有被访问那么立 即访问，访问完毕后尝试向左走，如果左孩子补课访问，则尝试右边走，如果左 右皆不可访问，则回溯；中序遍历是先尝试向左走，一直到左边不通后访问当前 节点，然后尝试向右走，右边不通，则回溯。(这里不通的意思是：节点不为空， 且没有被访问过)/ 中序遍历伪代码：非递归版本，不用栈，增加指向父节点的指针void In0rder3(TNode* root)while ( root != NULL ) /回溯到根节点时为NULL，退出while ( root->left != NULL && !root->left->bVisited )/ 沿左子树向下搜索当前子树尚未访问的最左节点root = root->left;if ( !root->bVisited )/ 访问尚未访问的最左节点Visit(root);root->bVisited=true;if ( root->right != NULL && !root->right->bVisited )/ 遍历当前节点的右子树root = root->right;else/ 回溯至父节点root = root->parent;这个算法时间复杂度与空间复杂度与第 3 个先序遍历的版本是一样的。3. 后序遍历 从直觉上来说，后序遍历对比中序遍历难度要增大很多。因为中序遍历节点序列 有一点的连续性，而后续遍历则感觉有一定的跳跃性。先左，再右，最后才中间 节点；访问左子树后，需要跳转到右子树，右子树访问完毕了再回溯至根节点并 访问之。这种序列的不连续造成实现前面先序与中序类似的第1 个与第3个版 本比较困难。但是按照第 2 个思想，直接来模拟递归还是非常容易的。如下： / 后序遍历伪代码：非递归版本，用栈实现void PostOrder(TNode* root)Stack S;if( root != NULL )S.push(root);while ( !S.empty() )TNode* node = S.pop();if ( node->bPushed ) / 如果标识位为 true, 则表示其左右子树都已经入栈，那么现在就需 要访问该节点了Visit(node);else / 左右子树尚未入栈，则依次将 右节点 , 左节点 ,根节点 入栈if ( node->right != NULL )node->right->bPushed = false; / 左右子树均设置为 false S.push(node->right);if ( node->left != NULL )node->left->bPushed = false;S.push(node->left);node->bPushed = true; / 根节点标志位为 trueS.push(node);和中序遍历的第 2 个版本比较，仅仅只是把左孩子入栈和根节点入栈顺序调换 一下；这种差别就跟递归版本的中序与后序一样。4. 层序遍历 这个很简单，就不说老。/ 层序遍历伪代码：非递归版本，用队列完成 void LevelOrder(TNode *root)Queue Q;Q.push(root);while (!Q.empty()node = Q.front(); / 取出队首值并访问 Visit(node);if (NULL != node->left) / 左孩子入队 Q.push(node->left);if (NULL != node->right) / 右孩子入队 Q.push(node->right);小结一下： 用栈来实现比增加指向父节点指针回溯更方便； 采用第一个思想，就是跟踪指针移动 用栈保存中间结果的实现方式，先序与中 序难度一致，后序很困难。先序与中序只需要修改一下访问的位置即可。