精妙的Morris二叉树遍历算法

arron刘

今天介绍一种精妙的无堆栈，O(1)空间的二叉树遍历算法：Morris遍历，它是Morris发明的。

大家都很熟悉用递归和堆栈来实现二叉树的遍历，比如，前序遍历，中序遍历，后序遍历。但Morris 遍历，使用无堆栈，O(1) 空间进行二叉树遍历。它的原理很简单，利用所有叶子结点的右指针，指向其后继结点，组成一个环，在第二次遍历到这个结点时，由于其左子树已经遍历完了，则访问该结点。

算法伪码：

MorrisInOrder()：

while 没有结束

   如果当前节点没有左后代

     访问该节点

     转向右节点

   否则

     找到左后代的最右节点，且使最右节点的右指针指向当前节点

     转向左后代节点

C++实现：

void bst_morris_inorder(struct bst_node *root)  {  

   struct bst_node *p = root, *tmp;

   while (p) {  

       if (p->left == NULL) {  

           printf("%d ", p->key);  

           p = p->right;  

       }  

       else {  

           tmp = p->left;  

           while (tmp->right != NULL && tmp->right != p)  

               tmp = tmp->right;  

           if (tmp->right == NULL) {  

               tmp->right = p;  

               p = p->left;  

           }  

           else {  

               printf("%d ", p->key);  

               tmp->right = NULL;  

               p = p->right;  

           }  

       }  

   }  

}  

Template实现：

算法示例：

思考题：

怎么实现Morris前序遍历？后序遍历？

arron刘

没有人关注么？

pandaiam

关注
先mark下,有空看.

weishuo1999

嗯，挺不错的算法，但是貌似好多书上都有这个算法的。

cjaizss

恩，经典算法之一

starwing83

这个算法的优势貌似就在于，不需要重复计算右节点了。

看看一般的二叉树遍历无栈算法：

while 没有结束:
   后续节点 <- 得到后续节点(本节点);
   if 没有后续节点:
      break;
   访问本节点
   本节点 <- 后续节点

得到后续节点(本节点):
   如果 本节点有左节点：
     返回 左节点
   如果 本节点有右节点：
     返回 右节点
   找到本节点是左节点的有右节点的祖先
     返回 祖先的右节点
   返回 无节点

注意到这里有个回溯的过程：需要反复去寻找祖先的右节点，而这个算法巧妙地利用了最右节点的右节点一定是NULL，拿最右节点节点的右节点当栈来缓存下一个需要访问的节点，从而避免了反复的回溯，使得在空间O(1)的情况下，时间也是O(n)

不过问题是，这需要（临时）修改树结构，如果不能保证对树结构进行遍历的同时不对树结构做任何修改（比如红黑树的调整遍历），那么这个算法就没有用武之地了。

starwing83

对了，应该说明一下，在现代的CPU优化下，能写递归的话还是写递归最好。主要原因是递归最终还是记录下了当前的所有的历史，因此肯定比任何的非递归代码都快（所谓用栈避免递归也算在这里）。本质是递归遍历树就是拿空间来换时间，避免对“左元素的最右节点”这样的计算——虽然这种计算平摊下来是O(1)，但是依然重新访问了一遍元素的。所以呢，简单的算法往往比精妙的算法更实用。

当然，在一些受限的环境下，这种算法还是大有施展之地的。

starwing83

对了，应该说明一下，在现代的CPU优化下，能写递归的话还是写递归最好。主要原因是递归最终还是记录下了当前的所有的历史，因此肯定比任何的非递归代码都快（所谓用栈避免递归也算在这里）。本质是递归遍历树就是拿空间来换时间，避免对“左元素的最右节点”这样的计算——虽然这种计算平摊下来是O(1)，但是依然重新访问了一遍元素的。所以呢，简单的算法往往比精妙的算法更实用。

当然，在一些受限的环境下，这种算法还是大有施展之地的。

emperor9

点评：
      本吊以为打一次酱油就可以用几天的，不曾想lz天天打酱油。这种出现在university课本中的东东拿到这里，除了被众屌丝鄙视之外还有任何其他作用。且，就算是打酱油，也不能随意兑水吧，Knuth-Morris-Pratt不是可以随便略写的。
      基于各种原因，本吊很诚恳的建议lz好好的把活动区那一亩三分地耕耘开，游手好闲，四处游荡是权志龙的特征。。。

yulihua49

emperor9 发表于 2013-08-05 18:35
点评：
      本吊以为打一次酱油就可以用几天的，不曾想lz天天打酱油。这种出现在university课本中的东东 ...

反对无故贬低楼主。
楼主及其这一类技术宣讲这对我等菜鸟十分有帮助，欢迎此类知识普及贴，论坛的重要功能就是交流知识。尤其对我等不读书不看报的白痴，受益匪浅。