二叉查找树及实现

//二叉搜索树
public class BinarySearchTree<T extends Comparable<? super T>>
{
    /**
     * 构造一棵空树.
     */
    public BinarySearchTree( )
    {
        root = null;
    }

    /**
     * 在二叉搜索树中插入数据.
     * @param x the item to insert.
     */
    public void insert( T x )
    {
        root = insert( x, root );
    }

    /**
     * 从二叉搜索中删除数据（节点）.
     * @param x the item to remove.
     */
    public void remove( T x )
    {
        root = remove( x, root );
    }

    /**
     * 找最小数据.
     * @return smallest item or null if empty.
     */
    public T findMin( )
    {
        if( isEmpty( ) )
            throw new UnderflowException( );
        return findMin( root ).element;
    }

    /**
     * 找最大数据.
     * @return the largest item of null if empty.
     */
    public T findMax( )
    {
        if( isEmpty( ) )
            throw new UnderflowException( );
        return findMax( root ).element;
    }

    //二叉搜索树中是否包含x
    public boolean contains( T x )
    {
        return contains( x, root );
    }

   
    public void makeEmpty( )
    {
        root = null;
    }

   
    public boolean isEmpty( )
    {
        return root == null;
    }

   //中序遍历输出二叉搜索树的内容
    public void printTree( )
    {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }

    //插入
    private BinaryNode<T> insert( T x, BinaryNode<T> t )
    {
        if( t == null )
            return new BinaryNode<T>( x, null, null );
        
        int compareResult = x.compareTo( t.element );
            
        if( compareResult < 0 )
            t.left = insert( x, t.left );
        else if( compareResult > 0 )
            t.right = insert( x, t.right );
        else
            ;  // Duplicate; do nothing
        return t;
    }

删除节点是最难的操作了。如果节点是一片树叶，那么它可以立即删除，将原来指向这个节点的引用设为null。如果节点有一个儿子，则该节点可以在其父节点调整自己的链以绕过该节点后被删除。

    //删除
    private BinaryNode<T> remove( T x, BinaryNode<T> t )
    {
         //先在树中查找x   
        if( t == null )
            return t;   // 没有找到，返回
        
        int compareResult = x.compareTo( t.element );
          // 在左树中找
        if( compareResult < 0 )
            t.left = remove( x, t.left );
          //在右树中找
        else if( compareResult > 0 )
            t.right = remove( x, t.right );
        //在树中找到了节点值为x的节点
        else if( t.left != null && t.right != null ) // 这个节点有两个孩子节点
        {
            t.element = findMin( t.right ).element;
            t.right = remove( t.element, t.right );
        }
        else//这个节点只有一个孩子节点或没有孩子节点
            t = ( t.left != null ) ? t.left : t.right;
        return t;
    }

   //在二叉搜索树中找最小值节点
    private BinaryNode<T> findMin( BinaryNode<T> t )
    {
        if( t == null )
            return null;
        else if( t.left == null )
            return t;
        return findMin( t.left );
    }

    //在二叉搜索树中找最大值节点
    private BinaryNode<T> findMax( BinaryNode<T> t )
    {
        if( t != null )
            while( t.right != null )
                t = t.right;

        return t;
    }

   //是否包含
    private boolean contains( T x, BinaryNode<T> t )
    {
        if( t == null )
            return false;
            
        int compareResult = x.compareTo( t.element );
            
        if( compareResult < 0 )
            return contains( x, t.left );
        else if( compareResult > 0 )
            return contains( x, t.right );
        else
            return true;    // Match
    }

   //中序遍历二叉树
    private void printTree( BinaryNode<T> t )
    {
        if( t != null )
        {
            printTree( t.left );
            System.out.print(t.element+"  ");
            printTree( t.right );
        }
       
    }

    // 二叉搜索树节点类
    private static class BinaryNode<T>
    {
            // Constructors
        BinaryNode( T theElement )
        {
            this( theElement, null, null );
        }

        BinaryNode( T theElement, BinaryNode<T> lt, BinaryNode<T> rt )
        {
            element  = theElement;
            left     = lt;
            right    = rt;
        }

        T element;            // The data in the node
        BinaryNode<T> left;   // Left child
        BinaryNode<T> right;  // Right child
    }


      /** 二叉搜索树的根 */
    private BinaryNode<T> root;


        // 测试
    public static void main( String [ ] args )
    {
        BinarySearchTree<Integer> t = new BinarySearchTree<Integer>( );
        final int NUMS = 100;
        final int GAP  =   37;

        System.out.println( "Checking... (no more output means success)" );

        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( i );
         t.printTree( );
       System.out.printf("\n\n");
       
       for( int i = 1; i < NUMS; i+= 2 )
            t.remove( i );
           t.printTree( );
        System.out.println();
       
        if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
            System.out.println( "FindMin or FindMax error!" );

          
        for( int i = 2; i < NUMS; i+=2 )
             if( !t.contains( i ) )
                 System.out.println( "Find error1!" );

        for( int i = 1; i < NUMS; i+=2 )
        {
            if( t.contains( i ) )
                System.out.println( "Find error2!" );
        }
    }
}

下载源码：