1

我正在尝试为二叉搜索树编写代码，我正在使用的第一个方法是添加（插入）方法。根似乎正确插入，但添加第二个节点时出现空指针异常。我将在我的代码中用注释指出确切的问题点。

如果您可以看到如何修复错误，或者让我知道我的整体逻辑是否有缺陷，那将非常有帮助。--我会提到这是为学校准备的，所以我不想制作一个真正令人印象深刻的模型。 ..我的大部分布局选择只是反映了我们在课堂上的工作方式。此外，方法名称是由老师选择的，应该保持不变。随意编辑格式，有点麻烦。

二叉树类

public class BinarySearchTree 
{   
private static Node root;

    public BinarySearchTree()
    {
        root = null;
    }

    public static void Add (Node newNode)
    {
        Node k = root;
        if (root == null)//-----------------IF TREE IS EMPTY -----------------
        {
            root = newNode;
        }

        else // -------TREE IS NOT EMPTY --------

        {
        if (newNode.value > k.value) //-------NEW NODE IS LARGER THAN ROOT---------
        {   
            boolean searching = true;

            while(searching) // SEARCH UNTIL K HAS A LARGER VALUE
            {   //***CODE FAILS HERE****
                if(k.value > newNode.value || k == null) 
                {
                    searching = false;
                }
                else {k = k.rightChild; }
            }

            if ( k == null) { k = newNode;} 
            else if (k.leftChild == null){ k.leftChild = newNode;} 
            else 
            {
                Node temp = k.leftChild;
                k.leftChild = newNode;
                newNode = k.leftChild;

                if(temp.value > newNode.value )
                {
                    newNode.rightChild = temp;
                }
                else
                {
                    newNode.leftChild = temp;
                }
            }

        }

        if (newNode.value < k.value) //-----IF NEW NODE IS SMALLER THAN ROOT---
        {   
            boolean searching = true;

            while(searching) // ----SEARCH UNTIL K HAS SMALLER VALUE
            {// **** CODE WILL PROBABLY FAIL HERE TOO ***
                if(k.value < newNode.value || k == null) {searching = false;}
                else {k = k.leftChild;} 
            }

            if ( k == null) { k = newNode;} 
            else if (k.rightChild == null){ k.rightChild = newNode;} 
            else 
            {
                Node temp = k.rightChild;
                k.rightChild = newNode;
                newNode = k.rightChild;

                if(temp.value > newNode.value )
                {
                    newNode.rightChild = temp;
                }
                else
                {
                    newNode.leftChild = temp;
                }
            }
        }       
           }} // sorry having formatting issues
}

节点类

public class Node 
{
    int value;
    Node leftChild;
    Node rightChild;

    public Node (int VALUE)
    {
                value = VALUE;
    }
}

测试应用

public class TestIT
{

    public static void main(String[] args) 
    {

        BinarySearchTree tree1 = new BinarySearchTree();
        Node five = new Node(5);
        Node six = new Node(6);

        tree1.Add(five);
        tree1.Add(six);

        System.out.println("five value: " + five.value);
        System.out.println("five right: " + five.rightChild.value);
    }

}
4

1 回答 1

1

条件语句是从左到右检查的，所以在检查是否 k.value > newNode.value 之前需要检查 k 是否为 null，因为如果 k 为 null，则它没有值。

于 2012-12-07T20:06:50.603 回答