您的位置：首頁(yè) > 軟件教程 > 教程 > BST 二叉搜索樹(shù) BinarySearchTree C++實(shí)現(xiàn)(遞歸/非遞歸)

BST 二叉搜索樹(shù) BinarySearchTree C++實(shí)現(xiàn)(遞歸/非遞歸)

來(lái)源：好特整理　|　時(shí)間：2024-08-21 10:22:09 |　閱讀：133　|　標(biāo)簽： a T S C in AR 搜索 EA c++ 　 |　分享到：

下載游戲

目錄二叉搜索樹(shù)基本概念常用結(jié)論用途二叉搜索樹(shù)的性能分析二叉搜索樹(shù)的操作查找插入刪除代碼實(shí)現(xiàn)BSTree.hpptest.cc 二叉搜索樹(shù) 基本概念二叉搜索樹(shù)(BST,Binary Search Tree) 二叉搜索樹(shù)又稱二叉排序樹(shù)，它或者是一棵空樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù): 若它的左子樹(shù)不為空

二叉搜索樹(shù)

基本概念

二叉搜索樹(shù)(BST,Binary Search Tree)

二叉搜索樹(shù)又稱二叉排序樹(shù)，它或者是一棵空樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù):

若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
它的左右子樹(shù)也分別為二叉搜索樹(shù)

BST 二叉搜索樹(shù) BinarySearchTree C++實(shí)現(xiàn)(遞歸/非遞歸)

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

二叉搜索樹(shù)/二叉查找樹(shù)也稱二叉排序樹(shù),因?yàn)槎媾判驑?shù)的中序遍歷結(jié)果是升序

常用結(jié)論

二叉搜索樹(shù)的左子樹(shù)一定小于根,右子樹(shù)一定大于根, 結(jié)合定義遞歸子樹(shù) 可以得到

左子樹(shù)的最右節(jié)點(diǎn)是左子樹(shù)的最大節(jié)點(diǎn),右子樹(shù)的最右節(jié)點(diǎn)是右子樹(shù)的最大節(jié)點(diǎn).
左子樹(shù)的最左節(jié)點(diǎn)是左子樹(shù)的最小節(jié)點(diǎn),右子樹(shù)的最左節(jié)點(diǎn)是右子樹(shù)的最小節(jié)點(diǎn).
二叉搜索樹(shù)的最小節(jié)點(diǎn)是左子樹(shù)的最左節(jié)點(diǎn),最大節(jié)點(diǎn)是右子樹(shù)的最右節(jié)點(diǎn)

用途

實(shí)際情況很少直接使用搜索二叉樹(shù),多是根據(jù)搜索二叉樹(shù)的高效搜索特性,衍生出更為實(shí)用的高階數(shù)據(jù)結(jié)構(gòu),例如平衡二叉搜索樹(shù)(AVL樹(shù),紅黑樹(shù))等...

K模型：K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲(chǔ)Key即可，關(guān)鍵碼即為需要搜索到的值。( 在不在 的問(wèn)題)
比如：給一個(gè)單詞word，判斷該單詞是否拼寫(xiě)正確，具體方式如下：
以詞庫(kù)中所有單詞集合中的每個(gè)單詞作為key，構(gòu)建一棵二叉搜索樹(shù)
在二叉搜索樹(shù)中檢索該單詞是否存在，存在則拼寫(xiě)正確，不存在則拼寫(xiě)錯(cuò)誤。

還有如:門(mén)禁系統(tǒng),車(chē)庫(kù)系統(tǒng)等...

KV模型：每一個(gè)關(guān)鍵碼key，都有與之對(duì)應(yīng)的值Value，即的鍵值對(duì)。該種方
式在現(xiàn)實(shí)生活中非常常見(jiàn)： ( 通過(guò)一個(gè)值查找另一個(gè)值 )
比如英漢詞典就是英文與中文的對(duì)應(yīng)關(guān)系，通過(guò)英文可以快速找到與其對(duì)應(yīng)的中文，英
文單詞與其對(duì)應(yīng)的中文就構(gòu)成一種鍵值對(duì)；
再比如統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出
現(xiàn)次數(shù)就是就構(gòu)成一種鍵值對(duì)。

還有如:通訊錄

二叉搜索樹(shù)的性能分析

插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹(shù)中各個(gè)操作的性能。

