学习“五大经典查找”(3)

今天就聊聊这个”五大经典查找“中的最后一个”二叉排序树“，又叫二叉查找树。

1. 概念


如图就是一棵二叉排序树:


2.实际操作：

    我们都知道，对一个东西进行操作，无非就是增删查改，接下来我们就聊聊其中的基本操作。

    <1> 插入：相信大家对“排序树”的概念都清楚了吧，那么插入的原理就很简单了。
比如说我们插入一个20到这棵树中。

首先：20跟50比，发现20是老小，不得已，得要归结到50的左子树中去比较。
然后：20跟30比，发现20还是老小。
再然后：20跟10比，发现自己是老大，随即插入到10的右子树中。
最后： 效果呈现图如下：



<2>查找：相信懂得了插入，查找就跟容易理解了。

就拿上面一幅图来说，比如我想找到节点10.

首先：10跟50比，发现10是老小，则在50的左子树中找。
然后：10跟30比，发现还是老小，则在30的左子树中找。
再然后:  10跟10比，发现一样，然后就返回找到的信号。
        
<3>删除：删除节点在树中还是比较麻烦的，主要有三种情况。

《1》 删除的是“叶节点20“，这种情况还是比较简单的，删除20不会破坏树的结构。如图：



《2》删除”单孩子节点90“，这个情况相比第一种要麻烦一点点，需要把他的孩子顶上去。


《3》删除“左右孩子都有的节点50”，这个让我在代码编写上纠结了好长时间，问题很直白，我把50删掉了，谁顶上去了问题，是左孩子呢？还是右孩子呢？还是另有蹊跷？这里我就坦白吧，不知道大家可否知道“二叉树”的中序遍历，现在可以当公式记住吧，就是找到右节点的左子树最左孩子。

比如：首先 找到50的右孩子70。
然后  找到70的最左孩子，发现没有，则返回自己。
最后  原始图和最终图如下。





3.说了这么多，上代码说话。

//二叉搜索树
public class BinarySearchTree<T extends Comparable<? super T>>
{

   /** 二叉排序树的根 */
    private BinaryNode<T> root;

    /**
     * 构造一棵空树.
     */
    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
           ;  // 重复的,什么也不做。当然你也可以将重复的数据加入右边。
        return t;
    }

    //删除
    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
    }


      

        // 测试
    public static void main( String [ ] args )
    {
         //创建二叉排序树   
        int list[]={ 50, 30, 70, 10, 40, 90, 80};
        BinarySearchTree<Integer> bsTree = new BinarySearchTree<Integer>( );
         for( int i = 0; i<list.length;i++)
            bsTree.insert( list[i] );
      
           System.out.println("中序遍历的原始数据：");  
            //中序遍历   
           bsTree.printTree( );
           System.out.printf("\n--------------------------------");  

         //查找一个节点   
       System.out.printf("\n10在二叉树中是否包含：" + bsTree.contains(new Integer(10)));  
   
           System.out.printf("\n---------------------------------");  

        //插入一个节点   
             bsTree.insert(20);  
   
             System.out.printf("\n20插入到二叉树，中序遍历后：");  
   
             //中序遍历   
             bsTree.printTree();  
             System.out.printf("\n-----------------------------------\n");  

          System.out.printf("删除叶子节点 20， \n中序遍历后：");  
   
             //删除一个节点(叶子节点)   
             bsTree.remove(new Integer(20));  
   
             //再次中序遍历   
             bsTree.printTree();   
             System.out.printf("\n****************************************\n");  
   
             System.out.printf("删除单孩子节点 90， \n中序遍历后：");  
   
             //删除单孩子节点   
             bsTree.remove(new Integer(90));  
   
             //再次中序遍历   
             bsTree.printTree();  
             System.out.printf("\n****************************************\n");  

             System.out.printf("删除根节点 50， \n中序遍历后：");  
             //删除根节点   
             bsTree.remove(new Integer(50));  
             bsTree.printTree();      
           
    }
}

public class UnderflowException extends RuntimeException{}

运行结果：

D:\java>java   BinarySearchTree
中序遍历的原始数据：
10  30  40  50  70  80  90
------------------------------------------------
10在二叉树中是否包含：true
--------------------------------------------------
20插入到二叉树，中序遍历后：10  20  30  40  50  70  80  90
-------------------------------------------------
删除叶子节点 20，
中序遍历后：10  30  40  50  70  80  90
*************************************************
删除单孩子节点 90，
中序遍历后：10  30  40  50  70  80
************************************************
删除根节点 50，
中序遍历后：10  30  40  70  80

值的注意的是：二叉排序树同样采用“空间换时间”的做法。

突然发现，二叉排序树的中序遍历同样可以排序数组，呵呵，不错！

PS:  插入操作：O(LogN)。

       删除操作：O(LogN)。

       查找操作：O(LogN）。

下载源码: