(一) 什么是二叉查找树

二叉查找树，也叫二叉搜索树，英文是Binary Search Tree，简称BST，它是以一颗二叉树来组织的，如图一所示，这样一颗树可以使用链表数据结构来表示，其中每个结点就是一个对象。除了key和数据之外，每个结点还包含属性left、right 和 p，它们分别指向结点的左孩子、右孩子和双亲。如果某个孩子结点和父结点不存在，则相应属性的值为NIL。

图一 二叉搜索树

(二) 二叉查找树实现

1. 结点的定义

结点应该包括key 、 value 、left 和 right 四个元素。

template<class K, class V>
struct BST_node
{
    K _key;
    V _value；
    BST_node<K, V> *_left;
    BST_node<K, V> *_right;

    BST_node(const K& key, const V& value)
                :_key(key), _value(value), _left(NULL), _right(NULL)
                {}
};

2. BST对象的定义

template<class K, class V>
class BST_tree
{
public:
    BST()
    :_root(NULL)
    {}

    bool Insert(const K& key, const V& value);          //插入新结点
    bool Remove(const K& key);                    //删除结点
    BST_node<K, V>* Find(const K& key);            //查找关键字

    void In_Order_Print_Tree();        //中序遍历打印
    void Post_Order_Print_Tree();   //后序遍历打印
    void Pre_Order_Print_Tree();    //前序遍历打印
    
protected:
    BST_node<K, V>* _root;
};

3. BST的插入操作

图二 BST的插入操作

template<class K, class V>
bool Insert(const K& key, const V& value)
{
    if( _root == NULL )
    {
        _root = new BST_node<K, V>(key, value);
        return true;
    }

    BST_node<K, V>* cur = _root;
    BST_node<K, V>* parent = _root;

    while( cur )        /*寻找插入位置的父结点parent*/
    {
        if( cur -> _key > key )
        {
            parent = cur;
            cur = cur -> _left;
        }
        else if( cur -> _key < key )
        {
            parent = cur;
            cur = cur -> _right;          
        }
        else
        {
            return false;
        }
    }

    if( key < parent -> _key )      /*小于父结点，插入到左结点*/
        parent -> _left = new BST_node<K, V>(key, value); 
    else                          /*大于父结点，插入到左结点*/
        parent -> _right = new BST_node<K, V>(key, value); 
    return ture;
}

4. BST的查询操作

BST_node<K, V>* Find(const K& key)
{
    if( _root == NULL )
        return NULL;
    
    BST_node<K, V>* cur = _root;

    while( cur )        
    {
        if( key == cur -> _key )
            return cur;
        else if( key > cur -> _key )      /*待查询key大于当前节点的key，则从其右子树再寻找*/
            cur = cur -> _right;          
        else                           /*待查询key小于当前节点的key，则从其左子树再寻找*/
            cur = cur -> _left;     
    }
    
    return NULL;      /*查询不到该key*/
}

5. BST的删除操作

从一颗二叉搜索树 T 中删除一个结点 y 的整个策略分三种情况，如图三。

• 如果 y 没有孩子结点，那么只是简单的将它删除，并修改 y 的父亲结点，用NULL来替换 y 结点。
• 如果 y 只有一个孩子， 那么删除 y 结点后，需要将其孩子提升到 y 的位置，并修改 y 的父结点， 用 y 的孩子来替换 y。
• 如果 y 有两个孩子，需要从 y 结点的右子树中寻找出一个最小key的结点 x， 让 x 占据原来 y 所在的位置， 并且y 的原来右子树成为 x 的新的右子树，y 的左子树成为 x 的新的左子树 。同时需要修改 x结点的父结点和 y结点父结点。
  如图三所示。
  

图三

bool Remove(const K& key)
{
    // 1.空树，根节点为空
    // 2.key结点没有有子树
    // 3.key结点有子树
        // a.key结点只有一个子树，左子树或者右子树
        // b.key结点有左右子树
    if( _root == NULL )
        return false;

    if( _root -> _left == NULL && _root -> _right == NULL )
    {          /*只有根结点*/
        if( key == _root -> _key )
        {
            delete _root;
            _root = NULL;
            return true;
        }
        else
            return false;

    }
        
    BST_node<K, V>* cur = _root;
    BST_node<K, V>* parent= _root;
   BST_node<K, V>* del= NULL;
    while( cur )       
    {
        if( cur -> _key > key )
        {
            parent = cur;
            cur = cur -> _left;
        }
        else if( cur -> _key < key )
        {
            parent = cur;
            cur = cur -> _right;          
        }
        else
        {
            /*找到该删除的结点*/
            del = cur;
            if( cur -> _left == NULL  )
            {    /*无左子树*/
                if( cur -> _right != NULL )
                {      /*但有右子树*/
                        if( parent -> _left == cur)
                            parent -> _left = cur -> _right;
                        else
                            parent -> _right = cur -> _right;
                }
                else
                {      /*也无右子树*/
                        if( parent -> _left == cur)
                            parent -> _left = NULL;
                        else
                            parent -> _right = NULL;                             
                }
            } 
            else if( cur -> _right == NULL )
            {    /*有左子树，但无右子树*/
                 if( parent->left == cur )     
                    parent -> _left = cur -> _left;
                 else
                    parent -> _right = cur -> _right;
            }
            else
            {    /*既有左子树和右子树*/
                BST_node<K, V>* first_left = cur -> _right ;  /*寻找右子树的最小的结点*/
                while( first_left )
                {
                    parent  = first_left;
                    first_left = first_left -> _left;
                }                  
                del = first_left;
                swap( cur -> _key, first_left -> _key );
                swap( cur -> _value, first_left -> _value );


                if( parent -> _left == first_left )    /*待删除结点的右子树的左子树非空*/
                    parent -> _left = first_left -> _right;
                else if( cur -> _left = first_left )   /*待删除结点的右子树的左子树为空*/
                    cur -> _right = first_left -> _right; 
                
            }
            delete del;
            return true;

        } 
         
        return false;
    }

(三) 测试代码

void  test()
{
}