> 作者簡介：?舊言~，目前大二，現(xiàn)在學(xué)習(xí)Java，c，c++，Python等
> 座右銘：松樹千年終是朽，槿花一日自為榮。> 目標(biāo)：熟練掌握二叉搜索樹，能自己模擬實(shí)現(xiàn)二叉搜索樹
> 毒雞湯：不斷的努力，不斷的去接近夢想，越挫越勇，吃盡酸甜苦辣，能夠抵御寒冬，也能夠擁抱春天，這樣的才叫生活。
> 望小伙伴們點(diǎn)贊??收藏?加關(guān)注喲?????
??前言??
前期呢我們學(xué)習(xí)了簡單二叉樹，這個(gè)簡單真的是一點(diǎn)都不簡單呀，如果大家對二叉樹的知識點(diǎn)忘記的小伙伴們可以看看這篇博客二叉樹的實(shí)現(xiàn)-CSDN博客，這篇博客不單單是二叉樹的進(jìn)階，這次的知識是為了后面的map和set以及紅黑樹...打下基礎(chǔ)，c++的學(xué)習(xí)也是上了一個(gè)層次，進(jìn)入今天的主題----二叉樹進(jìn)階之二叉搜索樹。
?主體
學(xué)習(xí)二叉樹進(jìn)階之二叉搜索樹咱們按照下面的圖解：
??二叉搜索樹基本概念
??基本概念
二叉搜索樹（Binary Search Tree），（又：二叉排序樹）它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值； 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹也分別為二叉搜索樹。二叉搜索樹作為一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它既有鏈表的快速插入與刪除操作的特點(diǎn)，又有數(shù)組快速查找的優(yōu)勢；所以應(yīng)用十分廣泛，例如在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)一般會采用這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行高效率的排序與檢索操作。?
??基本結(jié)構(gòu)
二叉搜索樹是能夠高效地進(jìn)行如下操作的數(shù)據(jù)結(jié)構(gòu)。
- 插入一個(gè)數(shù)值
- 查詢是否包含某個(gè)數(shù)值
- 刪除某個(gè)數(shù)值
??基本性質(zhì)
設(shè)x是二叉搜索樹中的一個(gè)結(jié)點(diǎn)。如果y是x左子樹中的一個(gè)結(jié)點(diǎn)，那么y.key≤x.key。如果y是x右子樹中的一個(gè)結(jié)點(diǎn)，那么y.key≥x.key。
在二叉搜索樹中：
- 若任意結(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均不大于它的根結(jié)點(diǎn)的值。
- 若任意結(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均不小于它的根結(jié)點(diǎn)的值。
- 任意結(jié)點(diǎn)的左、右子樹也分別為二叉搜索樹
1.這也就說明二叉搜索樹的中序遍歷（左 根 右）是升序的。
2.如果共有n個(gè)元素，那么平均每次操作需要O(logn)的時(shí)間。
???二叉搜索樹模擬實(shí)現(xiàn)
基本框架：
template <class K>
class BSTree
{
typedef BSTreeNode<K> Node;
private:
Node* _root = nullptr;
public:
//默認(rèn)成員函數(shù)
BSTree ();
BSTree (const K& key);
BSTree& operator=(BSTree Tree);
~BSTree();
bool Insert(const K& key);
void Inorder();
bool find(const K& key);
bool Erase(const K& key);
//遞歸實(shí)現(xiàn)
bool FindR(const K& key);
bool InsertR(const K& key);
bool EraseR(const K& key);
}??二叉搜索樹節(jié)點(diǎn)創(chuàng)建
創(chuàng)建樹之前要先定義好節(jié)點(diǎn)，跟之前普通鏈?zhǔn)蕉鏄錄]有什么區(qū)別。
代碼實(shí)現(xiàn)：
// 對每個(gè)結(jié)點(diǎn)初始化
template<class K>
struct BSTreeNode
{
typedef BSTreeNode<K> Node; // 重命名
Node* _left; // 左子樹
Node* _right; // 右子樹
K _key; // 二叉搜索樹節(jié)點(diǎn)元素的值
BSTreeNode(const K& key) // 初始化列表，成員變量初始化
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};拓展分析：
- 我們會不斷的通過 key 創(chuàng)建樹節(jié)點(diǎn)， new 出的對象會調(diào)用帶參的構(gòu)造函數(shù)。所以，我們定義好節(jié)點(diǎn)中的成員變量后還要書寫好構(gòu)造函數(shù)。
- 因?yàn)闃涔?jié)點(diǎn)會頻繁訪問成員變量，所以我們要將其置為公有成員(public)，如果覺得麻煩，可以直接使用 struct 定義節(jié)點(diǎn)。
??二叉搜索樹構(gòu)造函數(shù)
二叉搜索樹這個(gè)類只要存入二叉樹的根節(jié)點(diǎn)就可以了
代碼實(shí)現(xiàn)：
// 強(qiáng)制生成默認(rèn)構(gòu)造函數(shù)
BSTree() = default;拓展分析：
這里加入default關(guān)鍵字是讓編譯器強(qiáng)制生成默認(rèn)構(gòu)造函數(shù)，因?yàn)榈葧覀円獙懣截悩?gòu)造，根據(jù)C++的類和對象的知識，我們只要顯式的寫一個(gè)構(gòu)造函數(shù)，編譯器就不會生成默認(rèn)構(gòu)造函數(shù)
??二叉搜索樹查找函數(shù)
二叉搜索樹，左樹比根小，右樹比根大我們可以根據(jù)這個(gè)特性去尋找，走到空的位置還沒有找到，證明該樹中沒有該元素。
1）非遞歸
代碼實(shí)現(xiàn)：
// 查找函數(shù)
bool Find(const K& key)
{
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;
}拓展分析：
這里采用左樹比根小，右樹比根大的特性來實(shí)現(xiàn)代碼。
2）遞歸
步驟拆分：
- 如果 root 指向?yàn)?nullptr ，說明未找到 key 值
- 如果 key 大于 root->key，說明 key 在 root 的右邊，使用root->right繼續(xù)遞歸。
- 如果 key 小于 root->key，說明 key 在 root 的左邊，使用root->left繼續(xù)遞歸。
- 最后就是 key==root->key 的情況，返回 true 。
代碼實(shí)現(xiàn)：
// 遞歸版本
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;
}
}拓展分析：
遞歸這里有一點(diǎn)小問題，因?yàn)樵贑++類中，實(shí)現(xiàn)遞歸是有一些問題的，因?yàn)槲覀儼迅苯臃庠陬愔辛?，函?shù)根本就不需要參數(shù)就可以訪問根節(jié)點(diǎn)，但是我們的遞歸函數(shù)需要參數(shù)來控制向哪棵樹遞歸
??二叉搜索樹插入函數(shù)
對于鏈?zhǔn)浇Y(jié)構(gòu)來說，我們直接向這個(gè)空節(jié)點(diǎn)賦值，表面上是鏈接了，實(shí)際上根本沒有鏈接上，因?yàn)槲覀儽闅v所使用的節(jié)點(diǎn)是一個(gè)臨時(shí)變量，出了作用域就會自動(dòng)銷毀，所以根本沒有鏈接上，所以我們還要記住最后走到的空節(jié)點(diǎn)的父節(jié)點(diǎn)，用父節(jié)點(diǎn)來鏈接新插入的節(jié)點(diǎn)。
1）非遞歸
步驟拆分：
- 傳入空樹直接 new 一個(gè)節(jié)點(diǎn)，將其置為 root 。
- 找到 key 值該在的位置，如果 key 大于 當(dāng)前節(jié)點(diǎn)的 _key，則往右走，小于則往左走。
- 如果 key 等于當(dāng)前節(jié)點(diǎn)的 _key，直接返回 false。
- 直到 cur 走到空，此時(shí) cur 指向的便是 key 應(yīng)當(dāng)存放的地方。
- 創(chuàng)建一個(gè)節(jié)點(diǎn)并鏈接到樹中(鏈接到 parent 節(jié)點(diǎn)的左或右)
代碼實(shí)現(xiàn)：
// 插入結(jié)點(diǎn)
bool Insert(const K& key)
{
if (_root == nullptr) // 如果沒有結(jié)點(diǎn)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) // 開始插入
{
if (cur->_key < key) // 比它小走左子樹
{
parent = cur;
cut = cur->_left;
}
else if (cur->_key > key) // 比它大走右子樹
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key); // 開始鏈接
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}2）遞歸
bool InsertR(const K& key)
{
return _InsertR(_root, key)
}
// 遞歸版本
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;
}
}拓展分析：
??二叉搜索樹節(jié)點(diǎn)刪除
問題剖析：
Erase 刪除分為以下三種情況：
- 刪除節(jié)點(diǎn)為葉子節(jié)點(diǎn)
- 刪除節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)
- 刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
第一點(diǎn)和第二點(diǎn)可以歸納為一點(diǎn)，而第二點(diǎn)是這個(gè)三點(diǎn)最為復(fù)雜的。
問題分析：
①：刪除節(jié)點(diǎn)為葉子節(jié)點(diǎn)? ? &&? ? 刪除節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)
分析：其本質(zhì)都屬于左或右節(jié)點(diǎn)為空，當(dāng)該節(jié)點(diǎn)只有一個(gè)孩子或無孩子時(shí)，直接讓 parent 指向該節(jié)點(diǎn)子節(jié)點(diǎn)，然后將此節(jié)點(diǎn)移除出樹。?
1.刪除的是根節(jié)點(diǎn)
如果parent指向的是nullptr，則直接讓_root后移動(dòng)即可。
2. 鏈接時(shí)，應(yīng)該鏈接到父親的左還是右。
如果parent的左邊是待刪節(jié)點(diǎn)，即parent->left==cur，則將cur的右邊鏈接到parent的左邊
如果parent的右邊是待刪節(jié)點(diǎn)，即parent->right==cur，將cur的右邊鏈接到parent的右邊
①：刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
分析：采用的是替換法刪除，我們要?jiǎng)h除3，我們知道cur的右子樹中最左邊的節(jié)點(diǎn)的值是與cur節(jié)點(diǎn)的值是最接近的，所以我們交換3和4，這樣就轉(zhuǎn)換為刪除葉子節(jié)點(diǎn)了，這樣就會把問題的難度降低。
1.此時(shí) 6 節(jié)點(diǎn)的_left 仍然指向原來的 4 節(jié)點(diǎn)，出現(xiàn)野指針的問題。并且如果 4 節(jié)點(diǎn)還有右子樹呢？如圖：
解決方案：我們的方法是仍要記錄下min的父節(jié)點(diǎn)，讓父節(jié)點(diǎn)指向 min->right，此時(shí)無論min->right有子樹還是min->right==nullptr，都可以很好的解決該問題，
2. 無法刪除根節(jié)點(diǎn)(8)
解決方案：刪除8節(jié)點(diǎn)，此時(shí) min 指向了cur->right，min ->left 為空，沒有進(jìn)入循環(huán)，導(dǎo)致minparent 為空指針，指向 minparent->_left = min->right;出現(xiàn)非法訪問。
1）非遞歸
代碼實(shí)現(xiàn)：
// 刪除節(jié)點(diǎn)
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
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) // 第一種情況
{
if (cur == _root)
_root = cur->_right;
else
{
if (cur == parent->_right)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr) // 第二種情況
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_right)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
else // 第三種情況
{
// 替換法
Node* rightMinParent = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}2）遞歸
代碼實(shí)現(xiàn)：
// 遞歸版本
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
{
Node* del = root;
if (root->_right == nullptr)
{
root = root->_left;
}
else if (root->_left == nullptr)
{
root = root->_right;
}
else
{
Node* rightMin = root->_right;
while (rightMin->_left)
{
rightMin = rightMin->_left;
}
swap(root->_key, rightMin->_key);
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}??二叉搜索樹拷貝構(gòu)造
拷貝構(gòu)造，我們可以參考前面的二叉樹重建，直接遞歸解決，所以我們讓二叉搜索樹的拷貝構(gòu)造調(diào)用我們的_Copy函數(shù)。
// 拷貝構(gòu)造
BSTree(const BSTree<K>& t)
{
_root = Copy(t.root); // 調(diào)用拷貝構(gòu)造
}
// 拷貝構(gòu)造
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newRoot = new Node(root->_key); // 創(chuàng)建一個(gè)節(jié)點(diǎn)
newRoot->_left = Copy(root->left); // 拷貝左子樹
newRoot->_right = Copy(root->_right); // 拷貝右子樹
return newRoot; // 返回根
}??二叉搜索樹operator=
operator=我們采用現(xiàn)代寫法，傳參時(shí)會調(diào)用拷貝構(gòu)造，我們直接將形參與我們當(dāng)前對象交換。
// 賦值運(yùn)算重載
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}??二叉搜索樹析構(gòu)函數(shù)
析構(gòu)函數(shù)也要遞歸實(shí)現(xiàn)，采用后序遍歷，一個(gè)一個(gè)節(jié)點(diǎn)的刪除
// 析構(gòu)函數(shù)
~BSTree()
{
Destroy(_root); // 調(diào)用析構(gòu)函數(shù)
}
// 析構(gòu)函數(shù)
void Destroy(Node* root) // 采用遞歸的形式
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->right);
delete root;
}???二叉搜索樹應(yīng)用場景
1.K模型：K模型即只有 key 作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲 key 即可，關(guān)鍵碼即為需要搜索到的值。
比如： 給一個(gè)單詞 word，判斷該單詞是否拼寫正確，具體方法如下：
- 以詞庫中所有單詞集合中的每個(gè)單詞作為key，構(gòu)造一棵二叉搜索樹
- 在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯(cuò)誤。
2.KV模型：每一個(gè)關(guān)鍵碼 key ，都有與之對應(yīng)的值 value，即<key，value>的鍵值對。該種方法式在現(xiàn)實(shí)生活中非常常見：
- 比如英漢詞典就是英文與中文的對應(yīng)關(guān)系，通過英文可以快速找到與其對應(yīng)的中文，英文單詞與其對應(yīng)的中文<word,chinese>就構(gòu)成一種鍵值對；
- 再比如統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)的次數(shù)就是<world,count>，就夠成一種鍵值對。
代碼實(shí)現(xiàn)：
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key, value);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
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)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_right)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_right)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
else
{
// 替換法
Node* rightMinParent = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};??全部代碼
namespace lyk
{
// 對每個(gè)結(jié)點(diǎn)初始化
template<class K>
struct BSTreeNode
{
typedef BSTreeNode<K> Node; // 重命名
Node* _left; // 左子樹
Node* _right; // 右子樹
K _key; // 二叉搜索樹節(jié)點(diǎn)元素的值
BSTreeNode(const K& key) // 初始化列表，成員變量初始化
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
/
// 二叉搜索樹功能基本實(shí)現(xiàn)
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node; // 重命名
public:
// 強(qiáng)制生成默認(rèn)構(gòu)造函數(shù)
BSTree() = default;
// 拷貝構(gòu)造
BSTree(const BSTree<K>& t)
{
_root = Copy(t.root); // 調(diào)用拷貝構(gòu)造
}
// 賦值運(yùn)算重載
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
// 析構(gòu)函數(shù)
~BSTree()
{
Destroy(_root); // 調(diào)用析構(gòu)函數(shù)
}
// 插入結(jié)點(diǎn)
bool Insert(const K& key)
{
if (_root == nullptr) // 如果沒有結(jié)點(diǎn)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) // 開始插入
{
if (cur->_key < key) // 比它小走左子樹
{
parent = cur;
cut = cur->_left;
}
else if (cur->_key > key) // 比它大走右子樹
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key); // 開始鏈接
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
// 查找函數(shù)
bool Find(const K& key)
{
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;
}
// 刪除節(jié)點(diǎn)
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
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) // 第一種情況
{
if (cur == _root)
_root = cur->_right;
else
{
if (cur == parent->_right)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr) // 第二種情況
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_right)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
else // 第三種情況
{
// 替換法
Node* rightMinParent = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
// 這樣方便調(diào)用
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
// 析構(gòu)函數(shù)
void Destroy(Node* root) // 采用遞歸的形式
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->right);
delete root;
}
// 拷貝構(gòu)造
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newRoot = new Node(root->_key); // 創(chuàng)建一個(gè)節(jié)點(diǎn)
newRoot->_left = Copy(root->left); // 拷貝左子樹
newRoot->_right = Copy(root->_right); // 拷貝右子樹
return newRoot; // 返回根
}
// 遞歸版本
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
{
Node* del = root;
if (root->_right == nullptr)
{
root = root->_left;
}
else if (root->_left == nullptr)
{
root = root->_right;
}
else
{
Node* rightMin = root->_right;
while (rightMin->_left)
{
rightMin = rightMin->_left;
}
swap(root->_key, rightMin->_key);
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}
// 遞歸版本
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;
}
}
// 遞歸版本
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;
}
}
// 中序遍歷
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr
};
}
namespace key_value
{
template<class K, class V>
struct BSTreeNode
{
typedef BSTreeNode<K, V> Node;
Node* _left;
Node* _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:
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key, value);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
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)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_right)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_right)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
else
{
// 替換法
Node* rightMinParent = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
}??結(jié)束語
? ? ? ?今天內(nèi)容就到這里啦，時(shí)間過得很快，大家沉下心來好好學(xué)習(xí)，會有一定的收獲的，大家多多堅(jiān)持，嘻嘻，成功路上注定孤獨(dú)，因?yàn)閳?jiān)持的人不多。那請大家舉起自己的小手給博主一鍵三連，有你們的支持是我最大的動(dòng)力??????，回見。文章來源：http://www.zghlxwxcb.cn/news/detail-840482.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-840482.html
到了這里，關(guān)于【C++】二叉樹進(jìn)階之二叉搜索樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
