程序拋出異常後，我檢查了異常

Question

我一定是缺少的東西很簡單，因爲這是在吹我的腦海！

我想實現一個堆使用CompleteBinaryTree（這是使用數組實現）。 CompleteBinaryTree是一個Position<T>的數組，其中每個Position都包含一個元素。我正在爲Heap寫入add(T t)方法，其中t被插入CompleteBinaryTree的下一個空閒位置，然後執行upheap進程，直到CompleteBinaryTree被排序。下面是該方法：

private CompleteBinaryTree<T> tree = new CompleteBinaryTree<T>(); 
    private Position<T> entry = null; 

    public void add(T t) { 
     entry = tree.add(t); 

     if (entry.equals(tree.root())) { 
      return; 
     } 

     //continue to swap inserted element with its parent 
     //while it is smaller than its parent 
     while (entry.element().compareTo(tree.parent(entry).element()) < 0) { 
      Position<T> parent = tree.parent(entry); 
      Position<T> temp = entry; 
      entry = parent; 
      parent = temp; 
     } 
    } 

第一元素被添加細到堆，但是當我嘗試添加所述第二元件，InvalidPositionException是在while()線拋出。這就是exeption正在從CompleteBinaryTree類中拋出：

public Position<T> parent(Position<T> p) { 
     if (p == root()) throw new InvalidPositionException(); 

     return array[((ArrayPosition) p).index/2]; 
    } 

而且這裏距離CompleteBinaryTree使用其他兩種方法：

public Position<T> root() { 
     if (isEmpty()) throw new InvalidPositionException(); 
     return array[1]; 
    } 

    public Position<T> add(T t) { 
     if (last == array.length) { 
      // extend array 
      ArrayPosition[] temp = (ArrayPosition[]) new Object[array.length*2]; 
      for (int i=1; i < array.length; i++) { 
       temp[i] = array[i]; 
      } 
      array = temp; 
     } 

     array[last] = new ArrayPosition(last, t); 
     return array[last++]; 
    } 

我如何得到一個異常拋出，因爲p == root()，當我首先檢查p是否是根？

編輯

這裏是CompleteBinaryTree toString()，這是由堆toString()返回：

public String toString() { 
    StringBuffer buf = new StringBuffer(); 

    for (int i = 1; i < last; i++) { 
     buf.append(" ").append(array[i]); 
    } 

    return buf.toString();  
} 

Answer 1

我如何得到一個異常拋出，因爲p ==根（），當我首先檢查p是否是根？

但你不檢查每個tree.parent()說法，看它是否是根。您只檢查傳遞給該方法的第一個調用的參數。每次執行while循環的主體時，它都會將entry設置爲新值，並且當循環將新的未選中值傳遞給tree.parent()時。實際上，entry的每個新值都比前一個更接近根，因爲整個觀點是從樹向上移動樹，即朝向根。有時候這個過程有可能會達到根源，這很可能是樹中已經存在的元素越少。要解決這個

一種方式是移動根檢查到while條件：

while (!entry.equals(tree.root()) 
     && entry.element().compareTo(tree.parent(entry).element()) < 0) { 
    // ... 
} 

在這種情況下，當然，你並不需要您執行外目前一次性檢查循環。