字典分类与特里

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

字典分类与特里

回答

相关问题