柚子快報(bào)邀請(qǐng)碼778899分享：【C++】搜索二叉樹
柚子快報(bào)邀請(qǐng)碼778899分享：【C++】搜索二叉樹
1. 二叉搜索樹
a. 二叉搜索樹的概念
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹:
若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值它的左右子樹也分別為二叉搜索樹它的中序遍歷是得到的結(jié)果是升序
b. 二叉搜索樹的實(shí)現(xiàn)
1. 搜索二叉樹的構(gòu)建
代碼
template
struct BinNode
{
BinNode(K key)
:_key(key)
{}
K _key;
BinNode* left = nullptr;
BinNode* right = nullptr;
};
template
class BinNodeTree
{
public:
typedef BinNode
private:
node* _root = nullptr;
};
2. 二叉樹的插入?
循環(huán)實(shí)現(xiàn)思路
返回類型是 bool ，判斷能否插入傳入的值（二叉搜索樹不存相同的值）
跟節(jié)點(diǎn)比較，如果 插入的值 key > 節(jié)點(diǎn)的值，則走節(jié)點(diǎn)的右子樹 ; 如果插入的值 key < 節(jié)點(diǎn)的值，則走左子樹 ; 如果等于，返回 false ;如果結(jié)點(diǎn)為空 ，結(jié)束循環(huán) ，new 一個(gè)新的結(jié)點(diǎn)，需要空節(jié)點(diǎn)的父節(jié)點(diǎn)去鏈接新結(jié)點(diǎn)，所以我們一定要定義一個(gè)父節(jié)點(diǎn)
注意：
由于不知道新結(jié)點(diǎn)應(yīng)該是父節(jié)點(diǎn)的左子樹還是右子樹，這里鏈接就需要判斷一下，如果空結(jié)點(diǎn)是父結(jié)點(diǎn)的左子樹，那么就鏈接左邊，反之亦然一開始的根節(jié)點(diǎn)為空，所以這里需要特殊處理一下，讓根節(jié)點(diǎn)成為插入的第一個(gè)值構(gòu)造的新節(jié)點(diǎn)
代碼
bool insert(const K &key)
{
if (_root == nullptr)
{
_root = new node(key);
return true;
}
node* prev = _root;
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
prev = cur;
cur = cur->right;
}
else if (key < cur->_key)
{
prev = cur;
cur = cur->left;
}
else
{
return false;
}
}
cur = new node(key);
if (key > prev->_key)
{
prev->right = cur;
}
else
{
prev->left = cur;
}
return true;
}
?遞歸實(shí)現(xiàn)思路
大體思路和循環(huán)的思路差不多，但是略有不同
由于遞歸函數(shù)一定需要結(jié)點(diǎn)的地址（可以走左右子樹）和 需要插入的值，給這個(gè)遞歸函數(shù)傳入的結(jié)點(diǎn)的地址一定是根節(jié)點(diǎn)，但是根節(jié)點(diǎn)在類里面不能訪問，所以這里我們就弄一層包裝，一個(gè)函數(shù)是傳根節(jié)點(diǎn)的地址的，另一個(gè)函數(shù)用來遞歸實(shí)現(xiàn)（都在類里面）這里我們同樣需要判斷插入的值 key 和 結(jié)點(diǎn)的值的關(guān)系，但是這里可以不需要父節(jié)點(diǎn)，我們?cè)谶f歸函數(shù)的形參上面跟之前有所不同，這里的形參用了引用，使得可以直接讓空結(jié)點(diǎn)存新結(jié)點(diǎn)的地址
代碼
bool Insert(const K& key)
{
return _Insert(_root, key);
}
bool _Insert(node*& root, const K& key)
{
if (root == nullptr)
{
root = new node(key);
return true;
}
if (key == root->_key)
{
return false;
}
else if (key > root->_key)
{
_Insert(root->right, key);
}
else
{
_Insert(root->left, key);
}
}
? ?3. 二叉樹的查找
循環(huán)實(shí)現(xiàn)思路
跟節(jié)點(diǎn)比較，如果 插入的值 key > 節(jié)點(diǎn)的值，則走節(jié)點(diǎn)的右子樹 ; 如果插入的值 key < 節(jié)點(diǎn)的值，則走左子樹 ; 如果結(jié)點(diǎn)為空 return false；
代碼
bool find(const K& key)
{
node* cur = _root;
if (cur == nullptr)
{
return false;
}
while (cur)
{
if (key > cur->_key)
{
cur = cur->right;
}
else if(key < cur->_key)
{
cur = cur->left;
}
else
{
return true;
}
}
return false;
}
?
遞歸實(shí)現(xiàn)思路
和插入的遞歸思路有一點(diǎn)相同，都要封裝一層
剩下的思路和循環(huán)是一樣的
代碼
bool Find(const K& key)
{
return _Find(_root, key);
}
bool _Find(node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (key == root->_key)
{
return true;
}
else if (key > root->_key)
{
_Find(root->right, key);
}
else
{
_Find(root->left, key);
}
}
4. 二叉樹的刪除
循環(huán)實(shí)現(xiàn)思路
大體上遇到的情況分三種情況：
刪除的結(jié)點(diǎn)左右子樹為空刪除的結(jié)點(diǎn)左子樹或者右子樹為空刪除的結(jié)點(diǎn)左右子樹都不為空
第一種情況：
實(shí)際上，第一種情況的操作可以歸到第二種里面
第二種情況：
如果刪除的結(jié)點(diǎn)左子樹為空，那么我們需要這個(gè)結(jié)點(diǎn)的 父節(jié)點(diǎn)的左子樹或者右子樹（根據(jù)刪除結(jié)點(diǎn)是父節(jié)點(diǎn)的左子樹還是右子樹進(jìn)行判斷） 是刪除結(jié)點(diǎn)的右子樹
如果刪除結(jié)點(diǎn)是父節(jié)點(diǎn)的左子樹，那么父節(jié)點(diǎn)左邊鏈接，反之則相反
如圖：
如果刪除的結(jié)點(diǎn)右子樹為空，那么我們需要這個(gè)結(jié)點(diǎn)的 父節(jié)點(diǎn)的 左子樹或者右子樹 （根據(jù)刪除結(jié)點(diǎn)是父節(jié)點(diǎn)的左子樹還是右子樹進(jìn)行判斷）是刪除結(jié)點(diǎn)的左子樹
如果刪除結(jié)點(diǎn)是父節(jié)點(diǎn)的左子樹，那么父節(jié)點(diǎn)左邊鏈接，反之則相反
如圖：
前者我們說了，如果刪除節(jié)點(diǎn)兩邊都為空，則也歸到第二種，此時(shí)只要判斷刪除節(jié)點(diǎn)是父節(jié)點(diǎn)的左子樹還是右子樹就好了，無需管鏈接刪除節(jié)點(diǎn)的左子樹還是右子樹
如圖：
?
第三種情況：
由于兩邊都不為空，我們不好直接刪除，這時(shí)候，我們需要把刪除節(jié)點(diǎn)當(dāng)根節(jié)點(diǎn)（同樣構(gòu)成搜索二叉樹），找這個(gè)搜索二叉樹的某個(gè)節(jié)點(diǎn)的值，既可以比左邊節(jié)點(diǎn)的值大（除根節(jié)點(diǎn)外），也可以比右邊節(jié)點(diǎn)的值小，有兩個(gè)答案：這個(gè)搜索二叉樹的左子樹的最大值和右子樹的最小值
如圖：
如何找右子樹的最小值呢？先得到右子樹的地址，再一直往左走，直到節(jié)點(diǎn)為空，則它的父節(jié)點(diǎn)就是我們要找的，所以我們需要定義一個(gè)父節(jié)點(diǎn)，讓刪除節(jié)點(diǎn)存父節(jié)點(diǎn)的值，由于父節(jié)點(diǎn)的左子樹為空，那么刪除節(jié)點(diǎn)要鏈接父節(jié)點(diǎn)的右子樹，跟之前第二種情況一樣，要知道父節(jié)點(diǎn)是上一個(gè)父節(jié)點(diǎn)的左子樹還是右子樹（避免刪除節(jié)點(diǎn)就是根節(jié)點(diǎn)的情況導(dǎo)致的錯(cuò)誤），再刪除父節(jié)點(diǎn)
找左子樹的最大值相同道理
注意事項(xiàng)：
第二種情況有特例，可能刪除的是根節(jié)點(diǎn)，并且左子樹或者右子樹為空
如果左子樹為空，這個(gè)時(shí)候我們只需要直接讓根節(jié)點(diǎn)存右子樹的地址，釋放原來的節(jié)點(diǎn)
反之則相反（如果同樣為左右子樹都為空，同樣適用）
如圖：
第三種情況一定要注意本來定義的兩個(gè)指針(一前一后)，最開始初始化時(shí)，都指向刪除節(jié)點(diǎn)的地址，不要其中一個(gè)置空（防止刪除的節(jié)點(diǎn)是父節(jié)點(diǎn)，而導(dǎo)致置空節(jié)點(diǎn)不能進(jìn)入循環(huán)發(fā)生的一系列錯(cuò)誤）
代碼
bool erase(const K &key)
{
node* parent = _root;
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->left;
}
else
{
if (cur->left == nullptr)
{
if (cur == _root)
{
_root = cur->right;
}
if (parent->left == cur)
{
parent->left = cur->right;
}
else
{
parent->right = cur->right;
}
delete cur;
}
else if (cur->right == nullptr)
{
if (cur == _root)
{
_root = cur->left;
}
if (parent->left == cur)
{
parent->left = cur->left;
}
else
{
parent->right = cur->left;
}
delete cur;
}
else
{
node* MinRight = cur->right;
node* pMinRight = cur;
while (MinRight->left)
{
pMinRight = MinRight;
MinRight = MinRight->left;
}
cur->_key = MinRight->_key;
if (pMinRight->left == MinRight)
{
pMinRight->left = MinRight->right;
}
else
{
pMinRight->right = MinRight->right;
}
delete MinRight;
}
return true;
}
}
return false;
}
?遞歸實(shí)現(xiàn)思路
和插入的遞歸思路有些一樣，都需要包裝，都需要傳指針的引用
第一種情況和第二種情況和循環(huán)思路很像，由于是引用，這里我們不需要判斷是左子樹還是右子樹，直接賦值即可
第三種情況前面還是一樣，找到左子樹的最大值或者右子樹的最小值
如果找左子樹的最大值：
最大值我們可以在通過循環(huán)來找，找到之后，可以選擇交換刪除節(jié)點(diǎn)的值和最大值，再次進(jìn)行遞歸，刪除的值key不變
或者是只讓刪除節(jié)點(diǎn)的值換成最大值，其它不變，遞歸時(shí)，傳的根節(jié)點(diǎn)就是刪除節(jié)點(diǎn)的左子樹，刪除的值key就是最大值
注意：
第三種情況遞歸時(shí)，不可以直接傳存最大值的節(jié)點(diǎn)（那個(gè)最大值節(jié)點(diǎn)是局部變量，而引用接收局部變量會(huì)出很大問題）
代碼
bool Erase(const K& key)
{
return _Erase(_root,key);
}
bool _Erase(node*& root,const K& key)
{
if (root == nullptr)
{
return false;
}
if (key > root->_key)
{
_Erase(root->right, key);
}
else if(key < root->_key)
{
_Erase(root->left, key);
}
else
{
node* cur = root;
if (root->left == nullptr)
{
root = root->right;
delete cur;
}
else if (root->right == nullptr)
{
root = root->left;
delete cur;
}
else
{
cur = cur->left;
while (cur->right)
{
cur = cur->right;
}
int k = root->_key = cur->_key;
_Erase(root->left, k);
}
return true;
}
}
5.? 二叉樹的銷毀
代碼
~BinNodeTree()
{
_BinNodeTree(_root);
}
void _BinNodeTree(node* root)
{
if (root == nullptr)
{
return;
}
_BinNodeTree(root->left);
_BinNodeTree(root->right);
delete root;
}
后序遍歷即可?
6.? 二叉樹的拷貝構(gòu)造
代碼
BinNodeTree(const BinNodeTree
{
_root = copy(t._root,_root);
}
node* copy(node* t1, node* t2)
{
if (t1 == nullptr)
{
return nullptr;
}
t2 = new node(t1->_key);
t2->left = copy(t1->left, t2->left);
t2->right = copy(t1->right, t2->right);
return t2;
}
2. 二叉搜索樹的應(yīng)用
K模型：K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲(chǔ)Key即可，關(guān)鍵碼即為需要搜索到
的值
如：查找一個(gè)單詞是否拼寫正確
? ? 2. KV模型：每一個(gè)關(guān)鍵碼key，都有與之對(duì)應(yīng)的值Value，即
式在現(xiàn)實(shí)生活中非常常見
如：?jiǎn)卧~中英文查找 ， 統(tǒng)計(jì)單詞出現(xiàn)次數(shù)
柚子快報(bào)邀請(qǐng)碼778899分享：【C++】搜索二叉樹
相關(guān)鏈接
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Kaufland歐洲優(yōu)選貿(mào)
