二進制搜索樹中的重複項

Question

處理二進制搜索樹中重複項的優雅方式是什麼？假設每個鍵都有幾個不同的關聯值。我需要做的是按順序遍歷所有值。所以如果我有2個值A和B與關鍵字1和一個值C與關鍵字2，我想得到對：（1，A），（1，B），（2，C），當調用類似TreeIterator.next（）;

我能想到的：

• 每個節點有一個鍵和值的陣列，其中使用相同的密鑰值去
• 每個節點都有一個visited標誌

任何其他建議？作爲一般指導原則，我希望Tree實現儘可能抽象。

Answer 1

這聽起來像基本上你做想要每個鍵的值的列表，是的。所以添加到地圖的過程是：

• 是否存在關鍵？
  • 如果是這樣，請將值添加到現有列表中。
  • 如果沒有，創建在適當的點在樹中的一個新節點（正常），並用一個數值的清單開始

當在地圖上進行迭代，你的一般模式是：

• 收率從左側節點的所有值（較小的鍵）
• 收率該節點的所有值 - （鍵，值1），（鍵，值2）等
• 收率從所有值中正確的節點（大鍵）

當然，如果你不需要自己實現了學習的目的，你可以使用現成的多重映射，如Guava的TreeMultimap。如果你是實施自我教育，我會開始實施一個「正常」的二進制搜索地圖，然後從那裏繼續。