C++數據結構之二叉搜索樹的實現詳解

Posted on by

前言

今天我們來學一個新的數據結構：二叉搜索樹。

介紹

二叉搜索樹也稱作二叉排序樹，它具有以下性質：

  • 非空左子樹的所有鍵值小於其根節點的鍵值
  • 非空右子樹的所有鍵值大於其根節點的鍵值
  • 左，右子樹都是二叉搜索樹

那麼我先畫一個二叉搜索樹給大傢看看，是不是真的滿足上面的性質。

我們就以根節點6為例子來看，我們會發現比6小的都在6的左邊，而比6大的都在6的右邊。對於6的左右子樹來說，所有的節點都遵循這個規則。

同時我們還可以發現如果對搜索二叉樹進行一個中序遍歷，我們得到的序列是個有序序列，這就是為什麼二叉搜索樹也可以稱作二叉排序樹。

實現

節點的實現

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

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

二叉搜索樹的查找

二叉搜索樹的查找思路很簡單：要找的值比當前節點小就去左子樹找，比當前節點大就往右子樹找，找到空節點就說明沒找到返回false即可。

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

bool findR(const T &val, Node *root) //T為節點的K, Node為節點
{
    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為二叉搜索樹的根節點
    while (cur)
    {
        if (val < cur->_key)
        {
            cur = cur->_left;
        }
        else if (val > cur->_key)
        {
            cur = cur->_right;
        }
        else
        {
            return true;
        }
    }
    return false;
}

二叉搜索樹的插入

二叉搜索樹的插入和查找差別不大，首先尋找插入位置，比當前節點小就往左子樹找，比當前節點大就往右子樹找，直到找到空指針時，就可以進行一個插入。

那麼要插入的值和當前節點相同該怎麼辦呢？我們此時實現的二叉搜索樹是一個無重復元素的二叉搜索樹，所以對於相同的值我采取的方式是返回一個false，大傢如果想實現一個有重復元素的二叉搜索樹，可以選擇將重復的值放在右子樹或左子樹都可。

二叉搜索樹的插入和查找一樣，有遞歸和非遞歸兩個版本，首先我們先來看看非遞歸的版本。

bool insert(const T &val)
{
    //空樹直接改變根節點
    if (_root == nullptr)
    {
        _root = new Node(val);
        return true;
    }
    
     //非空樹先尋找插入位置
    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;
        }
    }
    //判斷新節點該插入到哪裡
    cur = new Node(val);
    if (val < pre->_key)
    {
        pre->_left = cur;
    }
    else
    {
        pre->_right = cur;
    }
    return true;
}

接下來用一個動畫來表示一下這個插入過程。

接下來我們來看看遞歸版本是如何實現的

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;
    }
}

此時我們可以發現，遞歸版本沒有非遞歸版本中的parent指針瞭，參數列表中隻有一個root指針，這是為什麼呢？

我們可以看見我們的root指針不僅是一個指針，同時它還是一個引用。這就意味著我們對root的修改也可以影響上一層傳遞過來的指針的值。所以此時我們不需要parent指針，就可以對上一個節點的指針進行一個修改。

二叉搜索樹的刪除

理論部分：

二叉搜索樹的刪除相比前面兩個要麻煩那麼一丟丟，首先當然是找要刪除的節點，找到後通常有以下三種情況：

  • 此節點無左右子樹
  • 此節點有右子樹或右子樹
  • 此節點有左右子樹

我們要做的就是對這三種情況分別進行一個處理。

1.首先是此節點無左右子樹，這種情況我們直接將此節點刪除即可

2.然後是此節點隻有一顆子樹，這個也比較簡單，如果此節點是父節點的左節點，那麼我們隻需要將父節點的左指針改成指向此節點的子樹即可。

3.最後一種就是既有左子樹又有右子樹的情況瞭，此時為瞭不破壞結構，我們需要用到替換刪除法。首先我們先找到要刪除的節點，然後找節點的左子樹的最右節點或右子樹的最左節點，將兩個節點進行一下互換，再將原節點刪除。

代碼部分：

首先是非遞歸版本

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 //找到瞭進行刪除
        {
            if (cur->_left == nullptr) //左子樹為空
            {
                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) //右子樹為空
            {
                if (cur == _root)
                {
                    _root = cur->_left;
                }
                else
                {
                    if (cur == pre->_left)
                    {
                        pre->_left = cur->_left;
                    }
                    else
                    {
                        pre->_right = cur->_left;
                    }
                }
                delete cur;
            }
            else //左右子樹都不為空
            {
                //找左子樹的最右節點
                Node *tmp = cur->_left;
                Node *tmp_pre = cur;
                while (tmp->_right) 
                {
                    tmp_pre = tmp;
                    tmp = tmp->_right;
                }
				//節點互換
                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;
}

接下來是遞歸版本

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)//左子樹為空
        {
            root = root->_right;
        }
        else if (root->_right == nullptr)//右子樹為空
        {
            root = root->_left;
        }
        else //左右子樹都不為空
        {
            Node *cur = root->_left;
            while (cur->_right)
            {
                cur = cur->_right;
            }
            swap(cur->_key, root->_key);
            return eraseR(val, root->_left);
        }
        return true;
    }
}

總結

大傢覺得二叉搜索樹的時間復雜度是多少呢？O(logn)嗎？不，它的時間復雜度還是O(n)，當插入數據是有序的，二叉搜索樹會發生退化，變成一個單支樹。比如下面這張圖：

為瞭解決這個問題，有人對二叉搜索樹進行瞭一些優化，如：AVL樹和紅黑樹，之後我也會帶著大傢來實現一個完整的AVL樹和紅黑樹

到此這篇關於C++數據結構之二叉搜索樹的實現詳解的文章就介紹到這瞭,更多相關C++二叉搜索樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：