0

好的，所以我正在为电话簿实现一个带有 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 回答