数据结构之二叉搜索树-创新互联

一。定义：二叉搜索树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 任意节点的左、右也分别为二叉查找树。

4. 没有键值相等的节点（no duplicate nodes）。

根据二叉搜索树的特点知：对二叉搜索树进行中序遍历得到的结点序列必然是一个有序序列。

一棵二叉搜索树：

  根据树的结构，我们可以封装一个结点的结构BSNode：

template  
struct BSNode  
{  
    BSNode* _left;  
    BSNode* _right;  
    K _key;  
    V _value;  
    BSNode(const K& key, const V& value)  
        :_left(NULL)  
        , _right(NULL)  
        ,_key(key)  
        , _value(value)  
    {}  
};

 在这里树的结构封装了key/value形式的键值对。

二叉搜索树的结构我们更加关注的是它的增删查改功能。而且在这过程中我们要保证整棵树中没有重复的key值（结点的值）

所以封装一棵二叉搜索树BSTree：

template  
class BSTree  
{  
public:  
    typedef BSNode Node;//增删改查功能  
    protected:  
    Node* _root;  
};

二。实现

  (一）插入新结点

bool Insert(const K& key, const V& value)//非递归形式  
    {  
        if (_root == NULL)  
        {  
            _root = new Node(key, value);  
            return true;  
        }  
        Node* parent = NULL;  
        Node* cur = _root;  
        while (cur)  
        {  
            if (cur->_key > key)  
            {  
                parent = cur;  
                cur = cur->_left;  
            }  
            else if (cur->_key < key)  
            {  
                parent = cur;  
                cur = cur->_right;  
            }  
            else  
                return false;  
        }  
        if (parent->_left == NULL && parent->_key > key)  
        {  
            parent->_left = new Node(key, value);  
        }  
        else if (parent->_right == NULL && parent->_key < key)  
        {  
            parent->_right = new Node(key, value);  
        }  
        return true;  
    }

bool Insert_R(const K& key, const V& value)//插入的递归实现  
    {  
        return _Insert_R(_root, key, value);  
    }bool _Insert_R(Node*& root,const K& key, const V& value)  
    {  
        if (root == NULL)  
        {  
            root = new Node(key, value);  
            return true;  
        }  
        if (root->_key > key)  
            _Insert_R(root->_left, key, value);  
        else if (root->_key < key)  
            _Insert_R(root->_right, key, value);  
        else  
            return false;  
        return false;  
    }

插入节点的思路就是递归的找要插入的位置，直到root为NULL，那么当前位置就是要插入的位置。

（二）查找结点，返回该结点

Node* Find(const K& key) //非递归实现  
    {  
        Node* cur = _root;  
        while (cur)  
        {  
            if (cur->_key > key)  
            {  
                cur = cur->_left;  
            }  
            else if (cur->_key < key)  
            {  
                cur = cur->_right;  
            }  
            else  
                return cur;  
        }  
        return NULL;  
    }

Node* Find_R(const K& key)//递归实现  
    {  
        return _Find_R(_root, key);  
    }Node* _Find_R(Node* root,const K& key)  
    {  
        if (root == NULL)  
            return NULL;  
        if (root->_key > key)  
            _Find_R(root->_left, key);  
        else if (root->_key < key)  
            _Find_R(root->_right, key);  
        else  
            return root;  
    }

  查找的实现就是分三种情况，当前结点key大于key，小于key，等于key。大于key递归的在当前结点的右子树查找，小于在左子树找，等于就返回结点。

（三）删除结点，使剩下结点仍是一棵二叉搜索树

bool Remove(const K& key)//非递归实现
{
        return _Remove(_root, key);  
  }

bool _Remove(Node* root, const K& key)  
    {  
        if (root == NULL)  
            return false;  
        Node* parent = NULL;  
        Node* cur = root;  
        Node* 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 (parent && parent->_left == cur)  
                        parent->_left = cur->_right;  
                    else if (parent && parent->_right == cur)  
                        parent->_right = cur->_right;  
                    else  
                        _root = cur->_right;  
                }  
                else if (cur->_right == NULL)//待删除结点右为空  
                {  
                    if (parent && parent->_left == cur)  
                        parent->_left = cur->_left;  
                    else if (parent &&parent->_right == cur)  
                        parent->_right = cur->_left;  
                    else  
                        _root = cur->_left;  
                }  
                else if (cur->_left == NULL && cur->_right == NULL)//待删除结点左右都为空  
                {  
                    if (parent && parent->_left == cur)  
                        parent->_left = NULL;  
                    else if (parent && parent->_right == cur)  
                        parent->_right = NULL;  
                    else  
                        _root = NULL;  
                }  
                else if (cur->_left && cur->_right)//待删除结点左右都不为空  
                {  
                    //找出右子树的最左结点  
                    Node* firstleft = cur->_right;  
                    parent = cur;  
                    while (firstleft->_left)  
                    {  
                        parent = firstleft;  
                        firstleft = firstleft->_left;  
                    }  
                    del = firstleft;  
                    swap(cur->_key, firstleft->_key);  
                    swap(cur->_value, firstleft->_value);  
                    //判断最左结点是它父节点的左结点还是右结点  
                    if (parent && parent->_left == firstleft)  
                    {  
                        parent->_left = firstleft->_right;  
                    }  
                    else if (parent && parent->_right == firstleft)  
                    {  
                        parent->_right = firstleft->_right;  
                    }  
                    else //parent==NULL。待删除结点的右边只有一个结点，则最左结点就是它  
                    {  
                        root->_right = NULL;  
                    }  
                }  
                delete del;  
                return true;  
            }  
                    }  
        return false;  
    }

