基本前綴樹實現問題

我已經實現了基本前綴樹或「trie」。這個trie由這樣的節點組成：基本前綴樹實現問題

// pseudo-code 
struct node { 
    char c; 
    collection<node> childnodes; 
};

說我給我的trie添加下列單詞：「Apple」，「Ark」和「Cat」。現在當我查找「Ap」和「Ca」前綴時，我的trie的「bool containsPrefix（string prefix）」方法將正確返回true。

現在我正在執行「bool containsWholeWord（string word）」方法，它將爲「Cat」和「Ark」返回true，但在「App」（以上示例）中返回false。

一個trie中的節點有某種「endOfWord」標誌常見嗎？這將有助於確定查找的字符串是否實際上是輸入到trie中的整個單詞而不僅僅是前綴。

乾杯！

來源

2011-06-14 MrDatabase

如果您需要同時存儲「App」和「Apple」，但不是「Appl」，那麼是的，您需要使用endOfWord標誌。

或者，您可以通過（有時）具有相同字符的兩個節點將其適用於您的設計。因此，「Ap」必須爲childnodes：葉節點「p」和內部節點「p」帶有子節點「l」。

來源

2011-06-15 12:03:51

密鑰的結尾通常通過葉節點表示。可以是：

子節點是空的;或
你有一個分支，有一個關鍵字的前綴和一些子節點。

您的設計沒有葉/空節點。嘗試用例如一個null。

來源

2011-06-14 20:17:22

感謝您的回覆。不過，我通過檢查空的childnodes集合來嘗試指示葉節點（就像你提到的那樣）。這並不能解決以下問題：將「Apple」插入到trie中。將「Appl」插入到trie中。詢問「蘋果」是否是一個整體詞。在這個例子中（假設你使用上面提到的方法檢查葉節點）然而，如果「Appl」是一個完整的單詞錯誤地返回錯誤，因爲「l」不是葉節點。添加「endOfWord」標誌修復了這個問題。 – MrDatabase 2011-06-14 20:49:33

基本前綴樹實現問題

回答

相關問題