Počet uzlů v uzlu trie

Question 1

Tady jsem vytvořil třída Trie a TrieNode, který implementuje datové struktury Trie v jazyce Java. Mám za úkol napsat metody size() [návratový typ int] vrátí počet uzlů v Trie.

class Trie {

    private TrieNode root;

    /////////////////////
    // TrieNode class
    class TrieNode {
        public char c;
        public boolean isWord;
        public TrieNode[] children;

        public TrieNode(char c) {
            this.c = c;
            isWord = false;
            children = new TrieNode[26];
        }
    }

    public Trie() {
        root = new TrieNode('\0');
    }

    public boolean isPrefix(String word) {
        return getNode(word) != null;
    }

    public void insert(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (curr.children[c - 'A'] == null)
                curr.children[c - 'A'] = new TrieNode(c);
            curr = curr.children[c - 'A'];
        }
        curr.isWord = true;
    }

    // Helper
    private TrieNode getNode(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (curr.children[c - 'A'] == null)
                return null;
            curr = curr.children[c - 'A'];
        }
        return curr;
    }

Snažil jsem se získat počet uzlů v Trie, a to, co jsem si myslel o tom, je:

    public int size() {
        return size(root);
    }

    private int size(TrieNode root) {

        for (int i = 0; i < root.children.length; i++) {
            if (root.children[i] != null) {
                if (root.isWord)
                return 1;
                else
                    return 1 + size(root.children[i]);
            }
        }
        return 0;
    }

Ale to není správné. Nějaké nápady?

Question 2

To je jednoduché prohledávání do Hloubky:

public static int size(TrieNode node) {
    if(node == null)
        return 0;
    
    int total = 1;
    
    for(TreeNode child : node.children)
        total += size(child);
    
    return total;
}

oleg.cherednik · Answer 1 · 2021-11-23T22:51:30

To je jednoduché prohledávání do Hloubky:

public static int size(TrieNode node) {
    if(node == null)
        return 0;
    
    int total = 1;
    
    for(TreeNode child : node.children)
        total += size(child);
    
    return total;
}

Počet uzlů v uzlu trie

Otázka

Nejlepší odpověď

V jiných jazycích

Tato stránka je v jiných jazycích

Populární v této kategorii

Oblíbené položky v této kategorii