0

私のデータ構造クラスはツリーを扱っています。左、中央、および右のノードへの参照を持つ 2 つの値を含む 3 項ツリーを実装しています (左のサブツリーは値 1 未満、中央のサブツリーは値 1 と値 2 の間、右のサブツリーは値 2 より大きい) ）。Tree クラスにはインターフェースが提供されており、find、insert、および delete メソッドは再帰的でなければなりません。これがテストされるクライアント コードは、挿入メソッドを繰り返し使用してツリーを作成し、ルートは として始まりますnull。

別のプライベート メソッドで親ノードを見つけ、返されたノードを適切に変更することで、再帰的にツリーに値を挿入しようとしています。現在の問題は、メソッドがルートである初期ノードを返し、ルートが null であるため、値を使用して新しいノードを正しく作成することです。ただし、ルートは null のままです。

これは、参照と値が Java で機能する方法によるものであると確信しています ( Jon Skeet によるこの記事で説明されている C# に似ています)。制約が与えられた場合、ツリーへの挿入を許可するには、これをどのように変更すればよいですか? 以下は、ツリー クラスの現在の挿入メソッドと、同様のプライベート メソッドです。

public void insert(AnyType newData)
{
    // If insert node is null, make a new node with newData as first key
    TernaryNode<AnyType> insert_node = findNode(newData, root);
    if (insert_node == null)
    {
        insert_node = new TernaryNode<AnyType>(newData);
    }
    else
    {
        // Get the key that is equal if the insert node is not null
        if (insert_node.getKey1() == null)
        {
            insert_node.setKey1(newData);
        }
        else
        {
            insert_node.setKey2(newData);
        }
    }// end else
}// end insert

private TernaryNode<AnyType> findNode(AnyType item, TernaryNode<AnyType> node)
{
    TernaryNode<AnyType> current_node = node;
    if (current_node != null)
    {
        if (current_node.getKey1() != item &&
                current_node.getKey2() != item)
        {
            // Comparator checks left
            if (compare.compare(current_node.getKey1(), item) <= -1)
            {
                return findNode(item, current_node.left);
            } // Comparator checks right
            else  if (compare.compare(current_node.getKey2(), item) >= 1)
            {
                return findNode(item, current_node.right);
            }// Comparator checks middle
            else
            {
                return findNode(item, current_node.middle);
            }
        }// end while
    }// end if
    // Return current node even if it is null
    return current_node;
}// end findNode
4

2 に答える 2

1

メンバーに何かを割り当てない限り、rootメンバーが値を取得することはありません。DocumentXMLドキュメント（ツリーでもある）が実際のドキュメントルートノードとは異なる外部オブジェクトを持っているのと同様に、ツリーにはおそらく何らかの外部コンテナが必要です。

于 2009-11-26T22:23:08.323 に答える
0 
    TernaryNode<AnyType> insert_node = findNode(newData, root);
    if (insert_node == null)
    {
            insert_node = new TernaryNode<AnyType>(newData);
            root = insert_node;
    }
于 2009-11-26T22:40:43.447 に答える