通過修改莫里斯遍歷的PreOrder和PostOrder遍歷

Question

莫里斯遍歷對O（n）時間和O（1）空間的InOrder遍歷很有效。是否有可能通過改變一些使用相同算法實現PreOrder和PostOrder遍歷的東西。

Answer 1

我知道使用morison Algo預訂的解決方案。

這裏是Java代碼

public static void morisonPreOrder(TreeNode root) { 
    TreeNode curr = root, tmp=null; 

    while (curr != null) { 
     if(curr.leftNode == null) { 
      System.out.print(curr.value + " "); 
      curr = curr.rightNode; 
     } else { 
      tmp = curr.leftNode; 
      while (tmp.rightNode != null && tmp.rightNode != curr) { 
       tmp = tmp.rightNode; 
      } 

      if(tmp.rightNode == null) { 
       System.out.print(curr.value + " "); 
       tmp.rightNode = curr; 
       curr = curr.leftNode; 
      } else { 
       tmp.rightNode = null; 
       curr = curr.rightNode; 
      } 
     } 
    } 
} 

Answer 2

下面是使用改性莫里斯遍歷預先序遍歷的代碼示例。

您可以使用類似的方式修改右前任的左側鏈接以進行後續訂單遍歷。

我沒有時間測試代碼。如果此代碼中出現錯誤，請告訴我。

void preOrderNonRecursive(BSTNode* root) 
{ 
    if(!root) 
     return; 
    BSTNode* cur = root; 

    while(cur) 
    { 
     bool b = false; 
     BSTNode* pre = NULL; 
     if (cur->left) 
     { 
      pre = cur->left; 
      while(pre->right && pre->right != cur) 
       pre = pre->right; 
      if(!pre->right) 
      { 
       pre->right = cur; 
       b = true; 
      }    
      else 
       pre->right = NULL; 
     } 
     else 
      printf("%d\n",cur->val); 

     if(b) 
     { 
      printf("%d\n",cur->val); 
      cur = cur->left;   
     } 
     else    
      cur = cur->right; 
    } 
} 

Answer 3

/預購實現無堆和遞歸/

private static void morrisPreorder(){ 
     while(node != null){ 
      System.out.println(node.getData()); 
      if (node.getLeftNode() == null){ 
       node = node.getRightNode(); 
      } else { 
       Node rightnode = node.getRightNode(); 
       Node current = node.getLeftNode(); 
       while(current.getRightNode() != null && current.getRightNode().getData() != node.getData()) 
        current = current.getRightNode(); 
       if(current.getRightNode() == null){ 
        current.setRightNode(node.getRightNode()); 
        node = node.getLeftNode(); 
       } else { 
        node = node.getRightNode(); 
       } 
      } 
     } 
    } 

Answer 4

我不認爲我們可以實現使用線程的職務序列。 在發佈後，我們必須遍歷孩子和父母。 我們可以從孩子到家長建立了聯繫，但在那之後，我們不能去了這個家長怎麼把他們都沒有聯繫。（一個點，左子和一個在它的右邊子無朝上）

   1 
      /\ 
      2 3 
     /\ 
     4 5 

我們可以在指向節點5的4的右邊節點上創建一個線程。 我們可以在5的右邊節點上創建一個指向節點2的線程。

但在節點2沒有空指針來創建任何線程。節點2的指針指向節點4 & 5.

Answer 5

上面已經回答了前序遍歷。

對於後序遍歷，答案也是「是」。

您唯一需要修改： 1.當前身的右子是當前節點，右子爲null，從當前節點的左子反向輸出的所有節點設置爲前身 。 2. 設置一個虛擬節點並將其左邊的子設置爲樹的根。

的Java代碼寫在這裏：

private void printPostTraverse(List<Integer> traverseList, TreeNode start, TreeNode end) { 
     TreeNode node = start; 
     int insertIndex = traverseList.size(); 
     while (node != end) { 
      traverseList.add(insertIndex, node.val); 
      node = node.right; 
     } 
     traverseList.add(insertIndex, node.val); 
    } 

    public List<Integer> postorderMorrisTraversal(TreeNode root) { 
     List<Integer> traverseList = new ArrayList<>(); 
     TreeNode dummy = new TreeNode(-1); 
     dummy.left = root; 
     TreeNode cur = dummy, prev = null; 
     while (cur != null) { 
      if (cur.left == null) { 
       cur = cur.right; 
      } else { 
       prev = cur.left; 
       while (prev.right != null && prev.right != cur) 
        prev = prev.right; 

       if (prev.right == null) { 
        prev.right = cur; 
        cur = cur.left; 
       } else { 
        // Modification on get the traversal list 
        printPostTraverse(traverseList, cur.left, prev); 
        prev.right = null; 
        cur = cur.right; 
       } 
      } 
     } 
     return traverseList; 
    }