C++簡單實現(xiàn)與分析二叉搜索樹流程
更新時間：2022年08月29日 09:11:13 作者：小小酥誒
二叉搜索樹作為一個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，具有鏈表的快速插入與刪除的特點，同時查詢效率也很優(yōu)秀，所以應(yīng)用十分廣泛。本文將詳細(xì)講講二叉搜索樹的C++實現(xiàn)，需要的可以參考一下
二叉搜索樹
二叉搜索樹又被稱為二叉排序樹。它可以是一個空樹，如果不是空樹則滿足下列性質(zhì)：
1、如果它的左子樹不為空，那么左子樹上的所有節(jié)點都小于根。
2、如果它的右子樹不為空，那么右子樹上的所有節(jié)點都大于根
3、它的左子樹、右子樹也是二叉搜索樹。
二叉搜索樹的重要操作
二叉搜索樹的插入
1、如果樹為空，則直接插入
2、如果樹不為空，則找到對應(yīng)的位置插入。
查找辦法：
根據(jù)二叉搜索樹的性質(zhì)，
1、如果給出的關(guān)鍵碼比當(dāng)前節(jié)點的關(guān)鍵碼小，則在當(dāng)前節(jié)點的左子樹中找位置
2、如果給出的關(guān)鍵碼比當(dāng)前節(jié)點的關(guān)鍵碼大，則在當(dāng)前節(jié)點的右子樹中找位置
如此反復(fù)循環(huán)……，直到找到一個空的位置插入。
二叉搜索樹的刪除
刪除分為三種情況：
- 情況一：要刪除的節(jié)點左孩子為空
- 情況二：要刪除的節(jié)點左孩子不為空，右孩子為空
- 情況三：要刪除的節(jié)點既有左孩子也有右孩子。
刪除情況一分析：
例如，刪除關(guān)鍵碼為1的節(jié)點。它的左孩子為空，那么遍歷這個二叉樹，找到這個節(jié)點。讓這個節(jié)點的父親節(jié)點指向該節(jié)點的右孩子節(jié)點
但是需要考慮刪除節(jié)點的父節(jié)點是右孩子指向，還是左孩子指向。
刪除情況二分析：
例如，刪除關(guān)鍵碼為7的節(jié)點。它的左孩子不為空，右孩子為空。首先遍歷這個二叉樹，找到這個節(jié)點。讓這個節(jié)點的父親節(jié)點指向該節(jié)點的左孩子節(jié)點。同樣需要考慮刪除節(jié)點的父節(jié)點是左孩子指向還是右孩子指向。
情況一和情況二都面臨這樣一個問題，如果刪除的是根節(jié)點則需要單獨考慮。
刪除情況三分析：
解決辦法：替換法
替換法：如果刪除節(jié)點既有左孩子又有右孩子，為了刪除之后依舊能使其保留二叉搜索樹的性質(zhì)，則需要將刪除的節(jié)點和一個合適的節(jié)點進(jìn)行替換，使這個合適的節(jié)點替換到刪除節(jié)點的位置，然后刪除被替換的節(jié)點即可解決。
兩個合適的節(jié)點：
1、刪除節(jié)點的左子樹中最大節(jié)點。
2、刪除節(jié)點的右子樹中最小節(jié)點。
例如，刪除關(guān)鍵碼為5的節(jié)點。它的左孩子、右孩子都不為空。首先遍歷這個二叉樹，找到這個節(jié)點。為使刪除后依舊能保持二叉搜索樹的性質(zhì)，需要挑選一個合適的節(jié)點進(jìn)行替換。這個合適的節(jié)點是關(guān)鍵碼為4的節(jié)點（刪除節(jié)點的左子樹中最大節(jié)點）和關(guān)鍵碼為6的節(jié)點（刪除節(jié)點的右子樹中最小節(jié)點），選一個即可。將替換節(jié)點的值給刪除節(jié)點后，刪除替換節(jié)點，然后這個時候就轉(zhuǎn)變?yōu)榱藙h除情況一了，按照刪除情況一的做法即可完美刪除！
二叉搜索樹實現(xiàn)(key模型)
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;
public:
BSTree()
:_root(nullptr)
{}
//insert
bool insert(const K& key)
{
if (_root == nullptr)
{
//為空
//直接就是給成根節(jié)點
_root = new Node(key);
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; //已經(jīng)有了，則不能插入
}
}
cur = new Node(key);
if (parent->_key > 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 (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
bool erase(const K& value)
{
if (_root == nullptr)
{
return false;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > value)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < value)
{
parent = cur;
cur = cur->_right;
}
else
{
//找到了，開始刪除
//情況一：要刪除的節(jié)點左孩子為空
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
//刪除的是根節(jié)點
_root = cur->_right;
}
//判斷刪除的是左孩子節(jié)點還是右孩子節(jié)點以便更改連接關(guān)系
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)
{
//情況二：要刪除的節(jié)點左孩子不為空、右孩子為空
if (parent == nullptr)
{
//刪除的是根節(jié)點
_root = cur->_left;
}
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
}
else
{
//情況三：要刪除的節(jié)點即有左孩子也有右孩子
//使用替換法
//兩種替換：1、用該節(jié)點的左子樹最大節(jié)點 2、用該節(jié)點右子樹的最小節(jié)點
//這里使用第一種替換方法
//找到用于替換的節(jié)點
Node* maxParent = cur;
Node* maxCur = cur->_right;
while (maxCur->_right)
{
maxParent = maxCur;
maxCur = maxCur->_right;
}
//
cur->_key = maxCur->_key;
//刪除用于替換的節(jié)點
if (maxParent->_left == maxCur)
{
maxParent->_left = maxCur->_left;
}
else
{
maxParent->_right = maxCur->_left;
}
delete maxCur;
}
return true;
}
}
//要刪除的節(jié)點不存在
return false;
}
//由于類外使用不到私有成員_root
//增加一個函數(shù)
void inorder()
{
_inorder(_root);
}
//遞歸版
Node* 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 _inorder(Node* root) //不需要在類外顯示調(diào)用它，所以放在私有
{
if (root == nullptr)
{
return;
}
_inorder(root->_left);
cout << root->_key << " ";
_inorder(root->_right);
}
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return nullptr;
}
if (root->_key > key)
{
_FindR(root->_left, key);
}
else if (root->_key < key)
{
_FindR(root->_right, key);
}
else
{
//找到了
return root;
}
}
bool _insertR(Node*& root, const K& key) //注意root加引用
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key > key)
{
_insertR(root->_left, key);
}
else if (root->_key < key)
{
_insertR(root->_right, key);
}
else
{
return false;
}
}
bool _eraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
//都已經(jīng)找到空了，表示不存在
return false;
}
if (root->_key > key)
{
_eraseR(root->_left, key);
}
else if (root->_key < key)
{
_eraseR(root->_right, key);
}
else
{
//找到要刪除的節(jié)點了，開始刪除
Node* del = root;
//左孩子為空
if (root->_left == nullptr)
{
root = root->_right; //使用了引用，直接就是
}
else if (root->_right == nullptr)
{
//左孩子不為空，右孩子為空
root = root->_left;
}
else
{
Node* min = root->_right;
while (min->_left)
{
min = min->_left;
}
swap(min->_key, root->_key);
// 遞歸到右子樹去刪除
return _eraseR(root->_right, key);
}
delete del;
return true;
}
}
private:
Node* _root;
};二叉搜索樹的應(yīng)用
應(yīng)用一：排序+去重
應(yīng)用二：key模型、key/value模型
二叉搜索樹的排序體現(xiàn)在中序遍歷二叉搜索樹時是有序的。
key模型：key模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲Key即可，關(guān)鍵碼即為需要搜索到的值。其價值在于判斷“在不在”。
比如：給一個單詞word，判斷該單詞是否拼寫正確，具體方式如下：
以單詞集合中的每個單詞作為key，構(gòu)建一棵二叉搜索樹
在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤。
key/value模型：每一個關(guān)鍵碼key，都有與之對應(yīng)的值Value，即<Key, Value>的鍵值對。該種方式在現(xiàn)實生活中非常常見。其價值在于可通過一個信息,找到其對應(yīng)的其他東西。。
比如：
1、通過英文查找對應(yīng)的中文；
2、高鐵檢票通過身份證查找對應(yīng)的乘車信息……
二叉搜索樹的實現(xiàn)(key/value模型)
//二叉搜索樹key/value模型
namespace KV
{
template<class K, class V>
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _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:
BSTree()
:_root(nullptr)
{}
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;
}
}
cur = new Node(key, value);
//
if (parent->_key > key)
{
//插入左孩子節(jié)點
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
Node* Find(const K& key)
{
if (_root == nullptr)
{
return nullptr;
}
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;
}
bool Erase(const K& key)
{
if (_root == nullptr)
{
return false;
}
//找到要刪除的節(jié)點
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
{
//找到了
//開始刪除
//情況一：要刪除的節(jié)點沒有左子樹
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
//刪除的是根節(jié)點
_root = cur->_right;
}
//判斷刪除的是左孩子節(jié)點還是右孩子節(jié)點，方便更改連接關(guān)系
if (parent->_left = cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)
{
//情況二：要刪除的節(jié)點左孩子不為空，，右孩子為空
if (parent == nullptr)
{
_root = cur->_left;
}
if (parent->_left = cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
}
else
{
//情況三：要刪除的節(jié)點既有左孩子也有右孩子
//要使用替換法刪除
//使用右子樹的最小節(jié)點進(jìn)行替換
Node* minParent = cur;
Node* minCur = cur->_right;
//找到右子樹的最小節(jié)點
while (minCur->_left)
{
minParent = minCur;
minCur = minCur->_left;
}
//替換
cur->_key = minCur->_key;
cur->_value = minCur->_value;
//刪除替換節(jié)點，并更改連接關(guān)系
if (minParent->_left == minCur)
{
minParent->_left = minCur->_right;
}
else
{
minParent->_right = minCur->_right;
}
delete minCur;
}
return true;
}
}
return false;
}
void inorder()
{
_inorder(_root);
}
private:
void _inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_inorder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_inorder(root->_right);
}
private:
Node* _root;
};
}到此這篇關(guān)于C++簡單實現(xiàn)與分析二叉搜索樹流程的文章就介紹到這了,更多相關(guān)C++二叉搜索樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家介紹了c++的glog與spdlog的性能對比測試分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
MATLAB自帶的進(jìn)度條是很簡單的，這樣的進(jìn)度條顯得冷冰冰的。因此，本文將用Matlab來DIY一款專屬的進(jìn)度條，感興趣的小伙伴可以了解一下2022-02-02
本文講解的是如何在C++中通過模板去除強制轉(zhuǎn)換，在編程工作中應(yīng)盡量少使用強制類型轉(zhuǎn)換，模板有助于我們實現(xiàn)這一目的,需要的朋友可以參考下2015-07-07
C語言的isatty函數(shù)和ttyname函數(shù)以及sendmsg函數(shù)用法
這篇文章主要介紹了C語言的isatty函數(shù)和ttyname函數(shù)以及sendmsg函數(shù)用法,是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
本篇文章是對c++中的變量類型進(jìn)行了詳細(xì)的分析介紹。需要的朋友參考下2013-05-05
這篇文章主要為大家詳細(xì)介紹了STL中vector的使用，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
本文給大家介紹的是使用C語言實現(xiàn)php的trim標(biāo)簽功能的代碼，非常的實用，其主要作用是清除字符串開頭結(jié)尾除空白，有需要的小伙伴可以參考下。2016-01-01
C++數(shù)據(jù)結(jié)構(gòu)深入探究棧與隊列
棧和隊列，嚴(yán)格意義上來說，也屬于線性表，因為它們也都用于存儲邏輯關(guān)系為 "一對一" 的數(shù)據(jù)，但由于它們比較特殊，本章講解分別用隊列實現(xiàn)棧與用棧實現(xiàn)隊列2022-05-05
掃雷是一款經(jīng)典的小游戲，這篇文章主要為大家詳細(xì)介紹了C語言輕松實現(xiàn)掃雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
今天遇到單向鏈表的反轉(zhuǎn)的問題,于是靜下心來好好想了一番。下面這篇文章主要給大家介紹了關(guān)于單鏈表反轉(zhuǎn)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-02-02