java - 实现 Trie 数据结构的问题

Question

我对 Trie 实现方面的嵌套类有疑问

我想知道在 Trie 类内部和 Trie 类外部定义 TrieNode 类有什么区别

如果我在 Trie 类之外实现 TrieNode 类，当我尝试使用 Insert 方法时，它会在 (Trie.java:14) 处保持 sayig NullPointException，

因此，当我在 Trie 类之外实现 TrieNode 类时，如果我想解决 Nullpointexception 错误，任何人都可以解释两种方式之间的区别以及解决方案是什么。

这是我的代码

public class Trie {

    private final TrieNode root;
    public Trie () {
        root = new TrieNode();
    }

    public void insert (String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.children.get(ch);
            if (node == null) {
                node = new TrieNode();
                current.children.put(ch, node);
            }
            current = node;
        }
        //mark the current nodes endOfWord as true
        current.isEnd = true;
}

    public boolean search (String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (current.children.get(ch) == null) {
                return false;
            }
            current = current.children.get(ch);
        }

        return current.isEnd;
    }

    public void delete (String word) {
        delete(root, word, 0);
    }

    private boolean delete (TrieNode node, String word, int index) {
        if (index == word.length()) {
            if (!node.isEnd) {
                return false;
            }
            node.isEnd = false;

            return node.children.size() == 0;
        }
        if (node == null) {
            return false;
        }
        node = node.children.get(word.charAt(index));
        boolean shouldBeDeleted = delete(node, word, index + 1);

        if (shouldBeDeleted) {
            node.children.remove(word.charAt(index));
            return node.children.size() == 0;
        }
        return false;
    }

    public static void main(String[] args) {

        Trie trie = new Trie();
        trie.insert("abcd");
      //  System.out.println(trie.search("abcd"));
    }
}

TrieNode 类分离为 Trie 类

public class TrieNode {
    boolean isEnd;
    Map<Character, TrieNode> children;
    public void TrieNode () {
        this.isEnd = false;
        this.children = new HashMap<>();
    }
}

标签： javaooptrie