二叉排序树

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

博客分类：
• 查找

java 数据结构 算法  

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

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）。