0

完全な Tree および Node クラスと、検索および挿入メソッドを完了するための SearchTree クラスが与えられた、Java でのバイナリ検索ツリーの宿題があります。検索は、検索されたキーに対応するノードの値を返すことになっています。

これが Tree クラスで、ここがNode クラスです。私の検索と挿入の方法は以下のとおりです。

近づいているようですが、キー 0 と値 2 を Tree[Node[0,1,null,null]] にテスト挿入すると、正しい Tree ではなく Tree[Node[0,1,null,null] になります[ノード[0,2,ヌル,ヌル]]. ここで何が理解できませんか？

public static Object search(Tree tree, int key) {
    Node x = tree.getRoot();
    while (x != null) {
        if (key == x.getKey()) {
            return x.getValue();
        }
        if (key < x.getKey()) {
            x = x.getLeft();
        } else {
            x = x.getRight();
        }            
    }
    return null;
}

public static void insert(Tree tree, int key, Object value) {
    if (tree.getRoot() == null) {
        tree.setRoot(new Node(key, value));
    }
    Node juuri = tree.getRoot();
    while (juuri != null) {
        if (key == juuri.getKey()) {
            return;
        } else if (key < juuri.getKey()) {
            if (juuri.getLeft() == null) {
                juuri.setLeft(new Node(key, value));
                return;
            } else {
                juuri = juuri.getLeft();
            }
        } else {
            if (juuri.getRight() == null) {
                juuri.setRight(new Node(key, value));
                return;
            } else {
                juuri = juuri.getRight();
            }
        }
    }
}
4

1 に答える 1

1

私が見ている問題は、ツリーのキー値が一意であることです。この if ステートメントinsertでは、キーが既にツリーにあることがわかっている場合は、ノードを追加せずにメソッドを終了します。

 if (key == juuri.getKey()) { 
      return;
 }

あなたの例では（私が正しく理解していれば）0はすでにツリーにあるため、0を再度挿入しても何も変わりません。あなたの例に基づいて、キーが同じ場合、ノードで更新を行いたいと想定しています。したがって、このコードはそれを行います。

if (key == juuri.getKey()) {
     juuri.setValue(value);
     return;
}
于 2013-02-18T17:32:08.380 に答える