目錄
一，概念
二，實(shí)現(xiàn)分析
1. ?插入
（1.）非遞歸版本?
?（2.）遞歸版本
?2. 打印搜索二叉樹(shù)
3.查找函數(shù)
（1.）非遞歸版本
（2.）遞歸版本
4. 刪除函數(shù)（重難點(diǎn)）?
易錯(cuò)點(diǎn)分析，包你學(xué)會(huì)
（1.）刪除目標(biāo)，沒(méi)有左右孩子
（2.）刪除目標(biāo)，只有一個(gè)孩子
（3.）刪除目標(biāo)，有兩個(gè)孩子
代碼
（1.）非遞歸版本?
（2.）遞歸版本
5. 析構(gòu)函數(shù)
6.拷貝構(gòu)造?
?三，應(yīng)用
?四，搜索二叉樹(shù)的缺陷及優(yōu)化
五，代碼匯總
結(jié)語(yǔ)
一，概念
二叉搜索樹(shù)又稱(chēng)二叉排序樹(shù)，它或者是一棵空樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù):
若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值它的左右子樹(shù)也分別為二叉搜索樹(shù)
為啥又被稱(chēng)作二叉排序樹(shù)呢？ 當(dāng)該樹(shù)被層序遍歷時(shí)，就是升序。
二，實(shí)現(xiàn)分析
實(shí)驗(yàn)例子：
int a[] = {8, 3, 1, 10, 6, 4, 5, 7, 14, 13};?
1. ?插入
（1.）非遞歸版本?
a、從根開(kāi)始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。b、最多查找高度次，走到到空，還沒(méi)找到，這個(gè)值不存在。
?比較簡(jiǎn)單這里就直接放代碼：
template <class K>
class BinarySeaTree_node
{
typedef BinarySeaTree_node<K> BST_node;
public:
BinarySeaTree_node(const K& val)
: _val(val)
,_left(nullptr)
,_right(nullptr)
{}
K _val;
BST_node* _left;
BST_node* _right;
};
template <class T>
class BSTree
{
typedef BinarySeaTree_node<T> BST_node;
private:
BST_node* root = nullptr;
public:
bool Insert(const T& val)
{
BST_node* key = new BST_node(val);
BST_node* cur = root;
BST_node* parent = nullptr;
while (cur)
{
if (key->_val < cur->_val)
{
parent = cur;
cur = cur->_left;
}
else if (key->_val > cur->_val)
{
parent = cur;
cur = cur->_right;
}
else
{
return 0;
}
}
// 查詢(xún)好位置后，建立鏈接
if (!root)
{
root = key;
return 0;
}
if (key->_val > parent->_val)
{
parent->_right = key;
}
else
{
parent->_left = key;
}
return 1;
}
};
?（2.）遞歸版本
這里面整了個(gè)活，大家注意了!!!
bool Re_Insert(const T& val){ return Re_Insert_table(root, val);}
bool Re_Insert_table(BST_node*& node, const T& val)
{
if (node == nullptr)
{
node = new BST_node(val);
return 1;
}
if (val < node->_left)
{
return Re_Insert_table(node->_left, val);
}
else if (val > node->_right)
{
return Re_Insert_table(node->_right, val);
}
else
{
return 0;
}
}這里方便大家理解，我給大家花一個(gè)遞歸展開(kāi)圖。
?2. 打印搜索二叉樹(shù)
?
插入的具體過(guò)程如下：
a. 樹(shù)為空，則直接新增節(jié)點(diǎn)，賦值給root指針b. 樹(shù)不空，按二叉搜索樹(shù)性質(zhì)查找插入位置，插入新節(jié)點(diǎn)
這里也是僅做代碼分享：?
void Print_table() { Re_Print(root); }
void Re_Print(const BST_node* node)
{
if (node == nullptr)
return;
Re_Print(node->_left);
cout << node->_val << " ";
Re_Print(node->_right);
}
3.查找函數(shù)
思路：其實(shí)也沒(méi)啥思路，比父結(jié)點(diǎn)小，就找左邊，否則找右邊。?
（1.）非遞歸版本
BST_node* Find(const T& val)
{
//直接跟尋找位置一樣
BST_node* parent = nullptr;
BST_node* cur = root; // 以返回cur的方式返回
while (cur) // 非遞歸版本
{
if (val < cur->_val)
{
parent = cur;
cur = cur->_left;
}
else if (val > cur->_val)
{
parent = cur;
cur = cur->_right;
}
else
{
return cur;
}
}
return cur;
}（2.）遞歸版本
BST_node* Re_Find(const T& val){ return Re_Find_table(root, val); }
BST_node* Re_Find_table(BST_node* node, const T& val)
{
if (node == nullptr)
return nullptr;
if (val < node->_val)
{
return Re_Find_table(node->_left, val);
}
else if (val > node->_val)
{
return Re_Find_table(node->_right, val);
}
else
{
return node;
}
}4. 刪除函數(shù)（重難點(diǎn)）?
我們簡(jiǎn)單尋找了一下思路，如下：
但這些思路只是大概方向，其中藏著許多的坑點(diǎn)，諾接下來(lái)我來(lái)帶大家，對(duì)這些易錯(cuò)點(diǎn)進(jìn)行分析。
首先是查詢(xún)到目標(biāo)：
這個(gè)比較簡(jiǎn)單，這里不做解釋。?
//首先尋找到目標(biāo),并且記錄到parent
BST_node* parent = nullptr;
BST_node* cur = root;
while (cur)
{
if (val < cur->_val)
{
parent = cur;
cur = cur->_left;
}
else if (val > cur->_val)
{
parent = cur;
cur = cur->_right;
}
else
{
break;
}
}
if (!cur)
{
return 0;
}易錯(cuò)點(diǎn)分析，包你學(xué)會(huì)
（1.）刪除目標(biāo)，沒(méi)有左右孩子
?
（2.）刪除目標(biāo)，只有一個(gè)孩子
一般的思路：?
?
但，這是有漏洞的！
諾：
（3.）刪除目標(biāo)，有兩個(gè)孩子
?好啦，前菜上完了來(lái)看看，本次的大菜。
代碼
（1.）非遞歸版本?
bool Erase(const T& val)
{
//首先尋找到指定值,并且記錄到parent
BST_node* parent = nullptr;
BST_node* cur = root;
while (cur)
{
if (val < cur->_val)
{
parent = cur;
cur = cur->_left;
}
else if (val > cur->_val)
{
parent = cur;
cur = cur->_right;
}
else
{
break;
}
}
if (!cur)
{
return 0;
}
// 查詢(xún)成功,開(kāi)始刪除
if (!cur->_left && !cur->_right) // cur沒(méi)有左右孩子
{ // 當(dāng)要?jiǎng)h除目標(biāo)是根
if (cur == root)
{
root = nullptr;
delete cur;
}
// 判斷cur是左右孩子
else if (cur->_val < parent->_val)
{
parent->_left = nullptr;
delete cur;
}
else
{
parent->_right = nullptr;
delete cur;
}
return 1;
}
else if (!cur->_left || !cur->_right) // 只有一個(gè)孩子
{
if (!parent) // 判斷是否是目標(biāo)是根
{
root = cur->_left != nullptr ? cur->_left : cur->_right;
delete cur;
}
// 判斷cur為啥孩子
else if (cur->_val < parent->_val) // 左側(cè)
{
parent->_left = cur->_left != nullptr ? cur->_left : cur->_right;
delete cur;
}
else // 右側(cè)
{
parent->_right = cur->_left != nullptr ? cur->_left : cur->_right;
delete cur;
}
}
else // 有2個(gè)孩子
{ // 使用左側(cè)最大的孩子來(lái)領(lǐng)養(yǎng)
// 尋找左側(cè)最大
BST_node* maxnode = cur->_left;
BST_node* max_parent = cur;
while (maxnode->_right)
{
max_parent = maxnode;
maxnode = maxnode->_right;
}
// 現(xiàn)在又進(jìn)入一種特殊情況,1.max_parent就沒(méi)進(jìn)入循環(huán)，2.進(jìn)入了循環(huán)
if (max_parent == cur)
{
max_parent->_left = maxnode->_left;
}
else
{
max_parent->_right = maxnode->_left;
}
// 值轉(zhuǎn)移
cur->_val = maxnode->_val;
delete maxnode;
}
return 1;
}（2.）遞歸版本
bool Re_Erease( const T& val)
{
return Re_Erease_table(root, val);
}
bool Re_Erease_table(BST_node*& node, const T& val)
{
// 首先我們先找到值
if (node == nullptr)
{
return 0; // 如果訪問(wèn)到了空，則說(shuō)明刪除失敗，原因是：不存在
}
if (val < node->_val)
{
return Re_Erease_table(node->_left, val);
}
else if (val > node->_val)
{
return Re_Erease_table(node->_right, val);
}
else
{
// 開(kāi)始刪除目標(biāo)數(shù)據(jù)。方法如下；
// 1. 就按照非遞歸的思路，不用改多少代碼
// 2. 使用遞歸方法，優(yōu)勢(shì)就是代碼簡(jiǎn)潔
// 這里使用方法2
BST_node* del = node; // 保存每次訪問(wèn)的對(duì)象，如果是目標(biāo)，就備份好了
if (node->_left == nullptr)
{
node = node->_right;
}
else if (node->_right == nullptr)
{
node = node->_left;
}
else
{
//處理左右都有孩子的目標(biāo)
// 左側(cè)查找最大值，右側(cè)查找最小值
BST_node* max_node = node->_left;
while (max_node->_right)
{
max_node = max_node->_right;
}
// 完成循環(huán)后，max_node最多有左孩子，然后數(shù)據(jù)交換，我們以目標(biāo)左側(cè)樹(shù)為起點(diǎn)
// 再次遞歸刪除替換數(shù)據(jù)。
swap(max_node->_val, node->_val);
return Re_Erease_table(node->_left, val); //已經(jīng)完成刪除，就直接退出，以免觸發(fā)刪除delete
}
//處理前兩種情況
delete del;
}
}5. 析構(gòu)函數(shù)
思路：
~BSTree()
{
Distroy_Re(root);
root = nullptr;
}
void Distroy_Re(BST_node*& node) // 我們采用遞歸刪除
{
if (node == nullptr)
return ;
// 先處理左右孩子
Distroy_Re(node->_left);
Distroy_Re(node->_right);
delete node;
node = nullptr;
}6.拷貝構(gòu)造?
// 我們實(shí)現(xiàn)了拷貝構(gòu)造，默認(rèn)構(gòu)造函數(shù)則不會(huì)生成
// 解決方案：1.實(shí)現(xiàn)構(gòu)造函數(shù) 2.使用default關(guān)鍵字，強(qiáng)制生成默認(rèn)構(gòu)造
BSTree()
{
}
// BSTree() = default
BSTree(const BSTree& Tree) // 拷貝構(gòu)造
{
root = copy(Tree.root);
}
BST_node* copy(BST_node* root)
{
if (root == nullptr)
return nullptr;
BST_node* new_node = new BST_node(root->_val);
new_node->_left = copy(root->_left);
new_node->_right = copy(root->_right);
return new_node;
}?三，應(yīng)用
1.
K模型：K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲(chǔ)Key即可，關(guān)鍵碼即為需要搜索到
的值。
? ? ?比如：
給一個(gè)單詞word，判斷該單詞是否拼寫(xiě)正確，具體方式如下：以詞庫(kù)中所有單詞集合中的每個(gè)單詞作為key，構(gòu)建一棵二叉搜索樹(shù)在二叉搜索樹(shù)中檢索該單詞是否存在，存在則拼寫(xiě)正確，不存在則拼寫(xiě)錯(cuò)誤。
2.
KV模型：每一個(gè)關(guān)鍵碼key，都有與之對(duì)應(yīng)的值Value，即<Key, Value>的鍵值對(duì)。該種方式在現(xiàn)實(shí)生活中非常常見(jiàn)：
? ? ?比如
英漢詞典就是英文與中文的對(duì)應(yīng)關(guān)系，通過(guò)英文可以快速找到與其對(duì)應(yīng)的中文，英文單詞與其對(duì)應(yīng)的中文<word, chinese>就構(gòu)成一種鍵值對(duì)；
再比如
統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，
單詞與其出現(xiàn)次數(shù)就是<word, count>就構(gòu)成一種鍵值對(duì)（這個(gè)比較簡(jiǎn)單，修改一下即可）
?四，搜索二叉樹(shù)的缺陷及優(yōu)化
對(duì)有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)，若每個(gè)元素查找的概率相等，則二叉搜索樹(shù)平均查找長(zhǎng)度是結(jié)點(diǎn)在二叉搜索樹(shù)的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。
但對(duì)于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹(shù)：
最壞情況：N
平均情況：O(logN)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-728431.html
問(wèn)題：如果退化成單支樹(shù)，二叉搜索樹(shù)的性能就失去了。那能否進(jìn)行改進(jìn)，不論按照什么次序插入關(guān)鍵碼，二叉搜索樹(shù)的性能都能達(dá)到最優(yōu)？那么我們后續(xù)章節(jié)學(xué)習(xí)的AVL樹(shù)和紅黑樹(shù)就可以上場(chǎng)了。
五，代碼匯總
namespace key
{
template <class K>
class BinarySeaTree_node
{
typedef BinarySeaTree_node<K> BST_node;
public:
BinarySeaTree_node(const K& val)
: _val(val)
,_left(nullptr)
,_right(nullptr)
{}
K _val;
BST_node* _left;
BST_node* _right;
};
template <class T>
class BSTree
{
public:
typedef BinarySeaTree_node<T> BST_node;
// 我們實(shí)現(xiàn)了拷貝構(gòu)造，默認(rèn)構(gòu)造函數(shù)則不會(huì)生成
// 解決方案：1.實(shí)現(xiàn)構(gòu)造函數(shù) 2.使用default關(guān)鍵字，強(qiáng)制生成默認(rèn)構(gòu)造
BSTree()
{
}
// BSTree() = default
BSTree(const BSTree& Tree) // 拷貝構(gòu)造
{
root = copy(Tree.root);
}
BSTree<T>& operator=(BSTree<T> t)
{
swap(root, t.root);
return *this;
}
BST_node* copy(BST_node* root)
{
if (root == nullptr)
return nullptr;
BST_node* new_node = new BST_node(root->_val);
new_node->_left = copy(root->_left);
new_node->_right = copy(root->_right);
return new_node;
}
bool Re_Insert(const T& val) { return Re_Insert_table(root, val); }
void Re_Print() { Re_Print_table(root); }
bool Re_Erease(const T& val) { return Re_Erease_table(root, val); }
BST_node* Re_Find(const T& val) { return Re_Find_table(root, val); }
bool Insert(const T& val)
{
BST_node* key = new BST_node(val);
BST_node* cur = root;
BST_node* parent = nullptr;
while (cur)
{
if (key->_val < cur->_val)
{
parent = cur;
cur = cur->_left;
}
else if (key->_val > cur->_val)
{
parent = cur;
cur = cur->_right;
}
else
{
return 0;
}
}
// 查詢(xún)好位置后，建立鏈接
if (!root)
{
root = key;
return 0;
}
if (key->_val > parent->_val)
{
parent->_right = key;
}
else
{
parent->_left = key;
}
return 1;
}
BST_node* Find(const T& val)
{
//直接跟尋找位置一樣
BST_node* parent = nullptr;
BST_node* cur = root; // 以返回cur的方式返回
while (cur) // 非遞歸版本
{
if (val < cur->_val)
{
parent = cur;
cur = cur->_left;
}
else if (val > cur->_val)
{
parent = cur;
cur = cur->_right;
}
else
{
return cur;
}
}
return cur;
}
bool Erase(const T& val)
{
//首先尋找到指定值,并且記錄到parent
BST_node* parent = nullptr;
BST_node* cur = root;
while (cur)
{
if (val < cur->_val)
{
parent = cur;
cur = cur->_left;
}
else if (val > cur->_val)
{
parent = cur;
cur = cur->_right;
}
else
{
break;
}
}
if (!cur)
{
return 0;
}
// 查詢(xún)成功,開(kāi)始刪除
if (!cur->_left && !cur->_right) // cur沒(méi)有左右孩子
{ // 當(dāng)要?jiǎng)h除目標(biāo)是根
if (cur == root)
{
root = nullptr;
delete cur;
}
// 判斷cur是左右孩子
else if (cur->_val < parent->_val)
{
parent->_left = nullptr;
delete cur;
}
else
{
parent->_right = nullptr;
delete cur;
}
return 1;
}
else if (!cur->_left || !cur->_right) // 只有一個(gè)孩子
{
if (!parent) // 判斷是否是目標(biāo)是根
{
root = cur->_left != nullptr ? cur->_left : cur->_right;
delete cur;
}
// 判斷cur為啥孩子
else if (cur->_val < parent->_val) // 左側(cè)
{
parent->_left = cur->_left != nullptr ? cur->_left : cur->_right;
delete cur;
}
else // 右側(cè)
{
parent->_right = cur->_left != nullptr ? cur->_left : cur->_right;
delete cur;
}
}
else // 有2個(gè)孩子
{ // 使用左側(cè)最大的孩子來(lái)領(lǐng)養(yǎng)
// 尋找左側(cè)最大
BST_node* maxnode = cur->_left;
BST_node* max_parent = cur;
while (maxnode->_right)
{
max_parent = maxnode;
maxnode = maxnode->_right;
}
// 現(xiàn)在又進(jìn)入一種特殊情況,1.max_parent就沒(méi)進(jìn)入循環(huán)，2.進(jìn)入了循環(huán)
if (max_parent == cur)
{
max_parent->_left = maxnode->_left;
}
else
{
max_parent->_right = maxnode->_left;
}
// 值轉(zhuǎn)移
cur->_val = maxnode->_val;
delete maxnode;
}
return 1;
}
~BSTree()
{
Distroy_Re(root);
root = nullptr;
}
protected:
bool Re_Insert_table(BST_node*& node, const T& val)
{
if (node == nullptr)
{
node = new BST_node(val);
return 1;
}
if (val < node->_val)
{
return Re_Insert_table(node->_left, val);
}
else if (val > node->_val)
{
return Re_Insert_table(node->_right, val);
}
else
{
return 0;
}
}
void Re_Print_table(const BST_node* node)
{
if (node == nullptr)
return;
Re_Print_table(node->_left);
cout << node->_val << " ";
Re_Print_table(node->_right);
}
BST_node* Re_Find_table(BST_node* node, const T& val)
{
if (node == nullptr)
return nullptr;
if (val < node->_val)
{
return Re_Find_table(node->_left, val);
}
else if (val > node->_val)
{
return Re_Find_table(node->_right, val);
}
else
{
return node;
}
}
bool Re_Erease_table(BST_node*& node, const T& val)
{
// 首先我們先找到值
if (node == nullptr)
{
return 0; // 如果訪問(wèn)到了空，則說(shuō)明刪除失敗，原因是：不存在
}
if (val < node->_val)
{
return Re_Erease_table(node->_left, val);
}
else if (val > node->_val)
{
return Re_Erease_table(node->_right, val);
}
else
{
// 開(kāi)始刪除目標(biāo)數(shù)據(jù)。方法如下；
// 1. 就按照非遞歸的思路，不用改多少代碼
// 2. 使用遞歸方法，優(yōu)勢(shì)就是代碼簡(jiǎn)潔
// 這里使用方法2
BST_node* del = node; // 保存每次訪問(wèn)的對(duì)象，如果是目標(biāo)，就備份好了
if (node->_left == nullptr)
{
node = node->_right;
}
else if (node->_right == nullptr)
{
node = node->_left;
}
else
{
//處理左右都有孩子的目標(biāo)
// 左側(cè)查找最大值，右側(cè)查找最小值
BST_node* max_node = node->_left;
while (max_node->_right)
{
max_node = max_node->_right;
}
// 完成循環(huán)后，max_node最多有左孩子，然后數(shù)據(jù)交換，我們以目標(biāo)左側(cè)樹(shù)為起點(diǎn)
// 再次遞歸刪除替換數(shù)據(jù)。
swap(max_node->_val, node->_val);
return Re_Erease_table(node->_left, val); //已經(jīng)完成刪除，就直接退出，以免觸發(fā)刪除delete
}
// 查找到刪除數(shù)據(jù)
delete del;
}
}
void Distroy_Re(BST_node*& node) // 我們采用遞歸刪除
{
if (node == nullptr)
return;
// 先處理左右孩子
Distroy_Re(node->_left);
Distroy_Re(node->_right);
delete node;
node = nullptr;
}
private:
BST_node* root = nullptr;
};
}結(jié)語(yǔ)
? ?本小節(jié)就到這里了，感謝小伙伴的瀏覽，如果有什么建議，歡迎在評(píng)論區(qū)評(píng)論，如果給小伙伴帶來(lái)一些收獲請(qǐng)留下你的小贊，你的點(diǎn)贊和關(guān)注將會(huì)成為博主創(chuàng)作的動(dòng)力文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-728431.html
到了這里，關(guān)于【C++】搜索二叉樹(shù)底層實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