對(duì)有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)，若每個(gè)元素查找的概率相等，則二叉搜索樹(shù)平均查找長(zhǎng)度是結(jié)點(diǎn)在二叉搜索樹(shù)的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。
但對(duì)于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹(shù)：

BST 二叉搜索樹(shù) BinarySearchTree C++實(shí)現(xiàn)(遞歸/非遞歸)

最優(yōu)情況下，二叉搜索樹(shù)為完全二叉樹(shù)(或者接近完全二叉樹(shù))，其平均比較次數(shù)為：$log_2 N$ ( $log_2 N$ )
最差情況下，二叉搜索樹(shù)退化為單支樹(shù)(或者類似單支)，其平均比較次數(shù)為：$\frac{N}{2}$ ( $\frac{N}{2}$ )

二叉搜索樹(shù)的操作

查找

從根開(kāi)始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。
最多查找高度次，走到到空，還沒(méi)找到，這個(gè)值不存在。

插入

樹(shù)為空，則直接新增節(jié)點(diǎn)，賦值給root指針(第一個(gè)節(jié)點(diǎn)就是root)
樹(shù)不空，按二叉搜索樹(shù)性質(zhì)查找插入位置，插入新節(jié)點(diǎn)

BST 二叉搜索樹(shù) BinarySearchTree C++實(shí)現(xiàn)(遞歸/非遞歸)

特別地

同樣一組數(shù)據(jù),插入順序不同,得到的二叉樹(shù)也不同
當(dāng)插入的值已存在時(shí),插入失敗(不考慮multi)

刪除

首先查找元素是否在二叉搜索樹(shù)中，如果不存在，則返回.

否則,根據(jù)樹(shù)的結(jié)構(gòu)定義,可以得到3種情況

要?jiǎng)h除的結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)
要?jiǎng)h除的結(jié)點(diǎn)只有左孩子或右孩子時(shí)
要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)

看起來(lái)有待刪除節(jié)點(diǎn)有4中情況，實(shí)際情況:

要?jiǎng)h除的結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)時(shí),直接刪除
要?jiǎng)h除的結(jié)點(diǎn)只有左孩子或右孩子時(shí),將左孩子或右孩子給父親
1. 要?jiǎng)h除的結(jié)點(diǎn)可能是父親的左孩子或者是右孩子,有2*2種情況(要?jiǎng)h除的結(jié)點(diǎn)是父親的左孩子或右孩子)
2. 左右孩子都是空時(shí),也滿足情況,因此可以合并無(wú)孩子結(jié)點(diǎn)情況
3. 在1的前提下,恰好是根節(jié)點(diǎn),也是一種情況(讓另外一個(gè)孩子做根即可)
要?jiǎng)h除的結(jié)點(diǎn)有左右孩子(子樹(shù))時(shí),需要找一個(gè)既要比左子樹(shù)大也要比右子樹(shù)小的節(jié)點(diǎn)來(lái)補(bǔ)上.

根據(jù) 遞歸定義 得知,只有左孩子的最右結(jié)點(diǎn)和右孩子的最左結(jié)點(diǎn)符合條件,二選一即可

當(dāng)選擇使用右孩子的最左結(jié)點(diǎn)時(shí),有以下三種情況(與是不是根無(wú)關(guān))
1. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹(shù)的最小結(jié)點(diǎn)恰好是要?jiǎng)h除結(jié)點(diǎn)的右孩子.
2. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹(shù)的最小結(jié)點(diǎn)沒(méi)有右孩子.
3. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹(shù)的最小結(jié)點(diǎn)有右孩子
  
  (上圖舉例分析)

代碼實(shí)現(xiàn)

BSTree.hpp

template
struct BSTreeNode {
    BSTreeNode* _left;
    BSTreeNode* _right;
    K _key;

    BSTreeNode(K key) 
    :_key(key),_left(nullptr),_right(nullptr)
    {}
};

