java - 覆蓋迭代器？

Question

誠實地說，我花了幾天的時間看着這個並試圖弄明白，但是都很短暫。目標是查看trie節點是否有下一個，如果是的話。

當它是由被稱爲：

public Iterator<String> iterator() { 
    return new TrieIterator(); 
} 

調用它來實現自己的迭代器。我試着用hasNext（）的數組+ 1中的一個位置，將事物與大小，數字或節點以及孩子進行比較，並且總結出來。我最近的嘗試是沿着（下面）的行，但不起作用。

hasNext() { 
return this.children.hasChildren(); /* doesn't work */ 
} 

public class TrieIterator implements Iterator<String> { 

    public TrieIterator(){ 
    } 

    public boolean hasNext() { 
     return false; 
    } 

    public String next() { 

     return null; 
    } 

    public void remove() { 
     throw new UnsupportedOperationException(); 
    } 
} 

這裏的trieNode類以及：

public class TrieNode { 

    protected char letter = ' '; 
    protected TrieNode parentNode = null; 
    protected boolean fullWord = false; 
    protected TrieNode[] children = new TrieNode[26]; 
    protected int prefixes = 0; 

    public TrieNode(char letter, TrieNode parentNode){ 
     this.letter = letter; 
     this.parentNode = parentNode; 
    } 

    public boolean hasChildren(){ 
     int index = 0; 

     while(index < children.length){ 
      if(children[index] != null) { 
       return true; 
      } 
      index++; 
     } 
     return false; 
    } 

    public TrieNode nodeForLetter(char ch) { 
     return children[ch - 97]; 
    } 

    public boolean isEndOfWord() { 
     return letter == '*'; 
    } 
} 

添加和刪除如下：

public void addWord(String s) { 
    if (hasWord(s)) return; 

    int index = 0; 
    TrieNode current = root; 
    char[] letters = s.toCharArray(); 

    while(index < s.length()){ 
     TrieNode child = current.children[letters[index] - 97]; 
     if(child == null){ 
      child = new TrieNode(letters[index], current); 
      child.prefixes++; 
      numOfNodes++; 
     } 

     current = child; 
     index++; 

     if(index == s.length()){ 
      current.fullWord = true; 
      numOfWords++; 
     } 
    } 
} 

public void deleteWord(String s) { 
    if(s.length() == 0) return; 
    if(size() == 0) return; 
    if(!hasWord(s)) return; 

    TrieNode current = root; 
    for (char ch : s.toCharArray()) { 
     TrieNode child = current.children[s.charAt(ch) - 97]; 
     if(child.prefixes == 1){ 
      child = null; 
      return; 
     } 
     else{ 
      child.prefixes--; 
      current = child; 
     } 
    } 
    current.fullWord = false; 
} 

public boolean hasWord(String s) { 
    if(size() == 0) return false; 

    char[] letters = s.toCharArray(); 
    int l = letters.length; 
    TrieNode current = root; 

    int i; 
    for (i = 0; i < l; i++){ 
     if (current == null) return false; 
     current = current.children[letters[i] - 97]; 
    } 

    if (i == l && current == null) return false; 
    if (current != null && !current.fullWord) return false; 

    return true; 
} 

請不要改變目前執行的線索:)

的

Answer 1

您嘗試執行hasNext()與this.children.hasChildren();不會因爲children是一個TrieNode的數組，所以它沒有任何hasChildren()方法。

hasChildren()方法是TrieNode而不是它的children陣列的方法。

您需要跟蹤當前節點，當前節點中的位置以及到目前爲止所看到的所有字符。 hasNext()應該返回true，如果有任何更多的單詞，這意味着如果該節點是一個完整的單詞，或者如果它有任何尚未訪問過的兒童，是完整的單詞。 （但是，我假設葉節點總是全字，所以如果節點有任何尚未訪問過的子節點，則後一個測試可能很簡單。）

您需要決定是否要返回較短的單詞之前較長的（你從next()只要你在一個完整的字節點到達，或訪問其子後只返回一個字？）你還需要保持節點的堆棧，所以你已經下降到一個孩子後，節點，您可以返回到父節點中的前一個位置。

這不是一件小事。我建議開始與特里從一個非常小的詞語集建（如「一」，「一個」和「AT」），並獲得該完全調試你移動到三個字母的單詞或更前。 （你也應該考慮一下你在迭代時修改Trie的方法，標準的java.util類會在每次修改時更新一個計數器，並測試它在迭代器中沒有改變。如果有，他們扔使用此策略的ConcurrentModificationException。迭代器稱爲快速失敗的迭代器）