字典分類與特里

enter image description here 根據維基百科，關於特里：字典分類與特里

一組鍵的字典分類可以用一個簡單的基於特里樹的算法來完成如下：

插入一個trie中的所有密鑰。

通過預順序遍歷來輸出trie中的所有密鑰，這會導致按字典順序遞增的輸出。

不過，這是我與我的標準特里執行測試：

Trie trie = new Trie(); 
trie.add("doll"); 
trie.add("ball"); 
trie.add("bat"); 
trie.add("dork"); 
trie.add("dorm"); 
trie.add("send"); 
trie.add("sense"); 
trie.add("sent");

預購打印：

 public List<String> allWords(){ 

    List<String> words = new ArrayList<String>(); 

    if(root == null){ 
     return words; 
    } 

    StringBuilder prefix = new StringBuilder(); 
    getAllWords(root.children,prefix,words); 

    return words; 
} 

// depth first search 
private void getAllWords(List<TrieNode> children, StringBuilder prefix, List<String> words){ 

    for(int i= 0; i<children.size(); i++){ 
     TrieNode child = children.get(i); 
     if(!child.isWord_){ 
      prefix.append(child.data_); 
      allWordsHelper(child.children, prefix, words); 
     }else{ 
      prefix.append(child.data_); 
      words.add(prefix.toString()); 
     } 
     prefix.deleteCharAt(prefix.length()-1); 
    } 
}

和輸出順序是：doll dork dorm ball bat send sense sent

'詞典排序'是什麼意思？看起來輸出順序更多地與插入順序相關，而不是詞典順序。我錯了嗎？以此樹爲例，預訂打印輸出將是「對茶十個旅店」。字典順序在哪裏？

來源

2014-01-28 user697911

您是否正在進行預購遍歷打印輸出時？ –

是的，預購。由於首先插入了「娃娃」，所以即使在預購中它也必須先輸出。在根源下，第一級角色是'd b s'。通過預購，首先打印帶有'd'前綴的所有單詞。 – user697911

想想上面描述的標準Trie數據結構和2步算法，沒有任何信息來保證字典排序。這怎麼可能？ – user697911

說關於辭書使用嘗試排序正確的方法是：

在特里樹節點的序是一樣的字符串，他們代表假設一個節點的孩子們的字典順序由排序邊緣標籤。

現在，如果您在您的代碼中嘗試了這一點，預順序遍歷應該爲您提供字典順序的字符串。

這裏是具有一個例子參考：http://www.cs.helsinki.fi/u/tpkarkka/opetus/12s/spa/lecture02.pdf

來源

2014-12-17 09:13:22 Lanc

據我來說，這應該是Inorder遍歷。可以遍歷trie，使得所有具有小於root值的鍵的分支首先被處理，然後打印root的值，最後所有的值都大於root的值。這是標準inorderinorder遍歷，但我想要做的唯一的一點是，你將不得不編寫自定義邏輯來處理所有具有小於根鍵的鍵的分支，這在常規二叉樹中將只是root.left，但由於沒有左/右，我們將不得不回到BST的左右本質（它的順序也輸出按字典排序的值。）

來源

2017-08-18 09:31:49 AnukuL

字典分類與特里

回答

相關問題