0

わかりましたので、PhoneBook の BinarySearchTree を使用して DictionaryADT インターフェイスを実装しています。私のファイルは、BST の追加と削除を除いて正常に動作しています。重複したエントリを追加することは許可されていませんが、ツリーに重複が追加されており、その理由がわかりません。削除でも同様に、削除したエントリがテスト ファイルで見つかったので、削除がまったく機能しないと思います。これが私の方法です：どんな助けも本当に感謝しています。

public boolean add(K key, V value) {

    if (root == null)
        root = new Node<K, V>(key, value);
    else
        insert(key, value, root, null, false);
    currentSize++;
    modCounter++;
    return true;

}

private void insert(K k, V v, Node<K, V> n, Node<K, V> parent, boolean wasLeft)
{
    if (n == null) {
        if (wasLeft)
            parent.leftChild = new Node<K, V>(k, v);
        else
            parent.rightChild = new Node<K, V>(k, v);
    }
    else if (((Comparable<K>) k).compareTo((K) n.key) < 0)
        insert(k, v, n.leftChild, n, true);
    else
        insert(k, v, n.rightChild, n, false);
}

ここに私の削除があります：

  public boolean delete(K key){
        if (!this.contains(key)) {
            return false;
    }

    Node<K, V> node = find(key, root, 0);
    Node<K,V> parent = remove(node, root);
    root=parent;
    currentSize--;
    modCounter++;

    return true;
}


private Node<K,V> remove( Node<K,V> node_to_delete, Node<K,V> start_node )
{
    if( start_node == null )
        return start_node;   
    if(((Comparable<K>)node_to_delete.key).compareTo( start_node.key ) < 0 )
        start_node.leftChild = remove( node_to_delete, start_node.leftChild );
    else if(((Comparable<K>)node_to_delete.key).compareTo( start_node.key ) > 0 )
        start_node.rightChild = remove( node_to_delete, start_node.rightChild );
    else if( start_node.leftChild != null && start_node.rightChild != null ) 
    {
        start_node.key = findMin( start_node.rightChild ).key;
        start_node.rightChild = remove( start_node, start_node.rightChild );
    }
    else
        start_node = ( start_node.leftChild != null ) ? start_node.leftChild : start_node.rightChild;
    return start_node;
}

private Node<K,V> findMin( Node<K,V> t )
{
    if( t == null )
        return null;
    else if( t.leftChild == null )
        return t;
    return findMin( t.leftChild );
}
4

2 に答える 2

0

さて、私のファイルは正常に実行され、重複は追加されず、削除も正常に機能します...しかし!! 電話帳から番号を印刷するとき、BSTはそれらを特定のソートされた順序で配布する必要がありますね。それは私の場合には起こらない...

これが私のaddメソッドに追加したものです。

Node<K,V> newNode = new Node<K,V>(key,value);
    if(contains(key))
        return false;

私の番号（キー）がランダムで、特定の順序ではない理由がわかりません。

于 2012-12-02T00:00:20.603 に答える
0

あなたのチェックは で不完全ですinsert:

else if (((Comparable<K>) k).compareTo((K) n.key) < 0)
    insert(k, v, n.leftChild, n, true);
else
    insert(k, v, n.rightChild, n, false);

比較の結果が 0 の場合は、ツリーに既に存在する値に遭遇したので、この時点から新しい値を破棄する必要があります。

は次のinsertようになります。

private void insert(K k, V v, Node<K, V> n, Node<K, V> parent, boolean wasLeft)
{
    if (n == null) {
        if (wasLeft)
            parent.leftChild = new Node<K, V>(k, v);
        else
            parent.rightChild = new Node<K, V>(k, v);
    }
    else {
        int result = ((Comparable<K>) k).compareTo((K) n.key);
        if (result < 0)
            insert(k, v, n.leftChild, n, true);
        else if(result > 0)
            insert(k, v, n.rightChild, n, false);
        //else: discard the data, it's a duplicate! 
    }
}
于 2012-11-30T08:28:29.703 に答える