非遞歸郵遞訂單遍歷

Question

我在一些網站上看到了以下郵遞訂單遍歷算法......它似乎是正確的。我只是想驗證這個算法是否正常工作 - 這個算法是否適用於沒有遞歸的後序遍歷？

void postOrderTraversal(Tree *root) 
{ 
    node * previous = null; 
    node * s = null; 
    push(root); 
    while(stack is not empty) 
    { 
     s = pop(); 

     if(s->right == null and s->left == null) 
     { 
      previous = s; 
      process s; 
     } 
     else 
     { 
      if(s->right == previous or s->left == previous) 
      { 
       previous = s; 
       process s; 
      } 
      else 
      { 
       push(s); 
       if(s->right) { push(s->right); } 
       if(s->left) { push(s->left); } 
      } 
     } 
    } 
} 

Answer 1

沒有這裏先前不應該用零 例如啓動：對於具有BST節點5 2 1 3 7 6 8 0 不會考慮爲零，因爲在1其右側爲null並且此時間以前也將是null因此它不會考慮它的左邊的孩子，即0 寫前一個=任何值，但不爲零

Answer 2

嘗試編寫預訂，按序和後序二進制遍歷方法的迭代版本。然後您將看到將相應的遞歸版本轉換爲迭代版本的模式或方法。

關鍵點是粘到一些基本規則：
- 使用節點選擇（例如，currentNode = currentNode->重申循環等前左），用於即時節點遍歷。
- 使用堆棧記住稍後需要訪問或重新訪問的節點。
- 如果某個節點需要「重新訪問」，則檢測/保持該狀態，以便您可以指示下一個迭代中是否需要「處理」下一個節點，或者是否應該在節點可以被處理。

如果你堅持這些規則，你可以esily完成任務。

下面是一個迭代後序遍歷的例子。忽略BinarySearchTree - 適用於任何二叉樹。

public static IEnumerator<BinarySearchTreeNode<T>> GetPostOrderTraverseEnumerator(BinarySearchTreeNode<T> root) 
    { 
     if (root == null) 
     { 
      throw new ArgumentNullException("root"); 
     } 

     Stack<BinarySearchTreeNode<T>> stack = new Stack<BinarySearchTreeNode<T>>(); 

     BinarySearchTreeNode<T> currentNode = root; 

     // If the following flag is false, we need to visit the child nodes first 
     // before we process the node. 
     bool processNode = false; 

     while (true) 
     { 
      // See if we need to visit child nodes first 
      if (processNode != true) 
      { 
       if (currentNode.Left != null) 
       { 
        // Remember to visit the current node later 
        stack.Push(currentNode); 

        if (currentNode.Right != null) 
        { 
         // Remember to visit the right child node later 
         stack.Push(currentNode.Right); 
        } 

        // Visit the left child 
        currentNode = currentNode.Left; 
        continue; 
       } 
       else if (currentNode.Right != null) 
       { 
        // Remember to visit the current node later 
        stack.Push(currentNode); 

        // Visit the right child 
        currentNode = currentNode.Right; 
        continue; 
       } 
      } 

      // Process current node 
      yield return currentNode; 

      // See if we are done. 
      if (stack.Count == 0) 
      { 
       break; 
      } 

      // Get next node to visit from the stack 
      BinarySearchTreeNode<T> previousNode = currentNode; 
      currentNode = stack.Pop(); 

      // See if the next node should be processed or not 
      // This can be determined by the fact that either of the current node's child nodes 
      // has just been processed now. 
      processNode = (previousNode == currentNode.Left || previousNode == currentNode.Right); 
     } 
    } 

Answer 3

這裏是工作的代碼

Stack s=new Stack(); 
    while(true){ 
     if(root!=null){ 
      s.push(root); 
      root=root.left; 
     } 
     else{ 
      if(s.top().right==NULL){ 
       root=s.top(); 
       s.pop(); 
       System.out.println(root.data); 
       if(root==s.top().right){ 
        System.out.println(s.top().data); 
        s.pop(); 
       } 
      } 
     if(!s.empty()) 
      root=s.top().right; 
     else 
      root=NULL; 

     } 
    }