二叉搜索樹是一顆排序樹,或者是一顆空樹如圖:
若它的左子樹不為空,則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
若它的右子樹不為空,則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
它的左右子樹也分別為二叉搜索樹,并且它可以去重
templatestruct BSTreeNode
{BSTreeNode* _left;
BSTreeNode* _right;
T _key;
BSTreeNode(const T& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
templateclass BSTree
{typedef BSTreeNodeNode;
public:
BSTree()
:_root(nullptr)
{}
private:
Node* _root;
};
二叉搜索樹的插入例如插入6和10
bool insert(const T& key)
{if (_root == nullptr)
{_root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = cur;
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);
if (parent->_key >key)
parent->_left = cur;
else
parent->_right = cur;
return true;
}
注意:會有樹為空的情況需要判斷
二叉搜索樹的查找查找的代碼和插入非常類似,大于根去右邊,小于根去左邊,最多查找高度次
代碼如下:
//Node* find(const T& key)
bool find(const T& key)
{if (_root == nullptr)
return false;
//return nullptr;
Node* cur = _root;
while (cur)
{if (cur->_key >key)
cur = cur->_left;
else if (cur->_key< key)
cur = cur->_right;
else
return true;
//return cur;
}
return false;
//return nullptr;
}
二叉搜索樹的刪除這里的刪除相對于插入和查找來說是比較難的,最重要的是不能改變二叉搜索樹的結(jié)構(gòu),所以這里主要分為兩種情況考慮
先找到要刪除的節(jié)點(diǎn),代碼如下:
bool erase(const T& key)
{if (_root == nullptr)
return false;
Node* cur = _root;
Node* parent = cur;
while (cur)
{if (cur->_key >key)
{ parent = cur;
cur = cur->_left;
}
else if (cur->_key< key)
{ parent = cur;
cur = cur->_right;
}
else
{ 刪除部分的代碼........
}
}
return false;
}
1. 刪除只有一個子節(jié)點(diǎn)或沒有子節(jié)點(diǎn)
(1)刪除葉子節(jié)點(diǎn)(刪除9舉例)
(2)刪除只存在一個子節(jié)點(diǎn)的節(jié)點(diǎn)(刪除8舉例)
情況1的刪除代碼:
else
{if (cur->_left == nullptr)
{if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
else if (cur->_right == nullptr)
{if (cur == parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
else
{情況2部分的代碼.......}
delete cur;
}
除上述代碼刪除的示例外,另外三種情況
所以這里需要仔細(xì)處理鏈接,否則會破壞搜索樹的結(jié)構(gòu)
2.刪除左右節(jié)點(diǎn)都存在的節(jié)點(diǎn)
(1)刪除根節(jié)點(diǎn)
(2)刪除其他存在左右子節(jié)點(diǎn)的節(jié)點(diǎn)
找到的右子樹最小節(jié)點(diǎn)一定沒有左節(jié)點(diǎn),且它的父節(jié)點(diǎn)一定不為空;所以在交換或覆蓋完數(shù)值后,剩下的步驟和情況一一樣,并且這里不用單獨(dú)判斷刪除的節(jié)點(diǎn)存在哪邊的子節(jié)點(diǎn)(右子樹的最小節(jié)點(diǎn)一定沒有左節(jié)點(diǎn),所以只可能存在右節(jié)點(diǎn))
情況2的刪除代碼:
else
{Node* min_parent = cur;
Node* min = cur->_right;
while (min->_left)
{min_parent = min;
min = min->_left;
}
cur->_key = min->_key;
if (min == min_parent->_left)
min_parent->_left = min->_right;
else
min_parent->_right = min->_right;
swap(min,cur);
}
以上就是刪除主要步驟,但還有個問題就是要考慮只有一個節(jié)點(diǎn),需要操作根節(jié)點(diǎn)。
if (_root->_key == key )
{if (_root->_left == nullptr)
_root = _root->_right;
else
_root = _root->_left;
}
總體代碼
bool erase(const T& key)
{if (_root == nullptr)
return false;
Node* cur = _root;
Node* parent = cur;
while (cur)
{if (cur->_key >key)
{ parent = cur;
cur = cur->_left;
}
else if (cur->_key< key)
{ parent = cur;
cur = cur->_right;
}
else
{ if (_root->_key == key )
{ if (_root->_left == nullptr)
_root = _root->_right;
else
_root = _root->_left;
}
else if (cur->_left == nullptr)
{ if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
else if (cur->_right == nullptr)
{ if (cur == parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
else
{ Node* min_parent = cur;
Node* min = cur->_right;
while (min->_left)
{min_parent = min;
min = min->_left;
}
cur->_key = min->_key;
if (min == min_parent->_left)
min_parent->_left = min->_right;
else
min_parent->_right = min->_right;
swap(min,cur);
}
delete cur;
return true;
}
}
return false;
}
整體代碼
循環(huán)寫法bool insert(const T& key)
{if (_root == nullptr)
{ _root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = cur;
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);
if (parent->_key >key)
parent->_left = cur;
else
parent->_right = cur;
return true;
}
bool find(const T& key)
{if (_root == nullptr)
return false;
//return nullptr;
Node* cur = _root;
while (cur)
{ if (cur->_key >key)
cur = cur->_left;
else if (cur->_key< key)
cur = cur->_right;
else
return true;
//return cur;
}
return false;
//return nullptr;
}
bool erase(const T& key)
{if (_root == nullptr)
return false;
Node* cur = _root;
Node* parent = cur;
while (cur)
{ if (cur->_key >key)
{ parent = cur;
cur = cur->_left;
}
else if (cur->_key< key)
{ parent = cur;
cur = cur->_right;
}
else
{ if (_root->_key == key )
{if (_root->_left == nullptr)
_root = _root->_right;
else
_root = _root->_left;
}
else if (cur->_left == nullptr)
{if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
else if (cur->_right == nullptr)
{if (cur == parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
else
{Node* min_parent = cur;
Node* min = cur->_right;
while (min->_left)
{min_parent = min;
min = min->_left;
}
cur->_key = min->_key;
if (min == min_parent->_left)
min_parent->_left = min->_right;
else
min_parent->_right = min->_right;
swap(min,cur);
}
delete cur;
return true;
}
}
return false;
}
//打印搜索樹
void print_BSTree()
{_print_BSTree(_root);
cout<< endl;
}
void _print_BSTree(Node* root)
{if (root == nullptr)
return;
_print_BSTree(root->_left);
cout<< root->_key<< " ";
_print_BSTree(root->_right);
}
遞歸寫法1.插入
bool insertR(const T& key)
{return insertR(_root,key)
}
bool _insertR(Node*& root,const T& key)
{if(root == nullptrd)
{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;
}
注意,這里可以成功鏈接上,主要是運(yùn)用了引用,遞的是左右指針的引用
2.查找
Node* findR(const T& key)
{if()
}
bool _insertR(Node*& root, const T& 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;
}
3.刪除
bool EarseR(const K& key)
{return EarseR(_root,key);
}
bool _EraseR(Node*& root, const T& key)
{if (root == nullptr)
return false;
if (root->_key >key)
_EraseR(root->_left, key);
else if (root->_key< key)
_EraseR(root->_right, key);
else
{Node* era = root;
if (root->_left == nullptr)
root = root->_right;
else if (root->_right == nullptr)
root = root->_left;
else
{ Node* min = root->_right;
Node* min_parent = root;
while (min->_left)
{ min_parent = min;
min = min->_left;
}
swap(min->_key, root->_key);
return _EraseR(root->_right, key);
}
delete era;
return true;
}
}
這里講一下刪除的思路:
情況一時,操作和遞歸的插入基本一樣,通過使用引用就可直接令要刪除節(jié)點(diǎn)的父節(jié)點(diǎn)與子節(jié)點(diǎn)直接相連,也不用再去判斷刪除節(jié)點(diǎn)是父節(jié)點(diǎn)的左邊還是右邊
情況二時,先找到右子樹最小節(jié)點(diǎn),再與要刪除的節(jié)點(diǎn)交換數(shù)值,最后遞歸傳遞的節(jié)點(diǎn)是,要刪除節(jié)點(diǎn)的左子樹(情況二再交換完數(shù)值后就可以按照情況一去處理了)
注意:要提前記錄一下找到的要刪除的節(jié)點(diǎn),中間過程會改變root的值,所以最后刪除的是提前記錄好的節(jié)點(diǎn)
總體代碼
bool insertR(const T& key)
{return _insertR(_root,key);
}
Node* findR(const T& key)
{return _findR(_root,key);
}
bool EraseR(const T& key)
{return _EraseR(_root, key);
}
private:
bool _insertR(Node*& root, const T& 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;
}
Node* _findR(Node* root, const T& 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 _EraseR(Node*& root, const T& key)
{if (root == nullptr)
return false;
if (root->_key >key)
_EraseR(root->_left, key);
else if (root->_key< key)
_EraseR(root->_right, key);
else
{ Node* era = root;
if (root->_left == nullptr)
root = root->_right;
else if (root->_right == nullptr)
root = root->_left;
else
{ Node* min = root->_right;
Node* min_parent = root;
while (min->_left)
{min_parent = min;
min = min->_left;
}
swap(min->_key, root->_key);
return _EraseR(root->_right, key);
}
delete era;
return true;
}
}
二叉搜索樹的應(yīng)用c++提供了這種鍵值對兒的結(jié)構(gòu),叫做pair
pairp1("one",1);
p1.first就是key
p1.second就是value
make_pair("one",p1); 可以構(gòu)造一個pair
二叉搜索樹的性能分析插入和刪除操作都必須先查找,查找效率代表了二叉搜索樹中各個操作的性能。
但是會有極端情況:當(dāng)插入的值順著一個方向一直插入(即插入的值一直是最小或大或者接近這種情況),那么二叉樹就變成了單樹,這時的查找效率就是極低了,即結(jié)點(diǎn)越深,則比較次數(shù)越多。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級服務(wù)器適合批量采購,新人活動首月15元起,快前往官網(wǎng)查看詳情吧
網(wǎng)頁名稱:C++初階學(xué)習(xí)————二叉樹進(jìn)階(二叉搜索樹)-創(chuàng)新互聯(lián)
網(wǎng)頁地址:http://muchs.cn/article46/ddjgeg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供網(wǎng)站建設(shè)、網(wǎng)站維護(hù)、虛擬主機(jī)、App設(shè)計、服務(wù)器托管、網(wǎng)站收錄
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容