首页 > 代码库 > 二叉树的遍历——Morris

二叉树的遍历——Morris

在之前的博客中,博主讨论过二叉树的经典遍历算法,包括递归和常规非递归算法,其时间复杂度和空间复杂度均为O(n)。Morris算法巧妙地利用了二叉树的线索化思路,将二叉树的遍历算法的空间复杂度降低为O(1),时间复杂度仍然为O(n)。关于该算法的讨论在网上有很多,例如:http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html,在这里,博主且讲讲自己的理解。各位看官可以结合本随笔和上面的帖子来加深对于Morris算法的理解。

1. 中序遍历

  分析:中序遍历的基本顺序为leftTree, root,rightTree,而我们总是先接触到root节点,然后再接触leftTree和rightTree,用stack可以很方便地保存已接触到的节点,但这里却不能用!只能再考虑其他思路。这里,我们抓住中序遍历的本质:要想访问root节点,必须先访问其leftTree。但如果不借助stack,在访问了leftTree之后,又如何能再次访问root呢?二叉树的线索化就给了我们一个很好的思路。我们知道,二叉树中节点的空白指针有2n-(n-1)=n+1个,这便是一个可以利用的极好条件。

技术分享

  从图中可以看出,我们可以在leftTree中找到root节点在中序遍历下的前驱节点pre,将该前驱节点pre的右指针指向root节点,那么,下次在访问完leftTree之后,便能通过前驱节点pre回到root节点。由此,便能不间断访问完全部节点。以下见算法:

 1 void inOrderTraverse(TreeNode *root){//Morris
 2   TreeNode *cur = root;
 3   TreeNode *pre = nullptr;
 4   while(cur){
 5     if(cur->left){
 6       pre = cur->left;
 7       while(pre->right && pre->right != cur){
 8         pre = pre->right;
 9       }
10       if(!pre->right){//first touch
11         pre->right = cur;//connect root
12         cur = cur->left;
13       }else{//second touch
14         pre->right = nullptr;//disconnect root
15         visit(cur);
16         cur = cur->right;
17       }
18     }else{
19       visit(cur);
20       cur = cur->right;
21     }
22   }
23 }

2. 前序遍历

  前序遍历的思路和中序遍历的思路完全相似,只是访问时机的不同。在前序遍历中,root节点需要先访问到,然后再访问其leftTree和rightTree。如图:

技术分享

 1 void preOrderTraverse(TreeNode *root){//Morris
 2   TreeNode *cur = root;
 3   TreeNode *pre = nullptr;
 4   while(cur){
 5     if(cur->left){
 6       pre = cur->left;
 7       while(pre->right && pre->right != cur){
 8         pre = pre->right;
 9       }
10       if(!pre->right){//first touch
11         pre->right = cur;
12         visit(cur);//visit root
13         cur = cur->left;
14       }else{
15         pre->right = nullptr;
16         cur = cur->right;
17       }
18     }else{
19       visit(cur);//visit root
20       cur = cur->right;
21     }
22   }
23 }

3. 后续遍历

  分析:在之前讨论二叉树的非递归后续遍历算法中,由于后续遍历(leftTree,rightTree, root)算法的独特性,root节点需要最后才能被访问。因此,如果先将rightTree的最后访问节点指向root,实现线索,那么leftTree将不好处理,因为leftTree要先于rightTree访问。因此,需要稍微调整一下思路。同样,利用上诉线索化的思路来改造原算法。先上图:

技术分享

  在了解完前序和中序遍历思路后,上图应该是很好懂的。F节点为root节点的前驱节点,第一次访问时需要将其right指针指向root节点,第二次时重新置空。在上图中,对于后续遍历,访问顺序为A->B->C->D->E->F->rightTree->root(无需区分节点和子树)。那么,思路便开始清晰起来,对于leftTree,先访问A,B,C,再从root节点的前驱节点pre逆向访问再root节点的左节点,便能正常实现逆序访问,这也是正是后续遍历的正确访问顺序。要实现从前驱节点pre到root->left的逆序访问,需要一点额外的操作,先将D->F视为单链表逆转,然后访问,最后再次逆转还原即可。最后,对于root节点和rightTee,需要增加一个额外的伪root节点,来实现和(root,leftTree)相同的结构,即(preRoot,tree)。以下见代码: 

 1 void reverseRightTreePath(TreeNode *from, TreeNode *to){
 2   TreeNode *temp = nullptr;
 3   TreeNode *next = from->right;
 4   from->right = nullptr;
 5   while(from != to){
 6     temp = next->right;
 7     next->right = from;
 8     from = next;
 9     next = temp;
10   }
11 }
12 void visitReverseRightTreePath(TreeNode *from, TreeNode *to){
13   reverseRightTreePath(from, to);
14   TreeNode *temp = to;
15   while(temp != from){
16     visit(temp);
17     temp = temp->right;
18   }
19   visit(temp);
20   reverseRightTreePath(to, from);
21 }
22 void postOrderTraverse(TreeNode *root){
23   TreeNode *preRoot = new TreeNode(0);
24   preRoot->left = root;
25   TreeNode *cur = preRoot;
26   TreeNode *pre = nullptr;
27 
28   while(cur){
29     if(cur->left){
30       pre = cur->left;
31       while(pre->right && pre->right != cur){
32         pre = pre->right;
33       }
34       if(!pre->right){
35         pre->right = cur;
36         cur = cur->left;
37       }else{
38         visitReverseRightTreePath(cur->left, pre);//Only visit in the second touch
39         pre->right = nullptr;
40         cur = cur->right;
41       }
42     }else{
43       cur = cur->right;
44     }
45   }
46 }

二叉树的遍历——Morris