遍历二叉树时出现NullPointerException

Question

现在我不确定有人能真正帮助我，因为它的代码量非常大，但任何帮助都将不胜感激。这里是我的相关代码：

public class BTree implements Iterable<String> { 
    /** Left child */ 
    BTree left; 
    /** Right Child */ 
    BTree right; 
    /** Comparator to use for sorting */ 
    Comparator<String> comp; 
    /** Parent node */ 
    BTree parent; 
    /** String stored in this leaf */ 
    String s; 
    /** # of iterators currently working on it */ 
    int active = 0; 
    /** Size of the BTree */ 
    int size; 

public void build(Iterable<String> iter, int numStrings) { 
     if (this.active > 0) { 
      throw new ConcurrentModificationException(); 
     } 
     else { 
      Iterator<String> itr = iter.iterator(); 
      while (numStrings != 0 && itr.hasNext()) { 
       String s = itr.next(); 
       if (!this.contains(s)) { 
        this.insert(s); 
        this.size++; 
        numStrings--; 
       } 
      } 
     } 
    } 

/** 
* Inserts the string into the given BTree 
* @param str - String to insert 
*/ 
private void insert(String str) { 
    if (this.s.equals("")) { 
     this.s = str; 
    } 
    else if (this.comp.compare(str, this.s) > 0) { 
     if (this.right == null) { 
      BTree bt = BTree.binTree(this.comp); 
      bt.s = str; 
      this.right = bt; 
      bt.parent = this; 
     } 
     else { 
      this.right.insert(str); 
     } 
    } 
    else if (this.comp.compare(str, this.s) < 0) { 
     if (this.left == null) { 
      BTree bt = BTree.binTree(this.comp); 
      bt.s = str; 
      this.left = bt; 
      bt.parent = this; 
     } 
     else { 
      this.left.insert(str); 
     } 
    } 
} 



    private class BTreeIterator implements Iterator<String> { 
      /** Current BTree being iterated over */ 
      BTree current; 
      /** How many next() calls have there been */ 
      int count; 
      /** Size of the BTree */ 
      int max; 
      /** Constructor for BTreeIterator 
      * @param current 
      */ 
      BTreeIterator(BTree current) { 
       this.current = current; 
       this.count = 0; 
       this.max = current.size; 
       active++; 
      } 

      /** Returns true if there is another string to iterate over 
      * @return boolean 
      */ 
      public boolean hasNext() { 
       if (this.count != this.max) { 
        return true; 
       } 
       else { 
        active--; 
        return false; 
       } 
      } 

      /** 
      * Returns the next string in the iterator 
      * @return String 
      */ 
      public String next() { 
       if (this.count == 0) { 
        this.count++; 
        current = this.current.getLeftMost(); 
        if (this.current.s.equals("")) { 
         throw new NoSuchElementException(); 
        } 
        return this.current.s; 
       } 
       else if (this.current.right != null) { 
        this.current = this.current.right.getLeftMost(); 
        this.count++; 
        return this.current.s; 
       } 
       else { 
        BTree tree = this.current; 
        while (tree.parent.right == tree) { 
         tree = tree.parent; 
        } 
        this.current = tree.parent; 
        this.count++; 
        return this.current.s; 
       } 
      } 

      /** Throws an exception since we aren't removing anything from the trees 
      */ 
      public void remove() { 
       throw new UnsupportedOperationException(); 
      } 

     } 
    } 

}

例外被在迭代器的next（）方法的while (tree.parent.right == tree)线抛出。有趣的是，我的代码工作得很好，比较器按字典顺序进行比较，并通过24000字的文件按字典顺序进行排序。

class StringWithOutPrefixByLex implements Comparator<String> { 

/** 
* compares o1 and o2 
* @param o1 first String in comparison 
* @param o2 second String in comparison 
* @return a negative integer, zero, or a positive integer 
*   as the first argument is less than, equal to, or 
*   greater than the second. 
*/ 
public int compare(String o1, String o2) { 
    String s1, s2; 
    if(o1.length() > 4){ 
     s1 = o1.substring(3); 
    } 
    else { 
     s1 = o1; 
    } 
    if(o2.length() > 4){ 
     s2 = o2.substring(3); 
    } 
    else { 
     s2 = o2; 
    } 
    return s1.compareTo(s2); 
} 
} 

即使怪异，它工作正常与比较器相同的文件多达199个字，但只要我有它累积到200个字它打破：它仅使用下面的比较时，抛出该异常。

编辑：我已经确定，例外是由于代码试图引用tree.parent.right而tree.parent是null，但我不明白为什么它试图做到这一点。据我所知，我的代码不应该尝试调用空值tree.parent，正如我下面的评论所解释的。

Answer 1

那么，你实际上并没有显示足够的代码，但是，你的BTree的根节点呢？根节点中的BTree.parent的值是多少？ null？

如果根节点有一个空父，那么，在这个while循环，很可能是：

   while (tree.parent.right == tree) { 
        tree = tree.parent; 
       } 

...将得到根节点，该tree将被设置为tree.parent，这是null，然后while循环测试将失败，因为tree.parent.right将尝试取消引用空指针。