java中的trie构建

Question

如何从文件构建树？我希望能够从文件中读取它们，然后添加到适当的水平

Answer 1

在我看来，你正在试图执行trie。

在这里看到java的一个很好的实现：http://www.cs.duke.edu/~ola/courses/cps108/fall96/joggle/trie/Trie.java

Answer 2

添加

在根开始，搜索第一（或电流）的来信。如果找到该字母，则转到该节点并搜索下一个字母。如果未找到该字母，则搜索与当前字母匹配的单词，如果有相似的单词，则将当前字母添加为新节点，然后将该单词移到该单词下方，否则添加该单词。

注意：这将导致为搜索更优化的树，然后显示示例中显示的树。 （金刚和调整将在另一个“一”节点进行分组）

更新：看看维基百科文章Trie

Answer 3

如果你有树只有两个级别叶前（实际单词），你可以简单地从具有28个元素的数组开始，并将这些字母转换为索引（即a == 1，b == 2等）。数组的元素可以是一些包含完整单词的集合/列表。您可以懒洋洋地创建数组和列表（即创建根数组，但对其他数组和列表有空值，然后在需要时创建数组/列表）。

我读的规则，你应该遵循正确吗？

P.S.我认为使用全尺寸的阵列在空间上不会太浪费，它应该是非常快的地址

更新：@ user1747976，以及每个阵列需要约28 * 4或28 * 8位+ 12字节overhead。希望你使用压缩操作，所以它是每个阵列28 * 4 + 12 = 116bytes。现在，这取决于您是否想要提高内存效率或处理效率。为了提高内存效率，你可以使用某种类型的hashmap来代替数组，但我不确定额外的开销会比使用数组少。处理将肯定会更糟。 根据树部门的要求，您需要多次使用一些巧妙的循环。用于插入树的一些难看的伪代码：

root=new Object[28]; 
word="something"; 
pos = root; 
wordInd=1; 
for (int i=1; i<=TREE_DEPTH ; i++) { 
    targetpos = letterInd(letter(wordInd,word)); 
    if (i==TREE_DEPTH) { 
     if (pos[targetpos] == null) pos[targetpos] = new HashSet<String>(); 
     (Set) pos[targetpos].add(word); 
     break; 
    } else { 
     if (pos[targetpos] == null) pos[targetpos] = new Object[28]; 
     wordInd++; 
     pos = pos[targetpos]; 
    } 
} 

您可以用于检索单词的类似循环。