美文网首页
数据结构:二叉查找树C++实现

数据结构:二叉查找树C++实现

作者: 胡博要毕业 | 来源:发表于2018-10-04 18:25 被阅读0次

    (一) 什么是二叉查找树

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

    图一 二叉搜索树

    (二) 二叉查找树实现

    1. 结点的定义

    结点应该包括keyvalueleftright 四个元素。

    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()
    {
    }
    

    相关文章

      网友评论

          本文标题:数据结构:二叉查找树C++实现

          本文链接:https://www.haomeiwen.com/subject/uvnxaftx.html