C++數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹(shù)的實(shí)現(xiàn)詳解

更新時(shí)間：2022年08月22日 14:19:42 作者：。菀枯。

二叉搜索樹(shù)作為一個(gè)經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，具有鏈表的快速插入與刪除的特點(diǎn)，同時(shí)查詢效率也很優(yōu)秀，所以應(yīng)用十分廣泛。本文將詳細(xì)講講二叉搜索樹(shù)的C++實(shí)現(xiàn)，需要的可以參考一下

前言

今天我們來(lái)學(xué)一個(gè)新的數(shù)據(jù)結(jié)構(gòu)：二叉搜索樹(shù)。

介紹

二叉搜索樹(shù)也稱作二叉排序樹(shù)，它具有以下性質(zhì)：

非空左子樹(shù)的所有鍵值小于其根節(jié)點(diǎn)的鍵值
非空右子樹(shù)的所有鍵值大于其根節(jié)點(diǎn)的鍵值
左，右子樹(shù)都是二叉搜索樹(shù)

那么我先畫(huà)一個(gè)二叉搜索樹(shù)給大家看看，是不是真的滿足上面的性質(zhì)。

我們就以根節(jié)點(diǎn)6為例子來(lái)看，我們會(huì)發(fā)現(xiàn)比6小的都在6的左邊，而比6大的都在6的右邊。對(duì)于6的左右子樹(shù)來(lái)說(shuō)，所有的節(jié)點(diǎn)都遵循這個(gè)規(guī)則。

同時(shí)我們還可以發(fā)現(xiàn)如果對(duì)搜索二叉樹(shù)進(jìn)行一個(gè)中序遍歷，我們得到的序列是個(gè)有序序列，這就是為什么二叉搜索樹(shù)也可以稱作二叉排序樹(shù)。

實(shí)現(xiàn)

節(jié)點(diǎn)的實(shí)現(xiàn)

template <typename K>
struct BTreeNode
{
	BTreeNode<K>* _left;
	BTreeNode<K>* _right;
	K _key;

	BTreeNode(const K& key)
		:_key(key), _left(nullptr), _right(nullptr)
	{}
};

二叉搜索樹(shù)的查找

二叉搜索樹(shù)的查找思路很簡(jiǎn)單：要找的值比當(dāng)前節(jié)點(diǎn)小就去左子樹(shù)找，比當(dāng)前節(jié)點(diǎn)大就往右子樹(shù)找，找到空節(jié)點(diǎn)就說(shuō)明沒(méi)找到返回false即可。

首先我們先看看遞歸的版本。

bool findR(const T &val, Node *root) //T為節(jié)點(diǎn)的K, Node為節(jié)點(diǎn)
{
    if (root == nullptr)
    {
        return false;
    }

    if (root->_key < val)
    {
        return findR(root->_right, val);
    }
    else if (root->_key > val)
    {
        return findR(root->_left, val);
    }
    else
    {
        return true;
    }
}

接著看看非遞歸的版本

bool find(const T &val)
{
    Node *cur = _root; //_root為二叉搜索樹(shù)的根節(jié)點(diǎn)
    while (cur)
    {
        if (val < cur->_key)
        {
            cur = cur->_left;
        }
        else if (val > cur->_key)
        {
            cur = cur->_right;
        }
        else
        {
            return true;
        }
    }
    return false;
}

二叉搜索樹(shù)的插入

二叉搜索樹(shù)的插入和查找差別不大，首先尋找插入位置，比當(dāng)前節(jié)點(diǎn)小就往左子樹(shù)找，比當(dāng)前節(jié)點(diǎn)大就往右子樹(shù)找，直到找到空指針時(shí)，就可以進(jìn)行一個(gè)插入。

那么要插入的值和當(dāng)前節(jié)點(diǎn)相同該怎么辦呢？我們此時(shí)實(shí)現(xiàn)的二叉搜索樹(shù)是一個(gè)無(wú)重復(fù)元素的二叉搜索樹(shù)，所以對(duì)于相同的值我采取的方式是返回一個(gè)false，大家如果想實(shí)現(xiàn)一個(gè)有重復(fù)元素的二叉搜索樹(shù)，可以選擇將重復(fù)的值放在右子樹(shù)或左子樹(shù)都可。

二叉搜索樹(shù)的插入和查找一樣，有遞歸和非遞歸兩個(gè)版本，首先我們先來(lái)看看非遞歸的版本。

bool insert(const T &val)
{
    //空樹(shù)直接改變根節(jié)點(diǎn)
    if (_root == nullptr)
    {
        _root = new Node(val);
        return true;
    }
    
     //非空樹(shù)先尋找插入位置
    Node *pre = nullptr;
    Node *cur = _root;
    while (cur)
    {
        if (val > cur->_key)
        {
            pre = cur;
            cur = cur->_right;
        }
        else if (val < cur->_key)
        {
            pre = cur;
            cur = cur->_left;
        }
        else
        {
            return false;
        }
    }
    //判斷新節(jié)點(diǎn)該插入到哪里
    cur = new Node(val);
    if (val < pre->_key)
    {
        pre->_left = cur;
    }
    else
    {
        pre->_right = cur;
    }
    return true;
}

接下來(lái)用一個(gè)動(dòng)畫(huà)來(lái)表示一下這個(gè)插入過(guò)程。

接下來(lái)我們來(lái)看看遞歸版本是如何實(shí)現(xiàn)的

bool insertR(const T &val, Node *&root)
{
    if (root == nullptr)
    {
        Node *newNode = new Node(val);
        root = newNode;
    }

    if (root->_key < val)
    {
        return insertR(val, root->_right);
    }
    else if (root->_key > val)
    {
        return insertR(val, root->_left);
    }
    else
    {
        return false;
    }
}

