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

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

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

下載游戲

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

二叉搜索樹

基本概念

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

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

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

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

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

二叉搜索樹/二叉查找樹也稱二叉排序樹,因?yàn)槎媾判驑涞闹行虮闅v結(jié)果是升序

常用結(jié)論

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

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

用途

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

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

還有如:門禁系統(tǒng),車庫系統(tǒng)等...

KV模型：每一個(gè)關(guān)鍵碼key，都有與之對(duì)應(yīng)的值Value，即的鍵值對(duì)。該種方
式在現(xiàn)實(shí)生活中非常常見： ( 通過一個(gè)值查找另一個(gè)值 )
比如英漢詞典就是英文與中文的對(duì)應(yīng)關(guān)系，通過英文可以快速找到與其對(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ì)。

還有如:通訊錄

二叉搜索樹的性能分析

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

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

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

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

二叉搜索樹的操作

查找

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

插入

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

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

特別地

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

刪除

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

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

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

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

要?jiǎng)h除的結(jié)點(diǎn)無孩子結(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í),也滿足情況,因此可以合并無孩子結(jié)點(diǎn)情況
3. 在1的前提下,恰好是根節(jié)點(diǎn),也是一種情況(讓另外一個(gè)孩子做根即可)
要?jiǎng)h除的結(jié)點(diǎn)有左右孩子(子樹)時(shí),需要找一個(gè)既要比左子樹大也要比右子樹小的節(jié)點(diǎn)來補(bǔ)上.

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

當(dāng)選擇使用右孩子的最左結(jié)點(diǎn)時(shí),有以下三種情況(與是不是根無關(guān))
1. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹的最小結(jié)點(diǎn)恰好是要?jiǎng)h除結(jié)點(diǎn)的右孩子.
2. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹的最小結(jié)點(diǎn)沒有右孩子.
3. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹的最小結(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),說明樹中不存在該節(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)出來,說明沒找著
        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 {
                //沒有左孩子
                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;
                }
                //沒有右孩子
                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 {
                    //找右孩子(子樹)的最小結(jié)點(diǎn)/最左結(jié)點(diǎn)
                    Node* rightMin = cur->_right;  //明確不為空
                    Node* rightMinParent = cur;
                    while (rightMin->_left) {
                        rightMinParent = rightMin;
                        rightMin = rightMin->_left;
                    }
                    // 刪除右子樹最小結(jié)點(diǎn)有3種情況(與是不是根無關(guān))
                    //1. 要?jiǎng)h除的結(jié)點(diǎn)右子樹最小結(jié)點(diǎn)恰好是自己的右孩子.
                    //2. 要?jiǎng)h除的結(jié)點(diǎn)的右孩子的左子樹的最左結(jié)點(diǎn)沒有右孩子.
                    //3. 要?jiǎng)h除的結(jié)點(diǎn)的右孩子的左子樹的最左結(jié)點(diǎn)有右孩子.
                    //結(jié)論解析: 復(fù)用刪除單結(jié)點(diǎn)代碼,進(jìn)行刪除rightMin即可
                    K tmp = rightMin->_key;
                    Erase(rightMin->_key); //只能從根開始遍歷,性能損失,但是二分查找很快,損失不大(理想情況,BST只學(xué)習(xí)用)
                    cur->_key = tmp;
                    return true;
                } //有左右孩子的情況 
            } //找到了_繼續(xù)處理的過程
        }//循環(huán)找的過程
        //循環(huán)結(jié)束,說明沒找到
        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;
    }

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

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

    //練習(xí)遞歸+引用 -- 代碼更加簡潔
    bool _EraseR(Node*& root, const K&key) {
        //走到空,說明沒找到,返回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;
                //找左子樹最大結(jié)點(diǎn)
                while (leftMax->_right) {
                    leftMax = leftMax->_right;
                }
                std::swap(root->_key, leftMax->_key);
                return _EraseR(root->_left, key);    //直接從左孩子開始遞歸刪除.
            }
        }

    }

    //練習(xí)遞歸+引用指針的玩法,僅練習(xí)
    bool _InsertR(Node*& root, const K& key) { //引用的妙用,跨棧幀直接訪問實(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();

    //測試兩孩子的三種情況即可
    bst.Erase(8);  //1. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹的最小結(jié)點(diǎn)恰好是要?jiǎng)h除結(jié)點(diǎn)的右孩子.
    bst.Erase(10); //2. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹的最小結(jié)點(diǎn)沒有右孩子
    bst.Insert(5); //構(gòu)造有右孩子的最小結(jié)點(diǎn)
    bst.Erase(3);  //3. 要?jiǎng)h除的結(jié)點(diǎn)的右子樹的最小結(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)營狀態(tài)：正式運(yùn)營　　語言：中文　　; 游戲攻略

游戲禮包

游戲視頻

游戲下載

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