C++數(shù)據(jù)結(jié)構(gòu)二叉搜索樹(shù)的實(shí)現(xiàn)應(yīng)用與分析
更新時(shí)間：2022年02月28日 14:48:32 作者：呆呆獸學(xué)編程
從這篇博客開(kāi)始，我就要和大家介紹有關(guān)二叉搜索樹(shù)的知識(shí)，它還衍生出了兩棵樹(shù)——AVL樹(shù)和紅黑樹(shù)，在后面兩篇博客我都會(huì)介紹。今天先從二叉搜索樹(shù)開(kāi)始引入
??博客代碼已上傳至gitee：https://gitee.com/byte-binxin/cpp-class-code
??概念
二叉搜索樹(shù)又稱(chēng)為二叉排序書(shū)，因?yàn)檫@棵樹(shù)的中序遍歷是有序的。二叉搜索樹(shù)總結(jié)起來(lái)有以下幾個(gè)性質(zhì)：
- 若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
- 若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于于根節(jié)點(diǎn)的值
- 它的左右子樹(shù)都是二叉搜索樹(shù)
- 這棵樹(shù)中沒(méi)有重復(fù)的元素
??二叉搜索樹(shù)的實(shí)現(xiàn)
??基本框架
由一個(gè)節(jié)點(diǎn)的成員構(gòu)成，先構(gòu)建節(jié)點(diǎn)的類(lèi)型，和我們之前數(shù)據(jù)結(jié)構(gòu)中的二叉樹(shù)的節(jié)點(diǎn)定義是一樣的。二叉搜索樹(shù)的根節(jié)點(diǎn)先默認(rèn)給空。
template <class K, class V>
struct BSTNode
{
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
K _key;
V _value;
BSTNode(const K& key, const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)
{}
};
template <class K, class V>
class BSTree //Binary Search Tree
{
typedef BSTNode<K, V> Node;
private:
Node* _root = nullptr;
};
??二叉搜索樹(shù)的插入
插入分為下面幾個(gè)步驟：
- 先判斷樹(shù)是否為空，為空就讓要插入的這個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)，然后結(jié)束
- 部署就確定要插入節(jié)點(diǎn)的位置
- 用一個(gè)cur記錄當(dāng)前節(jié)點(diǎn)，parent記錄父節(jié)點(diǎn)
- 要插入節(jié)點(diǎn)的值如果比當(dāng)前節(jié)點(diǎn)的值小，cur就往左走，如果比當(dāng)前節(jié)點(diǎn)的值大，就往右子樹(shù)走，如果等于就返回false，表面這棵樹(shù)中有這個(gè)數(shù)據(jù)，不需要插入。
下面是一個(gè)簡(jiǎn)單的動(dòng)圖演示
注意： 這里不用擔(dān)心新插入節(jié)點(diǎn)會(huì)在樹(shù)中間插入，它一定是在最下面插入的，它會(huì)走到最下面，然后在樹(shù)的底部插入。
代碼實(shí)現(xiàn)如下：
bool Insert(const K& key, const V& value)
{
// 沒(méi)有節(jié)點(diǎn)時(shí)第一個(gè)節(jié)點(diǎn)就是根節(jié)點(diǎn)
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
// 用一個(gè)父親節(jié)點(diǎn)記錄cur的上一個(gè)節(jié)點(diǎn)
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
// 小于往左邊走
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else
return false;// 已有的節(jié)點(diǎn)不插入，此次插入失敗
}
cur = new Node(key, value);
// 判斷應(yīng)該插在父節(jié)點(diǎn)的左邊還是右邊
if (cur->_key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
為了更好地觀(guān)察這棵樹(shù)插入后是否有效，我們可以實(shí)現(xiàn)一個(gè)中序遍歷，將其打印出來(lái)。 中序遍歷代碼如下：
void InOrder()
{
// 利用子函數(shù)遍歷
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
測(cè)試代碼如下：
void TestBSTree()
{
BSTree<int> bt;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
//int arr[] = { 1,2,3,4 };
//int arr[] = { 4,3,2,1};
for (auto e : arr)
{
bt.Insert(e);
}
bt.InOrder();
}
代碼運(yùn)行結(jié)果如下：
??二叉搜索樹(shù)的查找
查找的步驟如下：（和插入的步驟有些類(lèi)似）
- 如果查找值key比當(dāng)前節(jié)點(diǎn)的值小，就往左子樹(shù)走
- 如果查找值key比當(dāng)前節(jié)點(diǎn)的值大，就往右子樹(shù)走
- 如果查找值key和當(dāng)前節(jié)點(diǎn)的值相等，就返回當(dāng)前節(jié)點(diǎn)的指針
代碼實(shí)現(xiàn)如下：
Node* Find(const K& key)
{
if (_root == nullptr)
return nullptr;
Node* cur = _root;
while (cur)
{
// 小于往左邊走
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else
return cur;
}
return nullptr;
}
??二叉搜索樹(shù)的刪除（重點(diǎn)）
二叉搜索樹(shù)的刪除相對(duì)來(lái)說(shuō)會(huì)復(fù)雜一些，下面我要給大家分析一下。 有四種情況 先看下面這棵樹(shù)，分別對(duì)以下四個(gè)節(jié)點(diǎn)進(jìn)行刪除會(huì)發(fā)生什么（如何處理）？
- 刪除節(jié)點(diǎn)1時(shí)，它的左右都為空，可以直接刪除
- 刪除節(jié)點(diǎn)2時(shí)，它的左不為空右為空，刪除方法如下：
還要分析一種特殊的情況，就是此時(shí)2沒(méi)有父親節(jié)點(diǎn)，也就是自己為根時(shí)，看下面如何操作
- 刪除節(jié)點(diǎn)7時(shí)，它的左為為右不為空，刪除方法如下：
和情況2一樣，該節(jié)點(diǎn)如果為根節(jié)點(diǎn)，就讓自己的右孩子變成根節(jié)點(diǎn)。
- 左右都不為空（替代法）
這種情況我們采用替代法來(lái)解決，替代法就是找一個(gè)節(jié)點(diǎn)和現(xiàn)在這個(gè)節(jié)點(diǎn)交換，然后轉(zhuǎn)移為上面的情況，具體如下： 我們可以選擇用左子樹(shù)的最右節(jié)點(diǎn)（左子樹(shù)最大的節(jié)點(diǎn)）或右子樹(shù)的最左節(jié)點(diǎn)（右子樹(shù)的最小節(jié)點(diǎn)）和當(dāng)前節(jié)點(diǎn)互換，然后刪除互換后的節(jié)點(diǎn)，這里我們統(tǒng)一采用用右子樹(shù)的最右節(jié)點(diǎn)來(lái)進(jìn)行替換。
然后這里可以轉(zhuǎn)化為情況3來(lái)對(duì)節(jié)點(diǎn)進(jìn)行刪除，因?yàn)樗械淖钭蠛⒆右欢ㄊ亲鬄榭?，右是不確定的。
總結(jié)： 一共有四種情況，但是情況1可以歸為情況3，因?yàn)樗彩亲鬄榭?，所以整體處理下來(lái)是三種情況。
代碼實(shí)現(xiàn)如下：
bool Erase(const K& key)
{
// 如果樹(shù)為空，刪除失敗
if (_root == nullptr)
return false;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 小于往左邊走
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到了，開(kāi)始刪除
// 1.左右子樹(shù)都為空 直接刪除 可以歸類(lèi)為左為空
// 2.左右子樹(shù)只有一邊為空 左為空，父親指向我的右，右為空，父親指向我的左
// 3.左右子樹(shù)都不為空 取左子樹(shù)最大的節(jié)點(diǎn)或右子樹(shù)最小的節(jié)點(diǎn)和要?jiǎng)h除的節(jié)點(diǎn)交換，然后再刪除
if (cur->_left == nullptr)
{
// 要?jiǎng)h除節(jié)點(diǎn)為根節(jié)點(diǎn)時(shí)，直接把右子樹(shù)的根節(jié)點(diǎn)賦值給——root
// 根節(jié)點(diǎn)的話(huà)會(huì)導(dǎo)致parent為nullptr
if (_root == cur)
{
_root = _root->_right;
}
else
{
// 左為空，父親指向我的右
// 判斷cur在父親的左還是右
if (parent->_left == cur) // cur->_key < parent->_key
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
cur = nullptr;
}
else if (cur->_right == nullptr)
{
if (_root == cur)
{
_root = _root->_left;
}
else
{
// 右為空，父親指向我的左
// 判斷cur在父親的左還是右
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
cur = nullptr;
}
else
{
// 找右子樹(shù)中最小的節(jié)點(diǎn)
Node* rightMinParent = cur;
Node* rightMin = cur->_right;// 去右子樹(shù)找
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
//swap(cur->_key, rightMin->_key);
// 替代刪除
cur->_key = rightMin->_key;
// 轉(zhuǎn)換成了第一種情況 左為空
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
rightMin = nullptr;
}
return true;
}
}
return false;
}
測(cè)試代碼如下：（要測(cè)試每種情況，還有測(cè)試刪空的情況）
void TestBSTree()
{
BSTree<int> bt;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
for (auto e : arr)
{
cout << "插入 " << e << " 后：";
bt.Insert(e);
bt.InOrder();
}
cout << "------------------------------" << endl;
for (auto e : arr)
{
cout << "刪除 " << e << " 后：";
bt.Erase(e);
bt.InOrder();
}
}
代碼運(yùn)行結(jié)果如下：
??二叉搜索樹(shù)的應(yīng)用
二叉搜索樹(shù)有兩種模型：
- K模型： K模型只有key值，節(jié)點(diǎn)只存儲(chǔ)key值。這里主要應(yīng)用就是查找判斷某個(gè)元素在不在。
- KV模型： KV模型每個(gè)key值都對(duì)應(yīng)著一個(gè)value，主要應(yīng)用就是通過(guò)key找value。（我們平時(shí)查找單詞就是通過(guò)中文找英文，或者通過(guò)英文找中文）
下面我把上面的K模型的代碼簡(jiǎn)單改造一下，實(shí)現(xiàn)KV模型：（這里沒(méi)有使用傳鍵值對(duì)的方法，之后的博客我會(huì)給大家介紹，這里使用傳兩個(gè)值的方式）
template <class K, class V>
struct BSTNode
{
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
K _key;
V _value;
BSTNode(const K& key, const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)
{}
};
template <class K, class V>
class BSTree //Binary Search Tree
{
typedef BSTNode<K, V> Node;
public:
~BSTree()
{
Node* cur = _root;
while (cur)
{
Erase(cur->_key);
cur = _root;
}
}
Node* Find(const K& key)
{
if (_root == nullptr)
return nullptr;
Node* cur = _root;
while (cur)
{
// 小于往左邊走
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else
return cur;
}
return nullptr;
}
bool Insert(const K& key, const V& value)
{
// 沒(méi)有節(jié)點(diǎn)時(shí)第一個(gè)節(jié)點(diǎn)就是根節(jié)點(diǎn)
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
// 用一個(gè)父親節(jié)點(diǎn)記錄cur的上一個(gè)節(jié)點(diǎn)
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
// 小于往左邊走
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else
return false;// 已有的節(jié)點(diǎn)不插入，此次插入失敗
}
cur = new Node(key, value);
// 判斷應(yīng)該插在父節(jié)點(diǎn)的左邊還是右邊
if (cur->_key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
bool Erase(const K& key)
{
// 如果樹(shù)為空，刪除失敗
if (_root == nullptr)
return false;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 小于往左邊走
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到了，開(kāi)始刪除
// 1.左右子樹(shù)都為空 直接刪除 可以歸類(lèi)為左為空
// 2.左右子樹(shù)只有一邊為空 左為空，父親指向我的右，右為空，父親指向我的左
// 3.左右子樹(shù)都不為空 取左子樹(shù)最大的節(jié)點(diǎn)或右子樹(shù)最小的節(jié)點(diǎn)和要?jiǎng)h除的節(jié)點(diǎn)交換，然后再刪除
if (cur->_left == nullptr)
{
// 要?jiǎng)h除節(jié)點(diǎn)為根節(jié)點(diǎn)時(shí)，直接把右子樹(shù)的根節(jié)點(diǎn)賦值給——root
// 根節(jié)點(diǎn)的話(huà)會(huì)導(dǎo)致parent為nullptr
if (_root == cur)
{
_root = _root->_right;
}
else
{
// 左為空，父親指向我的右
// 判斷cur在父親的左還是右
if (parent->_left == cur) // cur->_key < parent->_key
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
cur = nullptr;
}
else if (cur->_right == nullptr)
{
if (_root == cur)
{
_root = _root->_left;
}
else
{
// 右為空，父親指向我的左
// 判斷cur在父親的左還是右
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
cur = nullptr;
}
else
{
// 找右子樹(shù)中最小的節(jié)點(diǎn)
Node* rightMinParent = cur;
Node* rightMin = cur->_right;// 去右子樹(shù)找
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
//swap(cur->_key, rightMin->_key);
// 替代刪除
cur->_key = rightMin->_key;
// 轉(zhuǎn)換成了第一種情況 左為空
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
rightMin = nullptr;
}
return true;
}
}
return false;
}
void InOrder()
{
// 利用子函數(shù)遍歷
_InOrder(_root);
cout << endl;
}
private:
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 TestBSTree_KV1()
{
// 創(chuàng)建一個(gè)簡(jiǎn)易的字典
BSTree<string, string> dict;
dict.Insert("蘋(píng)果", "apple");
dict.Insert("排序", "sort");
dict.Insert("培養(yǎng)", "cultivate");
dict.Insert("通過(guò)", "pass");
dict.Insert("apple", "蘋(píng)果");
dict.Insert("sort", "排序");
dict.Insert("cultivate", "培養(yǎng)");
dict.Insert("pass", "通過(guò)");
string str;
while (cin >> str)
{
BSTNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "本字典無(wú)此詞" << endl;
}
}
下面測(cè)試幾個(gè)應(yīng)用： 實(shí)例1 英漢字典
void TestBSTree_KV1()
{
// 創(chuàng)建一個(gè)簡(jiǎn)易的字典
BSTree<string, string> dict;
dict.Insert("蘋(píng)果", "apple");
dict.Insert("排序", "sort");
dict.Insert("培養(yǎng)", "cultivate");
dict.Insert("通過(guò)", "pass");
dict.Insert("apple", "蘋(píng)果");
dict.Insert("sort", "排序");
dict.Insert("cultivate", "培養(yǎng)");
dict.Insert("pass", "通過(guò)");
string str;
while (cin >> str)
{
BSTNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "本字典無(wú)此詞" << endl;
}
}
}
代碼運(yùn)行結(jié)果演示：
實(shí)例2： 統(tǒng)計(jì)樹(shù)
void TestBSTree_KV2()
{
// 統(tǒng)計(jì)水果個(gè)數(shù)
BSTree<string, int> countTree;
string strArr[] = { "香蕉","水蜜桃","西瓜","蘋(píng)果","香蕉" ,"西瓜","香蕉" ,"蘋(píng)果","西瓜","蘋(píng)果","蘋(píng)果","香蕉" ,"水蜜桃" };
for (auto e : strArr)
{
BSTNode<string, int>* ret = countTree.Find(e);
if (ret == nullptr)
{
// 第一次插入
countTree.Insert(e, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();
}
代碼運(yùn)行結(jié)果如下：
??二叉樹(shù)性能分析
一般情況下，二叉搜索樹(shù)的插入和刪除的效率都是O(logN)，極端情況會(huì)導(dǎo)致效率變成O(N)。
理想狀態(tài)： 完全二叉樹(shù)：O(logN)
極端情況： 一條鏈：O(1)
后面我要和大家分析的AVL樹(shù)會(huì)利用旋轉(zhuǎn)，就可解決掉這種極端情況。
??總結(jié)
上面這些是二叉搜索樹(shù)的大致內(nèi)容，其中刪除大家可以好好理解一下，它后面還有兩棵樹(shù)我還沒(méi)有介紹，就是AVL樹(shù)和紅黑樹(shù)，在后面兩篇博客我都會(huì)介紹。今天就先到這了，喜歡的話(huà)，歡迎點(diǎn)贊支持~
到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)二叉搜索樹(shù)的實(shí)現(xiàn)應(yīng)用與分析的文章就介紹到這了,更多相關(guān)C++ 二叉搜索樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文主要介紹了C++空間命名的使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
C/C++語(yǔ)言八大排序算法之桶排序全過(guò)程示例詳解
這篇文章主要為大家介紹了C/C++語(yǔ)言八大排序算法之桶排序算法過(guò)程的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助,祝大家多多進(jìn)步2021-11-11
C語(yǔ)言超詳細(xì)講解指針與結(jié)構(gòu)體
指針提供了對(duì)地址操作的一種方法，因此，使用指針可使得C語(yǔ)言能夠更高效地實(shí)現(xiàn)對(duì)計(jì)算機(jī)底層硬件的操作。另外，通過(guò)指針可以更便捷地操作數(shù)組。C數(shù)組允許定義可存儲(chǔ)相同類(lèi)型數(shù)據(jù)項(xiàng)的變量，結(jié)構(gòu)是C編程中另一種用戶(hù)自定義的可用的數(shù)據(jù)類(lèi)型，它允許您存儲(chǔ)不同類(lèi)型的數(shù)據(jù)項(xiàng)2022-05-05
C++實(shí)現(xiàn)當(dāng)前時(shí)間動(dòng)態(tài)顯示的方法
這篇文章主要介紹了C++實(shí)現(xiàn)當(dāng)前時(shí)間動(dòng)態(tài)顯示的方法,涉及C++時(shí)間操作及Sleep方法的使用,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07
c++語(yǔ)言的靈活是建立在對(duì)編程者個(gè)人的編程素質(zhì)的嚴(yán)格要求基礎(chǔ)上的，好的C++編程習(xí)慣能避免很多問(wèn)題。沒(méi)有好的編程習(xí)慣，極有可能編寫(xiě)一行代碼，編譯器能報(bào)十幾個(gè)錯(cuò)誤，而且就算編譯通過(guò)了，將來(lái)在運(yùn)行過(guò)程中也會(huì)有很多莫名奇妙的問(wèn)題2021-06-06
AT&T 匯編是一種和intel匯編在語(yǔ)法上完全不同的匯編語(yǔ)言，為避免混淆intel語(yǔ)法，本文只介紹AT&T匯編，AT&T的第一個(gè)特點(diǎn)就是每個(gè)寄存器名前必須加‘%’,立即數(shù)前必須加‘$’2019-02-02
今天小編就為大家分享一篇關(guān)于C語(yǔ)言用fstat函數(shù)獲取文件的大小方法，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-12-12
C語(yǔ)言中沒(méi)有BOOL類(lèi)型變量,它是C++獨(dú)有的,由于使用BOOL類(lèi)型可以使代碼更具有可讀性,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中bool變量的相關(guān)資料,需要的朋友可以參考下2021-08-08
C/C++?Qt?數(shù)據(jù)庫(kù)與TableView實(shí)現(xiàn)多組件聯(lián)動(dòng)
Qt?數(shù)據(jù)庫(kù)組件與TableView組件實(shí)現(xiàn)聯(lián)動(dòng)效果，本文通過(guò)案例給大家講解的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友參考下吧2021-12-12
這篇文章主要介紹了Vc++ 控件List Control用法總結(jié)的相關(guān)資料,需要的朋友可以參考下2015-06-06