此時(shí)我們可以發(fā)現(xiàn)，遞歸版本沒(méi)有非遞歸版本中的parent指針了，參數(shù)列表中只有一個(gè)root指針，這是為什么呢？

我們可以看見(jiàn)我們的root指針不僅是一個(gè)指針，同時(shí)它還是一個(gè)引用。這就意味著我們對(duì)root的修改也可以影響上一層傳遞過(guò)來(lái)的指針的值。所以此時(shí)我們不需要parent指針，就可以對(duì)上一個(gè)節(jié)點(diǎn)的指針進(jìn)行一個(gè)修改。

二叉搜索樹(shù)的刪除

理論部分：

二叉搜索樹(shù)的刪除相比前面兩個(gè)要麻煩那么一丟丟，首先當(dāng)然是找要?jiǎng)h除的節(jié)點(diǎn)，找到后通常有以下三種情況：

此節(jié)點(diǎn)無(wú)左右子樹(shù)
此節(jié)點(diǎn)有右子樹(shù)或右子樹(shù)
此節(jié)點(diǎn)有左右子樹(shù)

我們要做的就是對(duì)這三種情況分別進(jìn)行一個(gè)處理。

1.首先是此節(jié)點(diǎn)無(wú)左右子樹(shù)，這種情況我們直接將此節(jié)點(diǎn)刪除即可

2.然后是此節(jié)點(diǎn)只有一顆子樹(shù)，這個(gè)也比較簡(jiǎn)單，如果此節(jié)點(diǎn)是父節(jié)點(diǎn)的左節(jié)點(diǎn)，那么我們只需要將父節(jié)點(diǎn)的左指針改成指向此節(jié)點(diǎn)的子樹(shù)即可。

3.最后一種就是既有左子樹(shù)又有右子樹(shù)的情況了，此時(shí)為了不破壞結(jié)構(gòu)，我們需要用到替換刪除法。首先我們先找到要?jiǎng)h除的節(jié)點(diǎn)，然后找節(jié)點(diǎn)的左子樹(shù)的最右節(jié)點(diǎn)或右子樹(shù)的最左節(jié)點(diǎn)，將兩個(gè)節(jié)點(diǎn)進(jìn)行一下互換，再將原節(jié)點(diǎn)刪除。

代碼部分：

首先是非遞歸版本

bool erase(const T &val)
{
    Node *cur = _root;
    Node *pre = nullptr;
    //尋找刪除位置
    while (cur)
    {
        if (cur->_key < val)
        {
            pre = cur;
            cur = cur->_right;
        }
        else if (cur->_key > val)
        {
            pre = cur;
            cur = cur->_left;
        }
        else //找到了進(jìn)行刪除
        {
            if (cur->_left == nullptr) //左子樹(shù)為空
            {
                if (cur == _root)
                {
                    _root = cur->_right;
                }
                else
                {
                    if (cur == pre->_left)
                    {
                        pre->_left = cur->_right;
                    }
                    else
                    {
                        pre->_right = cur->_right;
                    }
                }
                delete cur;
            }
            else if (cur->_right == nullptr) //右子樹(shù)為空
            {
                if (cur == _root)
                {
                    _root = cur->_left;
                }
                else
                {
                    if (cur == pre->_left)
                    {
                        pre->_left = cur->_left;
                    }
                    else
                    {
                        pre->_right = cur->_left;
                    }
                }
                delete cur;
            }
            else //左右子樹(shù)都不為空
            {
                //找左子樹(shù)的最右節(jié)點(diǎn)
                Node *tmp = cur->_left;
                Node *tmp_pre = cur;
                while (tmp->_right) 
                {
                    tmp_pre = tmp;
                    tmp = tmp->_right;
                }
				//節(jié)點(diǎn)互換
                cur->_key = tmp->_key;

                if (tmp == tmp_pre->_left)
                {
                    tmp_pre->_left = tmp->_left;
                }
                else
                {
                    tmp_pre->_right = tmp->_left;
                }

                delete tmp;
            }
            return true;
        }
    }
    return false;
}

接下來(lái)是遞歸版本

bool eraseR(const T &val, Node *&root)
{
    //找不到返回false
    if (root == nullptr)
    {
        return false;
    }
	//尋找插入位置
    if (root->_key < val)
    {
        return eraseR(val, root->_right);
    }
    else if (root->_key > val)
    {
        return eraseR(val, root->_left);
    }
    else
    {
        if (root->_left == nullptr)//左子樹(shù)為空
        {
            root = root->_right;
        }
        else if (root->_right == nullptr)//右子樹(shù)為空
        {
            root = root->_left;
        }
        else //左右子樹(shù)都不為空
        {
            Node *cur = root->_left;
            while (cur->_right)
            {
                cur = cur->_right;
            }
            swap(cur->_key, root->_key);
            return eraseR(val, root->_left);
        }
        return true;
    }
}

總結(jié)

大家覺(jué)得二叉搜索樹(shù)的時(shí)間復(fù)雜度是多少呢？O(logn)嗎？不，它的時(shí)間復(fù)雜度還是O(n)，當(dāng)插入數(shù)據(jù)是有序的，二叉搜索樹(shù)會(huì)發(fā)生退化，變成一個(gè)單支樹(shù)。比如下面這張圖：

為了解決這個(gè)問(wèn)題，有人對(duì)二叉搜索樹(shù)進(jìn)行了一些優(yōu)化，如：AVL樹(shù)和紅黑樹(shù)，之后我也會(huì)帶著大家來(lái)實(shí)現(xiàn)一個(gè)完整的AVL樹(shù)和紅黑樹(shù)

到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹(shù)的實(shí)現(xiàn)詳解的文章就介紹到這了,更多相關(guān)C++二叉搜索樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: