🚀 作者簡介：一名在后端領域學習，并渴望能夠學有所成的追夢人。
🐌 個人主頁：蝸牛牛啊
🔥 系列專欄：🛹數據結構、🛴C++
📕 學習格言：博觀而約取，厚積而薄發
🌹 歡迎進來的小伙伴，如果小伙伴們在學習的過程中，發現有需要糾正的地方，煩請指正，希望能夠與諸君一同成長！ 🌹

文章目錄

二叉搜索樹的概念
二叉搜索樹的操作及實現
- 二叉搜索樹的結構
- 二叉搜索樹的構造函數
- 二叉搜索樹的接口（非遞歸實現）
- - 二叉搜索樹的插入
  - 二叉搜索樹的中序遍歷
  - 二叉搜索樹的查找
  - 二叉搜索樹的刪除
- 二叉搜索樹的接口（遞歸實現）
- - 二叉搜索樹的插入
  - 二叉搜索樹的查找
  - 二叉搜索樹的刪除
- 二叉搜索樹的拷貝構造
- 二叉搜索樹的賦值
- 二叉搜索樹的析構函數
二叉搜索樹的應用
二叉搜索樹性能分析

二叉搜索樹的概念

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

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

二叉搜索樹還有一個特征：按照中序走的話是一個升序的狀態。所以二叉樹搜索樹可以叫做二叉排序樹或二叉查找樹。

二叉搜索樹的操作及實現

二叉搜索樹的結構

首先實現一個結點類，結點類當中包含三個成員變量：結點值、左指針、右指針，同時結點類當中要對成員變量進行初始化，需要實現一個構造函數，用于將結點的左右指針置空和初始化指定結點值。

結點類的代碼實現：

//二叉樹搜索樹結點類
template<class K>
struct BSTreeNode {BSTreeNode<K>* _left;//左指針BSTreeNode<K>* _right;//右指針K _key;//節點值//構造函數BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
};
template<class K>
class BSTree {//喜歡在類里進行類型重定義，因為受到類域的限制typedef BSTreeNode<K> Node;
private:Node* _root = nullptr; //可以給一個構造函數，也可以直接寫一個缺省值
};

二叉搜索樹的構造函數

//構造函數
BSTree():root(nullptr)
{}

我們也可以這樣寫：

//default:默認情況下不會生成，讓其強制生成構造函數
BSTree() = default;//指定強制生成默認構造

二叉搜索樹的接口（非遞歸實現）

二叉搜索樹的插入

通過插入函數在二叉搜索樹中插入一個值，如果成功返回true，失敗返回false。

當我們想進行插入數據時，要和樹的根結點及各個子樹的根結點進行比較，如果待插入結點值比當前結點小就插入到該結點的左子樹；如果待插入結點值比當前節點值大就插入到該結點的右子樹。

默認的搜索二叉樹是不允許冗余的，有相同的值會插入失敗。

根的值是怎么來的？插入的第一個值就是根。所以如果是同樣的值，插入的順序不同二叉搜索樹的形狀就不同。

在實現時我們要定義一個parent指針，方便新增節點和父結點鏈接。同時在鏈接的時候還要判斷一下是和父親的左邊鏈接還是右邊鏈接。

代碼實現：

bool Insert(const K& key)
{//確定插入的是否是第一個值,如果是第一個值插入的值就是根結點if (_root == nullptr){_root = new Node(key);//申請一個新節點return true;}//當根不是空時找對應的位置Node* cur = _root;//從根結點開始向后找Node* parent = nullptr;//父結點while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}//當相等時返回false，搜索二叉樹中不能有相等的else{return false;}}cur = new Node(key);//將其鏈接到父結點上if (parent->_key > key){parent->_left = cur;}else if (parent->_key < key){parent->_right = cur;}return true;
}

二叉搜索樹的中序遍歷

二叉搜索樹中序遍歷出來的順序是升序的，我們可以實現一個中序遍歷來驗證。

void InOrder(Node* root)
{if (root == nullptr){return;}InOrder(root->_left);cout << root->_key << endl;InOrder(root->_right);
}

但是我們發現這個函數調用時候不好處理，因為要傳根結點，但是并沒有根結點，如果參數沒有根，又沒辦法遞歸。

所以我們可以套上一層函數：調用無參的函數，當我們調用時調用無參的函數就可以實現中序遍歷了。

//套用一層函數
void InOrder()
{_InOrder(_root);
}
//實現中序遍歷，中序遍歷打印出來是升序的
void _InOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);
}

測試一下：

void Test_BSTree()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t1;for (auto e : a){//插入t1.Insert(e);}//中序遍歷t1.InOrder();
}
int main()
{Test_BSTree();return 0;
}

打印結果：

二叉搜索樹的查找

在二叉搜索樹中也可以通和根結點和左右子樹的根結點比較查找指定節點值，如果找到返回true，沒找到返回false。

代碼實現：

//查找接口
bool Find(const K&	key)
{Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;
}

二叉搜索樹的刪除

首先查找要刪除的元素是否存在，如果不存在，則返回；否則要刪除的結點可能分下面三種情況：

a.要刪除的結點只有左孩子結點(包含要刪除的結點無孩子結點)

b.要刪除的結點只有右孩子結點

c.要刪除的結點有左、右孩子結點

所以我們針對上面三種情況進行分析：

情況a：要刪除的結點只有左孩子結點(包含要刪除的結點無孩子結點)

此時刪除要刪除的結點之后，使被刪除節點的父結點指向被刪除節點的左孩子結點（直接刪除法）

情況b.要刪除的結點只有右孩子結點

此時刪除要刪除的結點之后，使被刪除節點的父結點指向被刪除節點的右孩子結點（直接刪除法）

情況c.要刪除的結點有左、右孩子結點

若待刪除結點有左、右孩子結點，可以使用替換法進行刪除。
可以找到待刪除結點左子樹中結點值最大的結點，或者是待刪除結點右子樹中結點值最小的結點來代替待刪除結點被刪除。代替待刪除結點被刪除的結點，在左右子樹當中至少有一個為空樹，那刪除該結點之后可以利用上面兩種情況來處理。

必須是待刪除結點左子樹中結點值最大的結點，或者是待刪除結點右子樹中結點值最小的結點代替待刪除結點被刪除，只有這樣才能保證刪除后的二叉樹仍保持二叉搜索樹的特性。

刪除的時候也要用parent記錄父結點，保證當被刪除結點還有孩子時能夠被接管。

代碼實現：

bool Erase(const K& key)
{Node* parent = nullptr;//父結點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 {//如果該結點只有左孩子if (cur->_right == nullptr){//當只有一邊時，需要更新_rootif (cur == _root){//左孩子為空，讓_root等于右孩子_root = cur->_left;}else{//判斷是哪邊的，讓其接管if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}//刪除該結點delete cur;}//該節點只有右孩子else if (cur->_left == nullptr){//當只有右邊時，需要更新_rootif (cur == _root){_root = cur->_right;}else {if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_left;}}//刪除結點delete cur;}//該節點有左右孩子else{//找右樹的最小結點替代//這里不能等于空//Node* pminRight = nullptr;Node* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}//找到右樹的最小結點之后再把key傳過去cur->_key = minRight->_key;if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;
}

同時我們在實現時應該注意當其為如下特殊情況時，更新_root：

二叉搜索樹的接口（遞歸實現）

一般在類里面寫遞歸都要套上一層。

二叉搜索樹的插入

要在搜索樹里面進行一個插入：比根結點大的值和右子樹根結點比較插入；比根結點小的值和左子樹根結點比較插入，需要注意插入要和父結點鏈接起來。我們可以傳入父結點，但是這里使用引用是最優的，root是_root->left或者_root->right的別名（上一層的別名），就能夠鏈接上。要注意C++的引用不能改變指向，循環里面不能用引用。

遞歸實現插入代碼：

bool _InSertR(Node*& root, const K& key)
{if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){_InSertR(root->_left, key);}if (root->_key < key){_InSertR(root->_right, key);}elsereturn false;
}
bool InSertR(const K& key)
{return _InSertR(_root, key);
}

二叉搜索樹的查找

查找，如果在二叉樹中返回true，否則返回false。

遞歸實現查找代碼：

//套用一層函數
bool _FindR(Node* root,const K& key) 
{if (root == nullptr){return false;}if (root->_key == key){return true;}if (root->_key > key){return _FindR(root->_left, key);}else{return _FindR(root->_right, key);}
}
bool FindR(const K& key)
{return _FindR(_root,key);
}

二叉搜索樹的刪除

刪除的思路和非遞歸方式一樣，當要刪除的結點有左右孩子的時候使用替換法，找左子樹的最大值或者右子樹的最小值（下面的遞歸實現采用的是找左子樹的最大值），但是注意遞歸這里不能使用root->_key = maxLeft->_key，如果這樣兩個值相同了，不能找到要刪除的結點。

遞歸刪除函數子函數中必須使用引用接收參數，保證能夠鏈接起來。

root是指針，直接讓指針指向其指定結點就可以了，不用找到父節點。要保存一下要刪除的結點Node* del = root，不然改變root指針后沒辦法刪除要刪除的結點。