template
class BSTree {
public:
    using Node = BSTreeNode;
    BSTree() = default;
    BSTree(const BSTree& bst) {
        _root = Copy(bst._root);
    }
    BSTree& operator=(BSTree bst) { //拷貝復(fù)用
        swap(_root,bst.root);
        return *this;
    }
    ~BSTree() {
        Destroy(_root);
    }

public:
    bool Insert(const K& key) {
        if (_root == nullptr) {
            _root = new Node(key);
            _root->_key = key;
            return true;
        }
        BSTreeNode* cur = _root;
        BSTreeNode* parent = _root;
        while (cur) {
            if (key < cur->_key) {
                parent = cur;
                cur = cur->_left;
            }
            else if (key > cur->_key) {
                parent = cur;
                cur = cur->_right;
            }
            else {
                return false;
            }
        }
        //走出循環(huán),說(shuō)明樹(shù)中不存在該節(jié)點(diǎn), 可以插入
        cur = new BSTreeNode(key);
        if (key < parent->_key) {

            parent->_left = cur;
        }
        else {
            parent->_right = cur;
        }
        return true;
    }

    bool Find(const K& key) {
        if (_root == nullptr) return false;

        Node* cur = _root;
        while (cur) {
            if (key < cur->_key) {
                cur = cur->_left;
            }
            else if (key > cur->_key) {
                cur = cur->_right;
            }
            else {
                return true;
            }
        }
        // 從循環(huán)出來(lái),說(shuō)明沒(méi)找著
        return false;
    }

    bool Erase(const K& key) {
        if (_root == nullptr) return false;

        Node* cur = _root;
        Node* parent = _root;

        while (cur) {
            if (key < cur->_key) {
                parent = cur;
                cur = cur->_left;
            }
            else if (key > cur->_key) {
                parent = cur;
                cur = cur->_right;
            }
            else {
                //沒(méi)有左孩子
                if (cur->_left == nullptr) {
                    if (cur == _root) {
                        _root = cur->_right;
                    }
                    else if (parent->_left == cur) {
                        parent->_left = cur->_right;
                    }
                    else {
                        parent->_right = cur->_right;
                    }
                    delete cur;
                    return true;
                }
                //沒(méi)有右孩子
                else if (cur->_right == nullptr) {
                    if (cur == _root) {
                        _root = cur->_left;
                    }
                    if (parent->_left == cur) {
                        parent->_left = cur->_left;
                    }
                    else {
                        parent->_right = cur->_left;
                    }
                    delete cur;
                    return true;
                }
                //有左右孩子
                else {
                    //找右孩子(子樹(shù))的最小結(jié)點(diǎn)/最左結(jié)點(diǎn)
                    Node* rightMin = cur->_right;  //明確不為空
                    Node* rightMinParent = cur;
                    while (rightMin->_left) {
                        rightMinParent = rightMin;
                        rightMin = rightMin->_left;
                    }
                    // 刪除右子樹(shù)最小結(jié)點(diǎn)有3種情況(與是不是根無(wú)關(guān))
                    //1. 要?jiǎng)h除的結(jié)點(diǎn)右子樹(shù)最小結(jié)點(diǎn)恰好是自己的右孩子.
                    //2. 要?jiǎng)h除的結(jié)點(diǎn)的右孩子的左子樹(shù)的最左結(jié)點(diǎn)沒(méi)有右孩子.
                    //3. 要?jiǎng)h除的結(jié)點(diǎn)的右孩子的左子樹(shù)的最左結(jié)點(diǎn)有右孩子.
                    //結(jié)論解析: 復(fù)用刪除單結(jié)點(diǎn)代碼,進(jìn)行刪除rightMin即可
                    K tmp = rightMin->_key;
                    Erase(rightMin->_key); //只能從根開(kāi)始遍歷,性能損失,但是二分查找很快,損失不大(理想情況,BST只學(xué)習(xí)用)
                    cur->_key = tmp;
                    return true;
                } //有左右孩子的情況 
            } //找到了_繼續(xù)處理的過(guò)程
        }//循環(huán)找的過(guò)程
        //循環(huán)結(jié)束,說(shuō)明沒(méi)找到
        return false;
    }//Erase [end]

    void InOrder() {
        _InOrder(_root);
        std::cout << std::endl;
    }

    bool InsertR(const K& key) {
        _InsertR(_root, key);
    }

    bool EraseR(const K& key) {
        return _EraseR(_root,key);
    }

private:

