如何编写递归函数以查找TRIE中的节点数量?

发布于 01-22 10:55 字数 1332 浏览 4 评论 0原文

我正在尝试创建一个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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文