C++二叉搜索樹(shù)模擬實(shí)現(xiàn)示例
更新時(shí)間：2023年11月02日 14:29:56 作者：kkbca
本文主要介紹了C++二叉搜索樹(shù)模擬實(shí)現(xiàn)示例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
一、二叉搜索樹(shù)的概念
搜索二叉樹(shù)結(jié)構(gòu)上跟普通的二叉樹(shù)一樣，它要么是一棵空樹(shù)，要么是具有以下性質(zhì)的二叉樹(shù):
- 若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
- 若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
- 它的左右子樹(shù)也分別為二叉搜索樹(shù)
如下圖所示，這就是一顆二叉搜索樹(shù)。我們可以發(fā)現(xiàn)這顆樹(shù)的中序遍歷就是有序的
二、二叉搜索樹(shù)的結(jié)構(gòu)
首先我們肯定需要樹(shù)節(jié)點(diǎn)，來(lái)幫助我們保持樹(shù)的結(jié)構(gòu)和存放數(shù)據(jù)。
如下代碼我們就使用模板定義了樹(shù)的結(jié)構(gòu)，并添加了構(gòu)造函數(shù)，方便我們創(chuàng)建結(jié)點(diǎn)
template<class T>
struct BSTreeNode
{
BSTreeNode<T>* _left;
BSTreeNode<T>* _right;
T _key;
BSTreeNode(const T& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};二叉樹(shù)的成員變量只有根結(jié)點(diǎn)
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
private:
Node* _root
}三、二叉搜索樹(shù)的操作（非遞歸）
1.插入
我們定義了一個(gè)數(shù)組，現(xiàn)在要將這個(gè)數(shù)組的內(nèi)容放到搜索二叉樹(shù)里。
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};就會(huì)成為如下這棵樹(shù)
依次插入0和16
插入部分代碼還算簡(jiǎn)單，首先就判斷當(dāng)前樹(shù)是否為空，通過(guò)成員變量根結(jié)點(diǎn)來(lái)判斷，根節(jié)點(diǎn)為空就直接new一個(gè)結(jié)點(diǎn)賦值給根結(jié)點(diǎn)返回true。
我們可以通過(guò)key值來(lái)比較往左走還是往右走，如果插入的key值比當(dāng)前結(jié)點(diǎn)的值小，就往左走，如果比當(dāng)前結(jié)點(diǎn)的值大，就往右走，如果相等，就證明你找到了結(jié)點(diǎn)，我們返回false，代表插入失敗（二叉搜索樹(shù)為了保持他的結(jié)構(gòu)，是不能有相等的key的）。
- 目前我們已經(jīng)找到了這個(gè)結(jié)點(diǎn)應(yīng)該存放的位置，那么我們?nèi)绾螌⑺麄冩溄悠饋?lái)呢？
這就需要一個(gè)父結(jié)點(diǎn)來(lái)幫助我們處理，讓父結(jié)點(diǎn)一直跟隨著當(dāng)前結(jié)點(diǎn)走。直到找到應(yīng)該存在的地方之后，再判斷這個(gè)地方是父親的左還是右（同樣是用key來(lái)比較，key比父結(jié)點(diǎn)的值小，放在父結(jié)點(diǎn)的左邊，大就放在父結(jié)點(diǎn)的右邊，通過(guò)new一個(gè)結(jié)點(diǎn)來(lái)完成）最后返回true。
代碼如下
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
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
{
return false;
}
}
if (parent->_key > key)
{
parent->_left = new Node(key);
}
else
{
parent->_right = new Node(key);
}
return true;
}
2.查找
查找是插入的簡(jiǎn)潔版，依然用key來(lái)比較，找到了返回true，沒(méi)找到就返回false
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;
}3.刪除
刪除部分是二叉搜索樹(shù)較難的地方，因?yàn)槲覀兊米屵@棵樹(shù)刪除之后依然保持原來(lái)的特性，也就是
- 若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
- 若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
- 它的左右子樹(shù)也分別為二叉搜索樹(shù)
因此我們得考慮很多種情況
首先查找元素是否在二叉搜索樹(shù)中，如果不存在，則返回, 否則要?jiǎng)h除的結(jié)點(diǎn)可能分下面四種情 況：
- a. 要?jiǎng)h除的結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)
- b. 要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)
- c. 要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)
- d. 要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)
看起來(lái)有待刪除節(jié)點(diǎn)有4中情況，實(shí)際情況a可以與情況b或者c合并起來(lái)，因此真正的刪除過(guò)程 如下：
- 情況b：刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除節(jié)點(diǎn)的左孩子結(jié)點(diǎn)--直接刪除
- 情況c：刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)--直接刪除
- 情況d：在它的右子樹(shù)中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小)，用它的值填補(bǔ)到被刪除節(jié)點(diǎn) 中，再來(lái)處理該結(jié)點(diǎn)的刪除問(wèn)題--替換法刪除
對(duì)于情況b和c，我們首先要判斷找到的結(jié)點(diǎn)是否為根節(jié)點(diǎn)，如果是，根節(jié)點(diǎn)就會(huì)往相應(yīng)方向走
左為空
右為空也是同理，我們就不多贅述了。
對(duì)于情況d我們使用替換法刪除，比如刪除4，我們可以拿4的右子樹(shù)中的最小值（也就是3）和4交換，交換之后再去刪除下面那個(gè)結(jié)點(diǎn)就行。這樣也不會(huì)破壞數(shù)的結(jié)構(gòu)，
當(dāng)然你選擇刪除節(jié)點(diǎn)的左子樹(shù)的最大值也是可行的
知道了先交換之后，我們也要分情況來(lái)看，判斷右樹(shù)的第一個(gè)節(jié)點(diǎn)是否為最左節(jié)點(diǎn)
代碼如下
bool Erase(const K& key)
{
Node* parent = _root;
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->_left == nullptr)
{
//判斷是否為根節(jié)點(diǎn)
if (_root == cur)
{
_root = cur->_right;
}
//判斷是父親的左還是父親的右
else if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
}
//右為空
else if(cur->_right == nullptr)
{
//判斷是否為根節(jié)點(diǎn)
if (_root == cur)
{
_root = cur->_left;
}
//判斷是父親的左還是父親的右
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
}
else
{
parent = cur;
//定義右樹(shù)的最左節(jié)點(diǎn)
Node* subleft = cur->_right;
//往最左走
while (subleft->_left)
{
parent = subleft;
subleft = subleft->_left;
}
//交換
swap(subleft->_key, cur->_key);
//右樹(shù)第一個(gè)節(jié)點(diǎn)就是最左節(jié)點(diǎn)（沒(méi)有進(jìn)入循環(huán)）
if (parent == cur)
{
parent->_right = subleft->_right;
}
else
{
parent->_left = subleft->_right;
}
delete subleft;
}
return true;
}
}
return false;
}4.遍歷
對(duì)于搜索二叉樹(shù)，我們選擇中序遍歷，因?yàn)檫@樣遍歷出來(lái)的值是有序的。
這里我們先用非遞歸版本，遞歸版本在后面會(huì)寫(xiě)上。
使用stack來(lái)幫助我們操作，這里代碼的重要點(diǎn)就是cur，對(duì)cur進(jìn)行操作防止再次陷入循環(huán)。
循環(huán)著先往最左子樹(shù)走，邊走邊入棧，走到為空就結(jié)束循環(huán)，當(dāng)前取出的棧頂元素就是最左結(jié)點(diǎn)，先打印，再將 cur = top->_right;往top結(jié)點(diǎn)的右邊走，如此循環(huán)，便能中序遍歷。
代碼真的很巧妙，不理解的可以畫(huà)遞歸圖來(lái)幫助理解。
void InOrder()
{
stack<Node*> s;
Node* cur = _root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
s.pop();
cout << top->_key << " ";
cur = top->_right;
}
cout << endl;
}我們測(cè)試一下，代碼正常運(yùn)行。
四、二叉搜索樹(shù)的操作（遞歸）
1.遞歸插入
我們?yōu)榱四軌蜻M(jìn)行遞歸，需要再寫(xiě)一個(gè)函數(shù)，因?yàn)闊o(wú)法傳入_root進(jìn)行遞歸，這里我們將遞歸的函數(shù)用private修飾，防止類(lèi)外調(diào)用。
代碼邏輯跟普通的差不都，都是通過(guò)key來(lái)判斷，key比當(dāng)前結(jié)點(diǎn)的值大，就遞歸當(dāng)前節(jié)點(diǎn)的右邊，key比當(dāng)前結(jié)點(diǎn)的值小，就遞歸當(dāng)前節(jié)點(diǎn)的左邊，相等就返回。
重要的點(diǎn)是我們無(wú)法找到父親結(jié)點(diǎn)，因此可以選擇引用傳參，你給到的參數(shù)是root->left或者是 root->right，引用傳參傳遞的就是root->left或者是root->right的別名，因此找到合適的位置可以直接 root = new Node(key);
public:
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->_left, key);
}
else if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else
{
return false;
}
}2.遞歸查找
依然是用兩個(gè)函數(shù)，查找代碼比插入更簡(jiǎn)單，不多贅述
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->_left, key);
}
else if(root->_key < key)
{
return _FindR(root->_right, key);
}
else
{
return true;
}
}3.遞歸刪除
刪除也得使用引用，因?yàn)橐尭赣H結(jié)點(diǎn)指向空，因?yàn)閭鬟f的是別名，不需要讓父親跟隨了，因此代碼可以簡(jiǎn)潔不少，情況d（也就是左右都不為空），依然是用之前的交換，交換后再遞歸到右樹(shù)去查找即可。
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->_left, key);
}
else if (root->_key < key)
{
return _EraseR(root->_right, 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(subleft->_key, root->_key);
//到右子樹(shù)再去遞歸刪除
return _EraseR(root->_right, key);
}
}
return false;
}4.遞歸遍歷
更是小菜一碟，這是普通二叉樹(shù)的操作，遞歸左，打印，遞歸右即可。
public:
void InOrderR()
{
_InOrderR(_root);
cout << endl;
}
private:
void _InOrderR(Node* root)
{
if (root == nullptr)
return;
_InOrderR(root->_left);
cout << root->_key << " ";
_InOrderR(root->_right);
}五、二叉搜索樹(shù)的默認(rèn)成員函數(shù)
1.拷貝構(gòu)造
想要完成深拷貝，就需要將樹(shù)的所有結(jié)點(diǎn)都拷貝一遍，這里用遞歸處理也是很方便的，因此我們定義了一個(gè)Copy函數(shù)，去進(jìn)行先序遍歷拷貝。
public:
BSTree(const BSTree<K>& bst)
{
_root = Copy(bst._root);
}
private:
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* cur = new Node(root->_key);
cur->_left = Copy(root->_left);
cur->_right = Copy(root->_right);
return cur;
}2.賦值運(yùn)算符重載
這個(gè)很簡(jiǎn)單，不要傳遞 const 和 & 直接交換即可。
BSTree<K>& operator=(BSTree<K> bst)
{
swap(bst._root, _root);
return *this;
}3.析構(gòu)函數(shù)
調(diào)用后續(xù)遞歸函數(shù)進(jìn)行析構(gòu)
public:
~BSTree()
{
clear(_root);
}
private:
void clear(Node* root)
{
if (root == nullptr)
return;
clear(root->_left);
clear(root->_right);
delete root;
}4.默認(rèn)構(gòu)造函數(shù)
因?yàn)槲覀冎貙?xiě)了構(gòu)造函數(shù)，因此編譯器默認(rèn)構(gòu)造函數(shù)的就不提供了，我們隨便寫(xiě)一份，這里使用了C++11的新特性，default代表默認(rèn)生成
BSTree() = default;
到目前為止，我們的二叉搜索樹(shù)就算完成了，以下是代碼
namespace k
{
template<class T>
struct BSTreeNode
{
BSTreeNode<T>* _left;
BSTreeNode<T>* _right;
T _key;
BSTreeNode(const T& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree() = default;
BSTree(const BSTree<K>& bst)
{
_root = Copy(bst._root);
}
~BSTree()
{
clear(_root);
}
BSTree<K>& operator=(BSTree<K> bst)
{
swap(bst._root, _root);
return *this;
}
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
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
{
return false;
}
}
if (parent->_key > key)
{
parent->_left = new Node(key);
}
else
{
parent->_right = new Node(key);
}
return true;
}
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;
}
bool Erase(const K& key)
{
Node* parent = _root;
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->_left == nullptr)
{
//判斷是否為根節(jié)點(diǎn)
if (_root == cur)
{
_root = cur->_right;
}
//判斷是父親的左還是父親的右
else if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
}
//右為空
else if(cur->_right == nullptr)
{
//判斷是否為根節(jié)點(diǎn)
if (_root == cur)
{
_root = cur->_left;
}
//判斷是父親的左還是父親的右
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
}
else
{
parent = cur;
//定義右樹(shù)的最左節(jié)點(diǎn)
Node* subleft = cur->_right;
//往最左走
while (subleft->_left)
{
parent = subleft;
subleft = subleft->_left;
}
//交換
swap(subleft->_key, cur->_key);
//右樹(shù)第一個(gè)節(jié)點(diǎn)就是最左節(jié)點(diǎn)（沒(méi)有進(jìn)入循環(huán)）
if (parent == cur)
{
parent->_right = subleft->_right;
}
else
{
parent->_left = subleft->_right;
}
delete subleft;
}
return true;
}
}
return false;
}
void InOrder()
{
stack<Node*> s;
Node* cur = _root;
while (cur||!s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
s.pop();
cout << top->_key << " ";
cur = top->_right;
}
cout << endl;
}
void InOrderR()
{
_InOrderR(_root);
cout << endl;
}
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:
void clear(Node* root)
{
if (root == nullptr)
return;
clear(root->_left);
clear(root->_right);
delete root;
}
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* cur = new Node(root->_key);
cur->_left = Copy(root->_left);
cur->_right = Copy(root->_right);
return cur;
}
void _InOrderR(Node* root)
{
if (root == nullptr)
return;
_InOrderR(root->_left);
cout << root->_key << " ";
_InOrderR(root->_right);
}
bool _FindR(Node* root,const K& key)
{
if (root == nullptr)
return false;
if (root->_key > key)
{
return _FindR(root->_left, key);
}
else if(root->_key < key)
{
return _FindR(root->_right, key);
}
else
{
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->_left, key);
}
else if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else
{
return false;
}
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else if (root->_key < key)
{
return _EraseR(root->_right, 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(subleft->_key, root->_key);
//到右子樹(shù)再去遞歸刪除
return _EraseR(root->_right, key);
}
}
return false;
}
private:
Node* _root = nullptr;
};
}六、二叉搜索樹(shù)的KV模型
二叉搜索樹(shù)不僅僅有K模型，還有KV模型，我們只需要給結(jié)點(diǎn)多添加上一個(gè)value即可
template<class T, class V>
struct BSTreeNode
{
BSTreeNode<T,V>* _left;
BSTreeNode<T,V>* _right;
T _key;
V _value;
BSTreeNode(const T& key,const V&value)
:_left(nullptr)
,_right(nullptr)
,_key(key)
,_value(value)
{}
};代碼邏輯部分都是沒(méi)問(wèn)題的，只有少部分地方需要略做修改，大家直接看代碼吧
namespace kv
{
template<class T, class V>
struct BSTreeNode
{
BSTreeNode<T,V>* _left;
BSTreeNode<T,V>* _right;
T _key;
V _value;
BSTreeNode(const T& 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->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
if (parent->_key > key)
{
parent->_left = new Node(key,value);
}
else
{
parent->_right = new Node(key, value);
}
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 = _root;
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->_left == nullptr)
{
if (_root == cur)
{
_root = cur->_right;
}
else if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (_root == cur)
{
_root = cur->_left;
}
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
}
else
{
parent = cur;
Node* subleft = cur->_right;
while (subleft->_left)
{
parent = subleft;
subleft = subleft->_left;
}
swap(subleft->_key, cur->_key);
if (parent == cur)
{
parent->_right = subleft->_right;
}
else
{
parent->_left = subleft->_right;
}
delete subleft;
}
return true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
bool InsertR(const K& key,const V& value)
{
return _InsertR(_root, key,value);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " " << root->_value << endl;
_InOrder(root->_right);
}
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
return nullptr;
if (root->_key > key)
{
return _FindR(root->_left, key);
}
else if (root->_key < key)
{
return _FindR(root->_right, key);
}
else
{
return root;
}
}
bool _InsertR(Node*& root, const K& key,const V& value)
{
if (root == nullptr)
{
root = new Node(key,value);
return true;
}
if (root->_key > key)
{
return _InsertR(root->_left, key,value);
}
else if (root->_key < key)
{
return _InsertR(root->_right, key, value);
}
else
{
return false;
}
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else if (root->_key < key)
{
return _EraseR(root->_right, 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(subleft->_key, root->_key);
//到右子樹(shù)再去遞歸刪除
return _EraseR(root->_right, key);
}
}
return false;
}
private:
Node* _root = nullptr;
};
}KV模型測(cè)試
如此一來(lái)我們就算大功告成了。
到此這篇關(guān)于C++二叉搜索樹(shù)模擬實(shí)現(xiàn)示例的文章就介紹到這了,更多相關(guān)C++二叉搜索樹(shù)模擬內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- C++ 二叉搜索樹(shù)(BST)的實(shí)現(xiàn)方法
- C++實(shí)現(xiàn)LeetCode(108.將有序數(shù)組轉(zhuǎn)為二叉搜索樹(shù))
- C++數(shù)據(jù)結(jié)構(gòu)二叉搜索樹(shù)的實(shí)現(xiàn)應(yīng)用與分析
- C++ 超詳細(xì)快速掌握二叉搜索樹(shù)
- C++深入細(xì)致探究二叉搜索樹(shù)
- C++簡(jiǎn)單實(shí)現(xiàn)與分析二叉搜索樹(shù)流程
- C++?LeetCode0538二叉搜索樹(shù)轉(zhuǎn)換累加樹(shù)示例
- C++二叉搜索樹(shù)BSTree使用詳解
相關(guān)文章
C++教程之a(chǎn)rray數(shù)組使用示例詳解
這篇文章主要為大家介紹了C++教程之a(chǎn)rray數(shù)組使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-03-03
Detours 是一個(gè)兼容多個(gè)Windows系列操作系統(tǒng)版本（包括 Windows XP 到 Windows 11）的工具庫(kù),Detours 是微軟開(kāi)發(fā)的一個(gè)強(qiáng)大的Windows API鉤子庫(kù),用于監(jiān)視和攔截函數(shù)調(diào)用,這篇文章給大家介紹微軟Detours Hook庫(kù)編譯與使用,感興趣的朋友一起看看吧2024-08-08
這篇文章主要介紹了VSCode使用最新的C++20的相關(guān)知識(shí)，本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-03-03
C++實(shí)現(xiàn)浮點(diǎn)數(shù)精確加法
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)浮點(diǎn)數(shù)精確加法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
進(jìn)度條在很多時(shí)候都可以用到，有時(shí)我們需要在表格，樹(shù)狀欄中直觀顯示任務(wù)進(jìn)度或消耗百分比，本文就詳細(xì)的介紹一下Qt 進(jìn)度條的使用實(shí)例，感興趣的可以了解一下2021-06-06
左值(lvalue)和右值(rvalue)是 c/c++ 中一個(gè)比較晦澀基礎(chǔ)的概念,這篇文章主要給大家介紹了關(guān)于如何通過(guò)一篇文章弄懂C++左值引用和右值引用的相關(guān)資料,需要的朋友可以參考下2021-07-07
C++實(shí)現(xiàn)LeetCode(56.合并區(qū)間)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(56.合并區(qū)間),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++構(gòu)造函數(shù)初始化列表的實(shí)現(xiàn)詳解
構(gòu)造函數(shù)主要作用在于創(chuàng)建對(duì)象時(shí)為對(duì)象的成員屬性賦值，構(gòu)造函數(shù)由編譯器自動(dòng)調(diào)用,無(wú)須手動(dòng)調(diào)用；析構(gòu)函數(shù)主要作用在于對(duì)象銷(xiāo)毀前系統(tǒng)自動(dòng)調(diào)用，執(zhí)行一 些清理工作2022-09-09
這篇文章主要介紹了C++中的extern “C”用法詳解,簡(jiǎn)單來(lái)說(shuō),extern “C”是C++聲明或定義C語(yǔ)言符號(hào)的方法,是為了與C兼容,需要的朋友可以參考下2015-03-03
一篇文章讓你輕松理解C++中vector和list區(qū)別
對(duì)于學(xué)c語(yǔ)言的同學(xué)來(lái)說(shuō),vector和list這兩個(gè)東西經(jīng)常會(huì)搞錯(cuò),下面這篇文章主要給大家介紹了關(guān)于C++中vector和list區(qū)別的相關(guān)資料,需要的朋友可以參考下2022-01-01