java - 在二叉树中证明最小堆时出现空指针异常

Question

这段代码是为了确定二叉树是否是最小堆，我NullPointerException在公共静态布尔 isMinHeap 中的第三个 if 语句中不断得到一个，我不确定为什么我一直得到这个异常，因为我认为代码是有效的由于上述中断。

public class ArrayHeapChecker {
public static boolean isBinaryTree(Integer[] array) {
    for (int i = 1; i < array.length; i++){
        if (array[i] != null && array [(i-1)/ 2] == null)   {
            return false;
        }
    }
    return true;
}
public static boolean isCompleteBinaryTree(Integer[] array) {
    if(!isBinaryTree(array)) {
        return false;
    }

    for (int i = 0; i < array.length - 1; i++)  {
        if ((i % 2 == 0) && array[i] == null && array[i + 1] != null)   {
            return false;
        }
        if ((i % 2 != 0) && array[i] == null && array[i + 1] != null)   {
            return false;
        }
    }

    return true;
}
public static boolean isMinHeap(Integer[] array) {
    if(!isCompleteBinaryTree(array)) {
        return false;
    }
    for (int i = 0; i < array.length - 1; i++)  {
        if (array[i] == null)   {
            break;
        }
        if (array.length <= ((2*i) + 2))    {
            break;
        }
        if (array[(i * 2) + 1] == null || array[(i * 2) + 2] == null)   {
            break;
        }
        if (array[i] > array[(i * 2) + 1] || array[i] > array[(i * 2) + 2]) {
            return false;
        }
    }
    return true;
}
}

Answer 1

你没有检查你的元素array不是null。您只array[i] != null && array [(i-1)/ 2] == null在ArrayHeapChecker#isBinaryTree. Integer与 进行比较时，这并不能保护您免受 NPE 的侵害null。例如，您的代码将因以下输入而失败：new Integer[]{1, 2, 3, 4, 5, 6, null}. 我不建议您进行修复，因为这取决于您的要求，但您的检查不够严格。

更准确地说，就像现在一样，只要你有一个array奇数长度的最后一个元素是，你的代码就会失败null，除了 when lenght == 1。