java - 使用 Trie 进行字典排序

Question

根据维基百科，关于特里树:

Lexicographic sorting of a set of keys can be accomplished with a simple trie-based algorithm as follows:

• Insert all keys in a trie.
• Output all keys in the trie by means of pre-order traversal, which results in output that is in lexicographically increasing order.

但是，这是我对标准 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

“词典排序”是什么意思？似乎输出顺序与插入顺序更相关，而不是字典顺序。我弄错了什么吗？以这棵树为例，预订打印输出将是“to tea ted 10 a inn”。字典顺序在哪里？

Answer 1

关于使用尝试进行字典顺序排序的正确说法是:

假设节点的子节点按边标签排序，则 trie 中节点的预序与它们表示的字符串的字典顺序相同。

现在，如果您在代码中尝试这样做，预序遍历应该会为您提供字典顺序的字符串。

这里是有例子的引用:http://www.cs.helsinki.fi/u/tpkarkka/opetus/12s/spa/lecture02.pdf