bool _EarseR(Node*& root,const K& key)
{if (root == nullptr){return false;}if (root->_key > key){return _EarseR(root->_left, key);}else if (root->_key < key){return _EarseR(root->_right, key);}else {Node* del = root;//保存一下要刪除的結點if (root->_left == nullptr)//root是指針，直接讓指針指向其指定結點，這時就鏈接成功了root = root->_right;else if (root->_right == nullptr)root = root->_left;else{//去找左樹的最大值Node* maxLeft = root->_left;while (maxLeft->_right){maxLeft = maxLeft->_right;}//找到進行替代,直接交換swap(root->_key, maxLeft->_key);//交換值的時候不能使用root->_key = maxLeft->_key,如果這樣兩個值相同了，不能找到要刪除的結點。return _EarseR(root->_left,key);//轉換成在子樹去刪除}delete del;}
}
bool EarseR(const K& key)
{return _EarseR(_root, key);
}

return _EraseR(root->_left, key);這里不能使用maxLeft，因為要使用引用，maxLeft只是一個局部變量，會出問題的，引用在遞歸里面又變成別名。

二叉搜索樹的拷貝構造

當我們沒有實現拷貝構造時候，使用的都是默認拷貝構造函數，屬于淺拷貝。

當我們在沒有實現析構函數時使用以下代碼時并不會出問題：

void Test_BSTree() {int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t1;for (auto e : a){t1.Insert(e);}t1.InOrder();cout << endl;BSTree<int> t2(t1);t2.InOrder();
}

監視窗口如下：

但是當我們實現析構函數之后就會報錯：

所以拷貝構造我們要寫成深拷貝（推薦使用遞歸去實現）：

主要思想就是先去創建結點，在返回的時候才開始將各個節點鏈接起來。

從根結點開始，不能使用插入函數，因為插入順序不一樣，形狀不一樣：

BSTree(const BSTree<K>& t)
{_root = Copy(t._root);
}
Node* Copy(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;
}

二叉搜索樹的賦值

利用拷貝構造然后將其根結點交換即可。

BSTree& operator=(const BSTree<K> t)
{swap(_root, t._root);return *this;//支持連續賦值
}

二叉搜索樹的析構函數

二叉樹搜索樹的析構函數我們采用一個后序的遞歸刪除完成：

//析構函數
~BSTree()
{Destroy(_root);_root = nullptr;
}
void Destroy(Node* root)
{if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;
}

也可以在Destroy那里使用引用傳參，從而可以不在析構函數那里寫_root = nullptr;，直接在Destroy函數實現，因為root就是_root的別名。

~BSTree()
{Destroy(_root);
}
void Destroy(Node*& root)
{if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;
}

二叉搜索樹的應用

K模型

K模型，即只有key作為關鍵碼，結構中只需存儲key即可，關鍵碼即為需要搜索到的值。

我們在本篇中講到的構建、查找、插入就屬于K模型。

KV模型

KV模型，對于每一個關鍵碼key，都有與之對應的值value，即<key, value>的鍵值對。

通過一個值查找另一個值：如中英文互譯字典、電話號碼查詢快遞信息等。

我們可以通過改一下本篇中的二叉樹搜索樹來認識一下key-value模型，之前的二叉樹搜索樹是key模型。

將代碼修改，主要修改模板參數，增加一個參數：

namespace kv {template<class K,class V>struct BSTreeNode {BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _value;//構造函數BSTreeNode(const K& key,const V& value):_left(nullptr), _right(nullptr), _key(key),_value(value){}};template<class K, class V>class BSTree {//喜歡在類里進行類型重定義，因為受到類域的限制typedef BSTreeNode<K,V> Node;public://插入成功返回true，插入失敗返回falsebool Insert(const K& key,const V& value){if (_root == nullptr){_root = new Node(key,value);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(key,value);if (parent->_key > key){parent->_left = cur;}else {parent->_right = cur;}return true;}bool Erase(const K& key){Node* parent = nullptr;//父結點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 {//如果該結點只有左孩子if (cur->_right == nullptr){//當只有一邊時，需要更新_rootif (cur == _root){//左孩子為空，讓_root等于右孩子_root = cur->_left;}else{//判斷是哪邊的，讓其接管if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}//刪除該結點delete cur;}//該節點只有右孩子else if (cur->_left == nullptr){//當只有右邊時，需要更新_rootif (cur == _root){_root = cur->_right;}else {if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_left;}}//刪除結點delete cur;}//該節點有左右孩子else{//找右樹的最小結點替代//這里不能等于空//Node* pminRight = nullptr;Node* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}//找到右樹的最小結點之后再把key傳過去cur->_key = minRight->_key;if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return cur;}}return nullptr;}//套用一層函數void InOrder(){_InOrder(_root);}//實現中序遍歷void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};
}

實現之后我們通過實現一個單詞翻譯來測試一下：

//測試
void Test_BSTree()
{kv::BSTree<string, string> dict;dict.Insert("sort", "排序");dict.Insert("left", "左邊");dict.Insert("right", "右邊");dict.Insert("string", "字符串");dict.Insert("insert", "插入");dict.Insert("erase", "刪除");string str;while (cin >> str){//kv::BSTreeNode<std::string,std::string>* ret = dict.Find(str);auto ret = dict.Find(str);if (ret){cout << ":" << ret->_value << endl;}else{cout << "無此單詞" << endl;}}
}
int main()
{Test_BSTree();return 0;
}

測試結果：

這種程序怎么結束呢？while (cin >> str)按ctrl+c是發送終止信號，也可以使用ctrl+z+換行來結束。

我們還可以使用修改后的代碼用來測試統計水果出現的次數：

void Test_BSTree()
{string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜","蘋果", "香蕉", "蘋果", "香蕉" };kv::BSTree<string, int> countTree;for (auto str : arr){//kv::BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == nullptr){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();
}
int main()
{Test_BSTree();return 0;
}