bool Remove_R(const K& key)//递归实现 
{  
    return _Remove_R(_root, key);  
}bool _Remove_R(Node*& root, const K& key)  
{  
    if (root == NULL)  
        return false;  
    if (root->_key > key)  
    {  
        _Remove_R(root->_left, key);   
    }  
    else if (root->_key < key)  
    {  
        _Remove_R(root->_right, key);  
    }  
    else  
    {  
        Node* del = root;  
        if (root->_left == NULL&&root->_right == NULL)  
        {  
            root = NULL;  
        }  
        else if (root->_left == NULL)  
        {  
            root = root->_right;  
        }  
        else if (root->_right == NULL)  
        {  
            root = root->_left;  
        }  
        else  
        {  
            Node* parent = NULL;  
            Node* firstleft = root->_right;  
            while (firstleft->_left)  
              {  
                parent = firstleft;  
                firstleft = firstleft->_left;  
            }  
            del = firstleft;  
  
            swap(root->_key, firstleft->_key);  
            swap(root->_value, firstleft->_value);  
  
            if (parent && parent->_left == firstleft)  
            {  
                parent->_left = firstleft->_right;  
            }  
            else if (parent && parent->_right == firstleft)  
            {  
                parent->_right = firstleft->_right;  
            }  
            else //parent==NULL。待删除结点的右边只有一个结点，则最左结点就是它  
            {  
                root->_right = NULL;  
            }  
        }  
        delete del;  
        return true;  
    }  
    return false;  
}

 删除节点要考虑到的因素就要多了。我们可以划分子问题的方法来解决：

   查找待删除的结点，每次判断：

1. 当前结点key值大于key。递归进入左子树，继续查找。

2. 当前结点key值小于key。递归进入右子树，继续查找。

3. 当前结点key值等于key。在这又分为4种情况：

• 当前结点的左子树为空。删除当前结点，把右子树给当前指针

• 当前结点的右子树为空。删除当前结点，把左子树给当前指针

• 当前结点的左右子树都为空。把根指针置空，删除当前结点。

• 当前结点的左右子树都不为空。找到右子树的最左结点，和待删除结点交换值，删除最左结点。

把这些因素都考虑周全就可以准确的删除二叉搜索树的任何一个结点。

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。