    //此處返回值不能使用指針引用,雖然一定情況下可以使用(不推薦),至少目前不能引用空值.
    Node* Copy(const Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        Node* newRoot = new Node(root->_key);
        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);
        return newRoot;
    }

    //用不用引用無(wú)所謂,好習(xí)慣做到底
    //(析構(gòu)子節(jié)點(diǎn)時(shí),父節(jié)點(diǎn)兩個(gè)成員會(huì)成為垂懸指針,但是接下來(lái)父親也要析構(gòu)了,指針變量也隨之回收)
    void Destroy(Node*&root) {
        if (root == nullptr) {
            return ;
        }
        Destroy(root->_left);
        Destroy(root->_right);

        std::cout<_key<<" ";
        delete root; //釋放加自動(dòng)置空
    }

    //練習(xí)遞歸+引用 -- 代碼更加簡(jiǎn)潔
    bool _EraseR(Node*& root, const K&key) {
        //走到空,說(shuō)明沒(méi)找到,返回false
        if (root == nullptr) {
            return false;
        }

        //大于走右邊,小于走左邊
        if (key > root->_key) {
            return _EraseR(root->_right,key);
        }
        else if(key_key) {
            return _EraseR(root->_left,key);
        }
        //找到了
        else {
            if (root->_left == nullptr) {
                Node* del = root;
                root = root->_right;
                delete del;
                return true;
            }
            else if (root->_right == nullptr) {
                Node* del = root;
                root = root->_left;
                delete del;
                return true;
            }
            //有左右孩子
            else {
                Node* leftMax = root->_left;
                //找左子樹(shù)最大結(jié)點(diǎn)
                while (leftMax->_right) {
                    leftMax = leftMax->_right;
                }
                std::swap(root->_key, leftMax->_key);
                return _EraseR(root->_left, key);    //直接從左孩子開(kāi)始遞歸刪除.
            }
        }

    }

    //練習(xí)遞歸+引用指針的玩法,僅練習(xí)
    bool _InsertR(Node*& root, const K& key) { //引用的妙用,跨棧幀直接訪問(wèn)實(shí)參
        if (root == nullptr) {
            root == new Node(key);
            return true;
        }
        if (key == root->_key) return false;
        return (key > root->_key) ? _InsertR(root->_right, key) : _InsertR(root->_left, key);
    }

    void _InOrder(Node* root) {
        if (root == nullptr)  return;
        _InOrder(root->_left);
        std::cout << root->_key << " ";
        _InOrder(root->_right);
    }

private:
    BSTreeNode* _root = nullptr;
};

test.cc

void test() {
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    BSTree bst;
    for (int i : a) {
        bst.Insert(i);
    }
    bst.InOrder();

    ////Find
    //std::cout << std::boolalpha << bst.Find(8) << std::endl; //true
    //std::cout << std::boolalpha << bst.Find(9) << std::endl; //false

    BSTree cp(bst);
    cp.InOrder();

    //測(cè)試兩孩子的三種情況即可
    bst.Erase(8);  //1. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹(shù)的最小結(jié)點(diǎn)恰好是要?jiǎng)h除結(jié)點(diǎn)的右孩子.
    bst.Erase(10); //2. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹(shù)的最小結(jié)點(diǎn)沒(méi)有右孩子
    bst.Insert(5); //構(gòu)造有右孩子的最小結(jié)點(diǎn)
    bst.Erase(3);  //3. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹(shù)的最小結(jié)點(diǎn)有右孩子
    bst.Erase(4);
    bst.Erase(7);
    bst.Erase(1);
    bst.Erase(14);
    bst.Erase(13);
    bst.Erase(6);
    bst.Erase(5);
    bst.InOrder();

    //禁止顯式調(diào)用析構(gòu)函數(shù) --> 雙重釋放
    //bst.~BSTree();
    //cp.~BSTree();
    
}

int main() {
    test();
}

小編推薦閱讀

好特網(wǎng)發(fā)布此文僅為傳遞信息，不代表好特網(wǎng)認(rèn)同期限觀點(diǎn)或證實(shí)其描述。

a 1.0: 類型：休閑益智　　運(yùn)營(yíng)狀態(tài)：正式運(yùn)營(yíng)　　語(yǔ)言：中文　　; 游戲攻略

游戲禮包

游戲視頻

游戲下載

游戲活動(dòng); 《alittletotheleft》官網(wǎng)正版是一款備受歡迎的休閑益智整理游戲。玩家的任務(wù)是對(duì)日常生活中的各種雜亂物