數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹

一。定義：二叉搜索樹（Binary Search Tree），也稱有序二叉樹（ordered binary tree）,排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質(zhì)的二叉樹：

1. 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

2. 若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

3. 任意節(jié)點(diǎn)的左、右也分別為二叉查找樹。

4. 沒有鍵值相等的節(jié)點(diǎn)（no duplicate nodes）。

根據(jù)二叉搜索樹的特點(diǎn)知：對(duì)二叉搜索樹進(jìn)行中序遍歷得到的結(jié)點(diǎn)序列必然是一個(gè)有序序列。

一棵二叉搜索樹：

    根據(jù)樹的結(jié)構(gòu)，我們可以封裝一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)BSNode：

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

 在這里樹的結(jié)構(gòu)封裝了key/value形式的鍵值對(duì)。

二叉搜索樹的結(jié)構(gòu)我們更加關(guān)注的是它的增刪查改功能。而且在這過程中我們要保證整棵樹中沒有重復(fù)的key值（結(jié)點(diǎn)的值）

所以封裝一棵二叉搜索樹BSTree：

template<class K,class V>  
class BSTree  
{  
public:  
    typedef BSNode<K, V> Node;<pre name="code" class="cpp">//增刪改查功能  
    protected:  
    Node* _root;  
};

二。實(shí)現(xiàn)

    (一）插入新結(jié)點(diǎn)

bool Insert(const K& key, const V& value)//<span >非遞歸形式</span>  
    {  
        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)//<span >插入的遞歸實(shí)現(xiàn)</span>  
    {  
        return _Insert_R(_root, key, value);  
    }</span><pre name="code" class="cpp">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;  
    }

   插入節(jié)點(diǎn)的思路就是遞歸的找要插入的位置，直到root為NULL，那么當(dāng)前位置就是要插入的位置。

（二）查找結(jié)點(diǎn)，返回該結(jié)點(diǎn)

Node* Find(const K& key) //<span >非遞歸實(shí)現(xiàn)</span>  
    {  
        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)//<span >遞歸實(shí)現(xiàn)</span>  
    {  
        return _Find_R(_root, key);  
    }<pre name="code" class="cpp">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;  
    }

   查找的實(shí)現(xiàn)就是分三種情況，當(dāng)前結(jié)點(diǎn)key大于key，小于key，等于key。大于key遞歸的在當(dāng)前結(jié)點(diǎn)的右子樹查找，小于在左子樹找，等于就返回結(jié)點(diǎn)。

（三）刪除結(jié)點(diǎn)，使剩下結(jié)點(diǎn)仍是一棵二叉搜索樹

bool Remove(const K& key)//非遞歸實(shí)現(xiàn)
{
        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;  
                //待刪除結(jié)點(diǎn)左為空  
                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)//待刪除結(jié)點(diǎn)右為空  
                {  
                    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)//待刪除結(jié)點(diǎn)左右都為空  
                {  
                    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)//待刪除結(jié)點(diǎn)左右都不為空  
                {  
                    //找出右子樹的最左結(jié)點(diǎn)  
                    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);  
                    //判斷最左結(jié)點(diǎn)是它父節(jié)點(diǎn)的左結(jié)點(diǎn)還是右結(jié)點(diǎn)  
                    if (parent && parent->_left == firstleft)  
                    {  
                        parent->_left = firstleft->_right;  
                    }  
                    else if (parent && parent->_right == firstleft)  
                    {  
                        parent->_right = firstleft->_right;  
                    }  
                    else //parent==NULL。待刪除結(jié)點(diǎn)的右邊只有一個(gè)結(jié)點(diǎn)，則最左結(jié)點(diǎn)就是它  
                    {  
                        root->_right = NULL;  
                    }  
                }  
                delete del;  
                return true;  
            }  
                    }  
        return false;  
    }

bool Remove_R(const K& key)//遞歸實(shí)現(xiàn) 
{  
    return _Remove_R(_root, key);  
}<pre name="code" class="cpp">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。待刪除結(jié)點(diǎn)的右邊只有一個(gè)結(jié)點(diǎn)，則最左結(jié)點(diǎn)就是它  
            {  
                root->_right = NULL;  
            }  
        }  
        delete del;  
        return true;  
    }  
    return false;  
}

  刪除節(jié)點(diǎn)要考慮到的因素就要多了。我們可以劃分子問題的方法來解決：

     查找待刪除的結(jié)點(diǎn)，每次判斷：

1. 當(dāng)前結(jié)點(diǎn)key值大于key。遞歸進(jìn)入左子樹，繼續(xù)查找。

2. 當(dāng)前結(jié)點(diǎn)key值小于key。遞歸進(jìn)入右子樹，繼續(xù)查找。

3. 當(dāng)前結(jié)點(diǎn)key值等于key。在這又分為4種情況：

• 當(dāng)前結(jié)點(diǎn)的左子樹為空。刪除當(dāng)前結(jié)點(diǎn)，把右子樹給當(dāng)前指針

• 當(dāng)前結(jié)點(diǎn)的右子樹為空。刪除當(dāng)前結(jié)點(diǎn)，把左子樹給當(dāng)前指針

• 當(dāng)前結(jié)點(diǎn)的左右子樹都為空。把根指針置空，刪除當(dāng)前結(jié)點(diǎn)。

• 當(dāng)前結(jié)點(diǎn)的左右子樹都不為空。找到右子樹的最左結(jié)點(diǎn)，和待刪除結(jié)點(diǎn)交換值，刪除最左結(jié)點(diǎn)。

             
把這些因素都考慮周全就可以準(zhǔn)確的刪除二叉搜索樹的任何一個(gè)結(jié)點(diǎn)。