我正在尝试为自己编写二叉树的 isEmpty 方法,但我遇到了问题。所以这就是我正在使用的方法。
public boolean isEmpty(){
if(root == null) return true;
else return false;
}
当我只添加一个元素,然后删除该元素并调用 isEmpty 时,我得到的不是真,而是假。
我的实现有问题吗?
所以这是删除方法:
/**
* 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;
}