我们可以使用莫里斯遍历的后序？

我访问过很多网站，但无法找到任何Morris postOrder遍历算法。我知道我们可以将Morris算法用于preOrder和inOrder。如果有人将我指向postOrder Morris算法（如果存在），它将非常有帮助。我们可以使用莫里斯遍历的后序？

来源

2016-04-03 kingJ

我会试着解释一下，我们如何使用Morris方法来实现后序遍历。前提条件：在解释后，顺序遍历之前，让我们修改顺序遍历。

在有序遍历中，从根节点开始 1.如果当前节点已经离开了子节点，那么找到它的有序前导节点，并将它作为它的右侧子节点并向左移动根节点。 [找到前辈，在其左侧子树中找到最大元素] 2.如果当前节点没有离开孩子，则打印数据并向右移动。

恢复树：应该注意的主要事情是，在执行步骤1时，我们会达到一个点，前任右孩子本身就是当前节点，只有当整个左孩子关闭时我们才开始打印数据从那里。 [当你发现没有当前节点的左边的孩子] 因此，对于这种情况，我们需要从该节点切下正确的孩子。

void MorriesInorder(BTnode root) { 
if(root == null) return; 
BTnode temp; 
while (root!=null){ 
    //case 2: when left child does not exist 
     if (root.left == null) { 
       print(root.data); 
       root = root.right; 
    }else { 
      //find predecessor 
      temp = root.left; 
      while (temp.right!=null && 
         temp.right!=root) // to check restore case 
        temp = temp.right; 

      if (temp.right == null) //predecessor found, converting 
      { 
         temp.right = root; 
         root = root.left; 
      } else { 
        print root.data; 
        temp.right = null; // cut right child off 
        root = root.right; 
      } 
    } 

}}

所以现在回到原来的问题，我们如何执行Postorder遍历。我们将使用上面的概念进行小的更改以实现后序遍历。首先我们有一个虚拟节点，并将整棵树作为虚拟节点的左边子节点，并使右边的子节点为空。 [为什么？如果我们假设根没有权利孩子然后prinitng左孩子，然后根成为后序遍历，右;）] 现在接下来呢？我们完成了，没有... 只在新树上执行inorder没有任何意义，它仍然打印原始树的次序遍历，其次是虚拟节点。从[在序遍历讨论]壳体2

临界部分

首先删除打印数据：现在密切观察内else块，这一段代码需要注意。由于此临时扩展树是遍历的对象，除了在内部else子句中，在找到临时父项之后，p.left（included）和p（excluded）之间的节点在修改中扩展到右侧树按相反顺序处理。为了在不变的时间内处理它们，节点链被向下扫描，并且正确的引用被反转以引用节点的父节点。然后向上扫描同一链，访问每个节点，并将正确的引用恢复为其原始设置。

//This is Post Order :children before node(L ,R , N) 
void morrisPostorderTraversal(Node *root){ 

// Making our tree left subtree of a dummy Node 
Node *dummyRoot = new Node(0); 
dummyRoot->left = root; 

//Think of P as the current node 
Node *p = dummyRoot, *pred, *first, *middle, *last; 
while(p!=NULL){   

    if(p->left == NULL){ 
     p = p->right; 
    } else{ 
     /* p has a left child => it also has a predeccessor 
      make p as right child predeccessor of p  
     */ 
     pred = p->left; 
     while(pred->right!=NULL && pred->right != p){ 
      pred = pred->right; 
     } 

     if(pred->right == NULL){ 

      // predeccessor found for first time 
      // modify the tree 

      pred->right = p;  
      p = p->left; 

     }else {       

      // predeccessor found second time 
      // reverse the right references in chain from pred to p 
      first = p; 
      middle = p->left;    
      while(middle!=p){    
       last = middle->right; 
       middle->right = first; 
       first = middle; 
       middle = last; 
      } 

      // visit the nodes from pred to p 
      // again reverse the right references from pred to p  
      first = p; 
      middle = pred; 
      while(middle!=p){ 

       cout<<" "<<middle->data; 
       last = middle->right;   
       middle->right = first; 
       first = middle; 
       middle = last; 
      } 

      // remove the pred to node reference to restore the tree structure 
      pred->right = NULL;  
      p = p-> right; 
     } 
    } 
}  
}

来源

2017-02-24 11:21:58 gauramit87

我们可以使用莫里斯遍历的后序？

回答

相关问题