二元搜索樹的非遞歸地板法

Question

我一直試圖讓這個工作，但雖然它適用於大多數的輸入有時它會給出錯誤的輸出。我花了一些時間調試代碼，看起來問題是，當我得到一個小於根的節點但大於根節點下的左節點。

如果右子樹中沒有節點是該密鑰的發言節點，如何遍歷右子樹並仍然返回正確的密鑰？

Answer 1

回想一下，如果你遞歸地做任何事情，它可以被轉換成迭代。

讓我們來考慮一個格式良好的BST，它應該是樹中小於或等於您的密鑰的最小元素。我們所要做的就是遍歷樹來獲取它。

讓我們遞歸地實現它，以便我們可以在迭代和遞歸之間梳理出一些重要的推論。

// Assuming non-null root node with method declaration 
private Node floor(Node root, Key key, Node lowestNode) { 
    if(key.compareTo(root.getKey()) <= 0) { 
     if(root.getLeft() != null) { 
      return floor(root.getLeft(), key, lowestNode); 
     } else { 
      return root.compareTo(lowestNode) < 0 ? root : lowestNode; 
     } 
    } else { 
     if(root.getRight() != null) { 
      lowestRightNode.add(root); 
      return floor(root.getRight(), key, lowestNode); 
     } else { 
      return lowestNode; 
    } 
} 

讓我們來看看成功的條件。

• 如果我們比較節點小於或等於我們的關鍵價值：
  • 如果我們有一個左孩子，有什麼東西要小。沿着樹的左半邊向下走。
  • 否則，我們在場 - 這意味着我們處於節點的價值小於或等於我們的關鍵。把它返還。
• 否則（我們的節點具有比我們的關鍵更大的值）：
  • 如果我們有一個正確的孩子，有一個機會，我們的工作還沒有完成（有什麼地方更小）。我們想保留它，因爲我們可以離開樹，所以讓我們存儲它，然後遍歷樹的右半部分。
  • 否則，我們已經從樹上掉下來了。返回我們跟蹤的最小元素。

一個例子可以是這個樣子：

 9 
    /\ 
     3 14 
    /\ 
    1 2 

隨着12的關鍵：

• 與9.比較我們是更大的。將9存儲在我們的最低節點變量中，遞歸正確。
• 與14比較我們比較小，但我們沒有左孩子。我們的價值14比較9和9較小，所以我們返回與9

節點。如果我們想這個轉換成迭代，然後想想你的起點，你的條件檢查，和您的增量步驟。

• 起點：一個非空節點
• 條件檢查：
  • key.compareTo(root.getKey()) <= 0
    • root.getLeft() != null
      • 繼續
    • root.compareTo(lowestRightNode) < 0 ? root : lowestRightNode
      • 終端
  • 別的
    • root.getRight() != null
      • 存儲臨時值，然後繼續
    • return lowestRightNode
      • 終端

密切注意你的持續狀態，其他什麼工作，你必須做跟蹤到目前爲止你見過的最低點（僅適用於中就是右手邊）。

^{*：有些遞歸操作比更痛苦當然要比別人轉換。}