检查异常后程序抛出异常

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() 行。这是从 CompleteBinaryTree class:

内部抛出异常的地方

    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 是否是根时，我怎么会因为 p == root() 而抛出异常？

编辑

这里是CompleteBinaryTreetoString()，由HeaptoString()返回：

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

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

    return buf.toString();      
}

Answer 1

How am I getting an exception thrown because p == root(), when I first check if p is the root?

但是您不检查每个tree.parent()参数以查看它是否是root。您只检查传递给该方法的第一次调用的参数。每次执行 while 循环的主体时，它都会将 entry 设置为一个新值，并且在循环循环时将这个未经检查的新值传递给 tree.parent()。事实上，entry 的每个新值都比前一个更接近根，因为整个点是将树从子节点向上移动到父节点，即向根节点移动。有时这个过程很可能会到达根，而且树中已有的元素越少越有可能。

解决这个问题的一种方法是将根检查移动到 while 条件中：

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

在那种情况下，当然，您不需要在循环外执行的当前一次性检查。

检查异常后程序抛出异常

Program throwing an exception after I check for the exception

java

arrays

heap

binary-tree

exception