1

バイナリツリーのisEmptyメソッドを自分で作成しようとしていますが、問題が発生しています。これが私が使っている方法です。

public boolean isEmpty(){
if(root == null) return true;
else return false;
}

要素を1つだけ追加してから、この要素を削除してisEmptyを呼び出すと、trueではなくfalseになります。

私の実装に何か問題がありますか？

したがって、これはremoveメソッドです。

  /**
    * Internal method to remove from a subtree.
    * @param x the item to remove.
    * @param t the node that roots the tree.
    * @return the new root.
    * @throws ItemNotFoundException if x is not found.
    */
    protected BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
    {
    if( t == null )
    throw new ItemNotFoundException( x.toString( ) );
    if( x.compareTo( t.element ) < 0 )
    t.left = remove( x, t.left );
    else if( x.compareTo( t.element ) > 0 )
    t.right = remove( x, t.right );
    else if( t.left != null && t.right != null ) // Two children
    {
    t.element = findMin( t.right ).element;
    t.right = removeMin( t.right );
    }
    else
    t = ( t.left != null ) ? t.left : t.right;
    return t;
    }

これは、removeメソッドが使用するremoveMinメソッドです。

        /**
         * Internal method to remove minimum item from a subtree.
         * @param t the node that roots the tree.
         * @return the new root.
         * @throws ItemNotFoundException if t is empty.
         */
         protected BinaryNode<AnyType> removeMin( BinaryNode<AnyType> t )
         {
         if( t == null )
        throw new ItemNotFoundException( );
        else if( t.left != null )
        {
        t.left = removeMin( t.left );
        return t;
        }
        else
        return t.right;
        }
4

2 に答える 2

0

要素の削除コードを確認してください。通常、コードよりも削除ノードの親を見つけて、対応する参照をnullに設定します。そして最後の要素については、nullroot変数に設定する必要があります。

于 2012-02-25T21:52:25.003 に答える
0

メソッドremove(AnyType x, BinaryNode<AnyType> t)はX要素を持つノードを検索し、その子の1つをremoveMinメソッド（2つの子がある場合）または左または右の子ノードに置き換えます。public removeメソッドは、次のようになります。

public boolean remove(AnyType x) {
    try {
        BinaryNode<AnyType> node = remove(x, root);
        if (node != null) {
            node = null;
            return true;
        }
        return fal
    } catch (Exception e) {
        //do something with the exception
        return false;
    }
}
于 2012-02-25T22:28:16.607 に答える