如何在java中实现AVL树?为什么compareTo说来源未知

Question

我正在为class的项目实现AVL树。我已经编写了搜索和插入方法，但我不确定它是否有效。当我尝试测试我的搜索和插入时，每当我的程序中的搜索方法到达compareTo语句时，它都会给出一个空指针异常。我知道只有当有一个项目，即根，并且它返回true时，搜索才有效。但似乎根的左/右子项没有关联。当我插入多个整数并搜索它们时，它不会起任何作用，或者总是返回true。

如何实现AVL树？我必须使用链接列表/数组列表吗？可以在不使用任何这些的情况下实现它。部分要求是我不能使用JCF中的任何东西。我花了无数个小时试图找出问题所在，我总是回到一垒。

当我使用.compareTo时，它告诉我来源未知。示例测试运行：

树是空的吗树的大小：2测试左侧高度树高：2线程"main"java.lang.NullPointerException中出现异常位于java.lang.Integer.compareTo（未知源）位于java.lang.Integer.compareTo（未知源）在AVLTree.search（AVLTree.java:110）在AVLTreeTest.main（AVLTreeTest.java:13）

主要测试程序：

    public class AVLTreeTest {
        public static void main(String args[]){
            AVLTree<Integer> tree = new AVLTree<Integer>();
            tree.insert(9);
            //tree.insert(5);
            tree.insert(4);
            //tree.insert(3);
            //tree.insert(19);
            System.out.println("Is the tree empty " + tree.isEmpty());
            System.out.println("Size of tree: " + tree.size());
            System.out.println("Height of tree: " + tree.height());
            System.out.println(tree.search(9));
            System.out.println(tree.search(5));
        }
    }

当我在我的比较器上按f2时转到行：

    else if(root!=null && item.compareTo(root.getItem())==0){

弹出以下内容：

Open声明：int java.lang.Comparable.compareTo（T arg0）注意：此元素既没有附加源代码，也没有附加Javadoc，因此找不到Javadoc。

Answer 1

Integer.compareTo如果将null传递给它，就会抛出一个NullPointerException。给定您的代码，它看起来像是root.getItem()返回了null。

堆栈跟踪中的"未知源"表示有关源代码的信息不可用。在任何情况下，您都可以非常确定问题不在Integer标准类中，因此您应该查看来自代码的第一个跟踪条目。这将是110号线的AVLTree.java。