=========================================================================
個人主頁點擊直達：小白不是程序媛
C++系列專欄：C++干貨鋪
代碼倉庫：Gitee
=========================================================================
目錄
前言：
二叉搜索樹
二叉搜索樹概念
二叉搜索樹操作
二叉搜索樹的查找
?二叉搜索樹的插入
二叉搜索樹元素的刪除
?二叉搜索樹的實現(xiàn)
BSTree結(jié)點
BSTree框架
拷貝構(gòu)造函數(shù)和無參構(gòu)造函數(shù)
析構(gòu)函數(shù)
賦值重載（operator=）
插入Insert ()
查找Find()
刪除()
?中序遍歷
二叉搜索樹的應用
二叉搜索樹的性能分析
前言：
在C語言的數(shù)據(jù)結(jié)構(gòu)期間我們介紹過二叉樹的一些概念；并且實現(xiàn)了其鏈式結(jié)構(gòu)和實現(xiàn)了前、中、后序的遍歷；有些OJ題使用C語言方式實現(xiàn)比較麻煩，比如有些地方要返回動態(tài)開辟的二維數(shù)組，非常麻煩。因此本節(jié)借二叉樹搜索樹，對二叉樹部分進行收尾總結(jié)。并且后面的map和set特性需要先鋪墊二叉搜索樹，而二叉搜索樹也是一種樹形結(jié)構(gòu)；二叉搜索樹的特性了解，有助于更好的理解map和set的特性。
二叉搜索樹
二叉搜索樹概念
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹:
- 若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值
- 若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值
- 它的左右子樹也分別為二叉搜索樹
二叉搜索樹操作
二叉搜索樹的中序遍歷根據(jù)其存儲結(jié)構(gòu)是排好序的。
- 如果左邊存儲比根小的數(shù)字右邊存儲比根大的數(shù)字，中序遍歷的結(jié)果是升序的；
- 如果左邊存儲比根大的數(shù)組右邊存儲比根小的數(shù)字，中序遍歷的結(jié)果是降序的；
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
注意：二叉搜索樹是沒有“修改”的，因為如果隨便修改一個數(shù)據(jù)，整棵樹都要重新去實現(xiàn)。?
二叉搜索樹的查找
- 從根開始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。
- 最多查找高度次，走到空，還沒找到，這個值不存在。?
注意：
二叉搜索樹有一個特別重要的特點：樹中沒有兩個相同的元素。
?二叉搜索樹的插入
插入的具體過程如下：
- 樹為空，則直接新增節(jié)點，賦值給root指針
- 樹不空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點?
二叉搜索樹元素的刪除
首先查找元素是否在二叉搜索樹中，如果不存在，則返回, 否則要刪除的結(jié)點可能分下面四種情
況：
- 要刪除的結(jié)點無孩子結(jié)點
- 要刪除的結(jié)點只有左孩子結(jié)點
- 要刪除的結(jié)點只有右孩子結(jié)點
- 要刪除的結(jié)點有左、右孩子結(jié)點
看起來有待刪除節(jié)點有4中情況，實際情況1可以與情況2或者3合并起來，因此真正的刪除過程
如下：?
- 情況b：刪除該結(jié)點且使被刪除節(jié)點的雙親結(jié)點指向被刪除節(jié)點的左孩子結(jié)點--直接刪除
- 情況c：刪除該結(jié)點且使被刪除節(jié)點的雙親結(jié)點指向被刪除結(jié)點的右孩子結(jié)點--直接刪除
- 情況d：在它的右子樹中尋找中序下的第一個結(jié)點(關鍵碼最小)，用它的值填補到被刪除節(jié)點中，再來處理該結(jié)點的刪除問題--替換法刪除
二叉搜索樹的實現(xiàn)
BSTree結(jié)點
節(jié)點中包含兩個該節(jié)點類型的指針，分別代表著指向左右孩子和節(jié)點中存儲的值。
template <class K>
struct BSTNode
{
BSTNode<K>* _left;
BSTNode<K>* _right;
K _key;
//結(jié)點的構(gòu)造函數(shù)
BSTNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{
}
};BSTree框架
成員變量為結(jié)點類型的指針。
template<class K>
class BST
{
typedef BSTNode<K> Node;
private:
Node* _root=nullptr;
};拷貝構(gòu)造函數(shù)和無參構(gòu)造函數(shù)
因為我們自己寫了拷貝構(gòu)造函數(shù)，所以編譯器不會默認生成無參構(gòu)造函數(shù)。在C++11中可以讓默認構(gòu)造函數(shù)等于default，讓編譯器再次自動生成默認構(gòu)造函數(shù)。
拷貝一個二叉搜索樹開始要使用遞歸進行調(diào)用的。?
BST() = default;
BST(const BST<K>& st)
{
_root=Copy(st._root);
}析構(gòu)函數(shù)
因為我們在類外面顯示調(diào)用根節(jié)點很麻煩，直接在類內(nèi)部以根節(jié)點為參數(shù)直接遞歸實現(xiàn)。
public:
~BST()
{
Destory(_root);
}
private:
?
void Destory(Node*& root)
{
if (root == nullptr)
{
return;
}
Destory(root->_left);
Destory(root->_right);
delete root;
root = nullptr;
}
?賦值重載（operator=）
swap函數(shù)是庫std中的函數(shù)，深拷貝；
BST<K>& operator=(BST<K> t)
{
swap(_root, t._root);
return *this;
}插入Insert ()
非遞歸版本
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else if (parent->_key > key)
{
parent->_left = cur;
}
}
- 首先還是要判斷傳入的根結(jié)點是否為空，如果為空直接開辟一個新的結(jié)點即可；
- 如果不為空，先創(chuàng)建一個父親的結(jié)點便于插入的時候做修改；然后在創(chuàng)建一個結(jié)點從根節(jié)點開始根據(jù)二叉搜索樹的特點開始找適合插入的位置，當找到時開辟一個新的結(jié)點，然后讓合適位置的根節(jié)點指向開辟好的新節(jié)點即可；
遞歸版本
pbulic:
bool InsertR(const K & key)
{
return _InsertR(_root, key);
}
private:
?
bool _InsertR(Node*& root,const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
?這里的遞歸也是根據(jù)二叉搜索樹左右兩邊孩子的特點巧妙使用引用來實現(xiàn)的，每次遞歸的參數(shù)為上一個根節(jié)點指向左孩子或者右孩子的引用，去掉了記錄父親節(jié)點。?
查找Find()
非遞歸版本
也是根據(jù)二叉搜索樹左右孩子的特點實現(xiàn)的。如果查找的值比根結(jié)點的值大則和根節(jié)點的右孩子比較，反之；
注意：搜索二叉樹中是沒有兩個相同的值的。
bool find(const K& key)
{
if (_root == nullptr)
{
return false;
}
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}遞歸版本
public :
bool FindR(const K & key)
{
return _FindR(_root, key);
}
private :
?
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _FindR(_root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}
?刪除()
非遞歸版本
刪除這里的情況還比較復雜，先要根據(jù)上面查找函數(shù)的思路找到結(jié)點；
- 如果左孩子為空，且該結(jié)點為父節(jié)點的左孩子，則讓父節(jié)點指向的左孩子為該節(jié)點的右支；刪掉此節(jié)點。如果該結(jié)點為父節(jié)點的右孩子，則讓父節(jié)點指向的右孩子為該節(jié)點右支；刪掉此節(jié)點。
- 如果右孩子為空，且該節(jié)點為父節(jié)點的左孩子，則讓父節(jié)點指向的左孩子為該節(jié)點的右支；刪掉此節(jié)點。如果該節(jié)點為父節(jié)點的右孩子，則讓父節(jié)點指向的左孩子為該節(jié)點的左支；刪掉此節(jié)點。
- 如果左右孩子都不為空，則要取左支最大的（最右結(jié)點）或者取右支最小的（最左結(jié)點），這里實現(xiàn)的是取右支最小的；先進入該結(jié)點的右邊，然后使用循環(huán)找到最左結(jié)點；對該節(jié)點和其父節(jié)點的值進行交換，然后按照上面左孩子為空調(diào)整其父節(jié)點指向的孩子結(jié)點。然后刪除結(jié)點。
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//左為空
if (cur->_left == nullptr)
{
//刪除根節(jié)點的值
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
}
delete cur;
}
//右為空
else if (cur->_right == nullptr)
{
//刪除根節(jié)點的值
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
//右樹的最小值
Node* subleft = cur->_right;
Node* parent = cur;
while (subleft->_left)
{
parent = subleft;
subleft = subleft->_left;
}
swap(cur->_key, subleft->_key);
if (subleft == parent->_left)
{
parent->_left = subleft->_right;
}
else
{
parent->_right = subleft->_right;
}
delete subleft;
}
return true;
}
}
return false;
}遞歸版本
public:
bool EraseR(const K&key)
{
return _EraseR(_root, key);
}
private:
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else if (root->_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* subleft = root->_right;
while (subleft->_left)
{
subleft = subleft->_left;
}
swap(root->_key, subleft->_key);
return _EraseR(root->_right, key);
}
}
}?中序遍歷
public:
void Inorder()
{
_Inorder(_root);
cout << endl;
}
private:
?
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}
?二叉搜索樹的應用
1. K模型：K模型即只有key作為關鍵碼，結(jié)構(gòu)中只需要存儲Key即可，關鍵碼即為需要搜索到的值。
比如給一個單詞word，判斷該單詞是否拼寫正確，具體方式如下：
- 以詞庫中所有單詞集合中的每個單詞作為key，構(gòu)建一棵二叉搜索樹
- 在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤。
2. KV模型：每一個關鍵碼key，都有與之對應的值Value，即<Key, Value>的鍵值對。該種方式在現(xiàn)實生活中非常常見：
- 比如英漢詞典就是英文與中文的對應關系，通過英文可以快速找到與其對應的中文，英文單詞與其對應的中文<word, chinese>就構(gòu)成一種鍵值對；
- 再比如統(tǒng)計單詞次數(shù)，統(tǒng)計成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)次數(shù)就是<word, count>就構(gòu)成一種鍵值對。?
二叉搜索樹的性能分析
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能。
對有n個結(jié)點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結(jié)點在二
叉搜索樹的深度的函數(shù)，即結(jié)點越深，則比較次數(shù)越多。但對于同一個關鍵碼集合，如果各關鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹：?
文章來源：http://www.zghlxwxcb.cn/news/detail-765031.html
- 最優(yōu)情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數(shù)為：O(logN)
- 最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其平均比較次數(shù)為：O(N)；如果退化成了單支樹，那么二叉搜索樹的性能就失去了。此時就需要用到即將登場的 AVL 樹和紅黑樹了。
今天對二叉搜索樹的介紹、使用、模擬實現(xiàn)的分享到這就結(jié)束了，希望大家讀完后有很大的收獲，也可以在評論區(qū)點評文章中的內(nèi)容和分享自己的看法。您三連的支持就是我前進的動力，感謝大家的支持！！?!文章來源地址http://www.zghlxwxcb.cn/news/detail-765031.html
到了這里，關于【C++干貨鋪】會搜索的二叉樹（BSTree)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
