1

二分探索木のコードを書こうとしています。最初に取り組んでいるメソッドは、追加 (挿入) メソッドです。ルートは適切に挿入されているようですが、2 番目のノードを追加するときに null ポインター例外が発生します。コード内の正確な問題箇所をコメントで示します。

バグを修正する方法を確認できる場合、または私の全体的なロジックに欠陥があるかどうかを教えていただければ、非常に役立ちます.--これは学校用であることを述べておきますので、本当に印象的なモデルを作成するつもりはありません. ..私のレイアウトの選択のほとんどは、クラスでの作業方法を反映しているだけです。また、メソッド名は教師によって選択されたものであり、同じままにする必要があります。フォーマットを自由に編集してください。少し問題がありました。

二分木クラス

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 が null の場合は値がないため、k.value > newNode.value かどうかをチェックする前に、k が null かどうかをチェックする必要があります。

于 2012-12-07T20:06:50.603 に答える