創建特里數據結構 - NullPointerException異常

Question

package trie; 

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 

class Node { 
    private String word; 
    private HashMap<Character, Node> nodes; 

    public List<String> getAll() { 
     List<String> x = new ArrayList<String>(); 
     for (HashMap.Entry<Character, Node> entry : nodes.entrySet()) { 
      Character key = entry.getKey(); 
      Node node = entry.getValue(); 
      if (node.word != null) 
       x.add(node.word); 
      x.addAll(node.getAll()); 
     } 
     return x; 
    } 

    public String toString() { 
     return this.word; 
    } 

    public HashMap<Character, Node> getNodes() { 
     return this.nodes; 
    } 

    public boolean insert(String word, int stringPos) { 
     this.word = word; 
     this.nodes = new HashMap<Character, Node>(); 

     Character currentLetter = word.charAt(stringPos); 
     if (nodes.containsKey(currentLetter)) { 
      nodes.put(currentLetter, new Node()); 
     } 

     if (stringPos + 1 == word.length()) { 
      nodes.get(currentLetter).word = word; 
     } else { 
      nodes.get(currentLetter).insert(word, stringPos); 
     } 
     return true; 
    } 

    public List<String> getAllWithPrefix(String prefix, int stringPos) { 
     List<String> x = new ArrayList<String>(); 
     for (HashMap.Entry<Character, Node> entry : nodes.entrySet()) { 
      Character key = entry.getKey(); 
      Node node = entry.getValue(); 
      if (stringPos >= prefix.length() || key.equals(prefix.charAt(stringPos))) { 
       if (node.word != null) { 
        x.add(node.word); 
       } 

       if (node.nodes.size() == 0) { 
        if (stringPos + 1 <= prefix.length()) { 
         x.addAll(node.getAllWithPrefix(prefix, stringPos + 1)); 
        } else { 
         x.addAll(node.getAllWithPrefix(prefix, stringPos)); 
        } 
       } 
      } 
     } 
     return x; 
    } 
} 

public class Trie { 
    private Node root; 
    public Trie() { 
     this.root = new Node(); 
    } 

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

    public List<String> getAll() { 
     return root.getAll(); 
    } 

    public List<String> getAllWithPrefix(String prefix, int stringPos) { 
     return root.getAllWithPrefix(prefix, stringPos); 
    } 

    public static void main(String[] args) { 
     Trie trie = new Trie(); 
     trie.insert("java"); 
    } 
} 

OUTPUT：

Exception in thread "main" java.lang.NullPointerException 
    at trie.Node.insert(Trie.java:47) 
    at trie.Trie.insert(Trie.java:83) 
    at trie.Trie.main(Trie.java:96) 

我只要運行該程序獲得NullPointerException。我知道當對象指向null時會發生此異常。但是在Trie的構造函數中，我創建了一個新對象Node，那麼爲什麼會發生這種情況呢？

Answer 1

的問題似乎是這一行：

nodes.get(currentLetter).insert(word, stringPos); 

nodes.get(currentLetter)返回NULL，因爲地圖是空的。

你需要插入到你HashMap類第一。

Answer 2

你插入法，用評論：

public boolean insert(String word, int stringPos) { 
    this.word = word; 
    this.nodes = new HashMap<Character, Node>(); // <-- nodes is now empty 

    Character currentLetter = word.charAt(stringPos); 
    if (nodes.containsKey(currentLetter)) { // <-- can never be true since nodes is empty 
     nodes.put(currentLetter, new Node()); // <-- will never be executed 
    } 

    if (stringPos + 1 == word.length()) { 
     nodes.get(currentLetter).word = word; // <-- nodes is empty, so get() returns null causing NPE 
    } else { 
     nodes.get(currentLetter).insert(word, stringPos); // <-- nodes is empty, so get() returns null causing NPE 
    } 
    return true; 
}