基於堆棧的樹遍歷的時間複雜度

Question

以下執行二叉樹遍歷的時間複雜度是多少？

void Tree::nonRecInOrder() 
{ 
    // nonrecursive inOrder Traversal using Stack 
    Stack< TreeNode* > s ; // declare and initialize stack 
    TreeNode* currentNode = root ; 

    while(true) 
    { 
     while(currentNode) 
     { 
      // move down leftChild fields 
      s.add(currentNode) ; 
      currentNode = currentNode->leftChild ; 
     } 

     if(! s.isEmpty()) // stack is not empty 
     { 
      currentNode = *s.del(currentNode) ; // delete from stack 
      cout << currentNode->data ; 
      currentNode = currentNode->rightChild ; 
     } 
     else 
     { 
      break ; 
     } 
    }  
} 

你能否解釋一下如何計算複雜性？

Answer 1

表徵困難函數的大O複雜性的一種方法是考慮它訪問的某些資源，然後限制該資源被訪問的次數。在這種情況下，當您進行樹遍歷時，您可能會考慮每個節點從堆棧中被壓入或彈出的次數。這是一個很好的界限的原因是，這個函數的所有努力工作 - 內部循環通過一系列節點下降，外部循環處理堆棧中的最頂層 - 可能受到節點被推動的次數的限制進入堆棧或從堆棧彈出。這是因爲當堆棧爲空時，最外層的循環終止，所以它不能運行多次，而堆棧有一些東西壓到它上面，而最內層的循環的工作與按壓堆棧的次數成正比循環過程。

讓我們看看我們如何限制這些數量。第一個問題是每個節點可以將多少次加入到堆棧中。那麼，如果一個節點或者它的一個祖先沿着一條只有左路的路徑是循環開始執行時的當前節點，那麼它只會被添加到棧中。這可能發生多少次？我的說法是這最多隻發生一次。這個證明是基於樹中節點深度的歸納。我們使用這樣的觀察：如果一個節點是堆棧中節點的直接右子節點，那麼只會再次選擇該節點作爲當前節點。作爲歸納的基本情況，如果節點是根（深度爲零），則不能再次選擇該節點，因爲它沒有父節點。對於歸納步​​驟，如果確實沒有深度爲d的節點可以被選擇爲當前節點的兩倍，那麼深度d + 1中的節點不能被選擇兩次，因爲深度d + 1處的節點僅在選擇其父母時被選擇再次，但通過歸納假設，我們知道這不是真的。因此，我們沒有選擇任何節點作爲當前節點的兩倍。我們通過一個簡單的觀察來跟蹤這個問題，即沒有一個左子節點可以作爲循環開始時的當前節點，因爲當前節點是根節點（不是左子節點），或者是某個節點的右子節點。這個說法，再加上沒有兩次訪問節點這一事實，意味着一個節點最多隻能添加到隊列中一次，這種情況發生在最高的左祖先變爲當前節點時發生。

這也給了我們一個可能的出隊數量的限制，因爲出隊數量不能超過入隊數量。由於每個節點最多隻有一次入隊，因此最多也只能出隊一次。爲了完成這些工作，我們知道整個函數的複雜性受到排隊和出隊數量的限制，所以複雜度爲O（n），其中n是節點數量。

Whe！分析起來並不好玩。我更喜歡遞歸版本。 :-)