如何编写递归函数以查找TRIE中的节点数量?
我正在尝试创建一个size()函数以返回我的trie中的节点数量,但是我不确定需要在trienode中更改什么才能实现这一目标。我从一个带有单词的文件中创建一个trie,我希望它返回节点的数量。因此,适用于以下文件: 猫 车 狗 挑选 泡菜 我希望它打印trie尺寸:14个节点。
class TrieNode {
public final Map<Character, TrieNode> children = new HashMap<>();
private boolean endOfWord;
static final int ALPHABET_SIZE = 26;
public Map<Character, TrieNode> getChildren() {
return children;
}
boolean isEndOfWord() {
return endOfWord;
}
void setEndOfWord(boolean endOfWord) {
this.endOfWord = endOfWord;
}
int size(TrieNode node) {
if(node == null)
return 0;
int total = 1;
for(TrieNode child : node.children)
total += size(child);
return total;
}
public static void main(String[] args) throws IOException {
Trie myTrie = new Trie();
try {
BufferedReader reader = new BufferedReader(new FileReader("test.txt"));
String line;
while ((line = reader.readLine()) != null)
myTrie.insert(line);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("Trie Size: " + myTrie.size() + " nodes");
I am trying to create a size() function to return the number of nodes in my Trie but I am not sure what I need to change in TrieNode to make this possible. I create a Trie from a file with words in it and I would like it to return the number of nodes. So for a file with:
cat
car
dog
pick
pickle
I would like it to print trie size: 14 nodes.
class TrieNode {
public final Map<Character, TrieNode> children = new HashMap<>();
private boolean endOfWord;
static final int ALPHABET_SIZE = 26;
public Map<Character, TrieNode> getChildren() {
return children;
}
boolean isEndOfWord() {
return endOfWord;
}
void setEndOfWord(boolean endOfWord) {
this.endOfWord = endOfWord;
}
int size(TrieNode node) {
if(node == null)
return 0;
int total = 1;
for(TrieNode child : node.children)
total += size(child);
return total;
}
public static void main(String[] args) throws IOException {
Trie myTrie = new Trie();
try {
BufferedReader reader = new BufferedReader(new FileReader("test.txt"));
String line;
while ((line = reader.readLine()) != null)
myTrie.insert(line);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("Trie Size: " + myTrie.size() + " nodes");
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论