網站首頁 編程語言 正文
零.前言
了解搜索二叉樹是為了STL中的map和set做鋪墊，我們所熟知的AVL樹和平衡搜索二叉樹也需要搜索二叉樹的基礎，本文就來建立一棵搜索二叉樹。
1.概念
搜索二叉樹又稱為二叉排序樹，它或者是一棵空樹，或者具有如下性質：
1.若其左子樹不為空，則左子樹上所有節點的值都小于根節點的值。
2.若其右子樹不為空，則右子樹上所有節點的值都大于根節點的值。
3.它的左右子樹也分別為二叉搜索樹。
2.作用
1.搜索：通過搜索二叉樹的性質來進行搜索。
2.排序：二叉搜索樹的中序遍歷就是將所有數據進行排序。
3.迭代實現
(1)查找
對二叉搜索樹的節點進行查找：
1.定義查找節點指針cur
2.比較cur->_k與要查找的節點k的值的大小關系，當_k<k的時候，cur指向該節點的右子樹，否則指向左子樹。
3.查找成功返回true，失敗返回false
bool Find(const K& k)
{
Node* cur = _root;//1.
while (cur)//2.
{
if (cur->_k < k)
{
cur = cur->_right;
}
else if (cur->_k > k)
{
cur = cur->_left;
}
else
{
return true;//3
}
}
return false;//3
}
(2)插入
1.判斷根節點指針是否為空。如果為空則直接將該節點插入根節點位置。
2.定義遍歷節點cur與其父節點parent。
3.依次判斷插入節點的k與當前節點cur的大小決定cur指向當前節點的左或者右節點。并在改變cur指向之前將parent賦值為cur。
如果二叉搜索樹中已經有該值，則返回false。
4.當cur為空的時候，建立根據k在cur處建立節點。比較parent的_k與k的大小，判斷cur建立在parent的左子樹還是右子樹。并返回true。
bool InsertNode(const K& k)
{
if (_root == nullptr)
{
_root = new Node(k);
return true;
}//1
Node* cur = _root;
Node* parent = nullptr;//2
while (cur)
{
if (cur->_k < k)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_k > k)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}//3
cur = new Node(k);
if (parent->_k < k)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;//4
}
(3)刪除
1.首先通過cur和parent查找該節點。
2.如果cur左為空，判斷cur相對于parent的位置，并將cur的右子樹賦值到cur相對于parent的位置處。并刪除cur。
3.如果cur右為空，判斷cur相對于parent的位置，并將cur的左子樹賦值到cur相對于parent的位置處。并刪除cur。
4.如果cur的左右都不為空：
(1)建立一個新的節點指針min賦值為cur->right作為遍歷指針，和其父節點指針minparent賦值為cur。
(2)一直向左遍歷直到min->left為空。并交換min與cur的_key。
(3)判斷min與minparent的位置關系，并將min的右子樹放在該處。
(4)刪除min，返回true。若沒找到返回false。
bool Erase(const K& k)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_k < k)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_k > k)
{
parent = cur;
cur = cur->_left;
}//1
else
{
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
return true;
}//2
else
{
Node* min = cur->_right;
Node* minparent = cur;//4.(1)
while(min->_left)
{
minparent = min;
min = min->_left;
}//4.(2)
cur->_k = min->_k;
if (minparent->_left == min)
{
minparent->_left = min->_right;
}
else
{
minparent->_right = min->_right;
}//4.(3)
delete min;
return true;
}
}
}
return false;//4.(4)
}
4.遞歸實現
(1)查找
1.判空
2.判斷root->_k與k的大小，判斷遞歸的方向。
3.如果找到了返回root節點。
Node* _FindR(const K& k)
{
return FindR(_root, k);
}//1
Node* FindR(Node* root, const K& k)
{
if (root == nullptr)
{
return nullptr;
}
if (root->_k > k)
{
return FindR(root->_left, k);
}
else if (root->_k < k)
{
return FindR(root->_right, k);
}//2
else
{
return root;
}//3
}
(2)插入
1.判斷節點是否為空，如果為空將該節點插入節點的位置。并返回true
2.判斷_k和k的大小，判斷遞歸的方向。
3.如果節點值等于k返回false。
bool InsertR(const K& k)
{
return _InsertR(_root, k);
}
bool _InsertR(Node*& root, const K& k)
{
if (root == nullptr)
{
root = new Node(k);
return true;
}//1
if (root->_k < k)
{
return _InsertR(root->_right, k);
}
else if (root->_k > k)
{
return _InsertR(root->_left, k);
}//2
else
{
return false;
}//3
}
(3)刪除
1.如果節點為空則返回false
2.通過_k和k的大小來判斷遞歸方向。
3.找到該節點：
(1)定義del指針賦值為root。
(2)如果root左子樹為空，則將root指向該節點的右子樹。
(3)如果root右子樹為空，則將root指向該節點的左子樹。
(4)如果root左右子樹都不為空，將min賦值為root->right，并依次向左找，直到min->left為空。并交換min的k與root的k。 然后遞歸到右子樹來進行刪除。
(5)刪除原root節點(del)，并返回true。
bool EraseR(const K& k)
{
return _EraseR(_root, k);
}
bool _EraseR(Node*& root, const K& k)
{
if (root == nullptr)
return false;//1
if (root->_k < k)
{
return _EraseR(root->_right, k);
}
else if (root->_k > k)
{
return _EraseR(root->_left, k);
}//2
else
{
Node* del = root;//3.(1)
if (root->_left == nullptr)
{
root = root->_right;
}//3.(2)
else if (root->_right == nullptr)
{
root = root->_left;
}//3.(3)
else
{
Node* min = root->_right;
while (min->_left)
{
min = min->_left;
}
swap(min->_k, root->_k);
// 遞歸到右子樹去刪除
return _EraseR(root->_right, k);//3.(4)
}
delete del;
return true;//3.(5)
}
}
5.key/value模型的應用
key/value模型，即在原來k的基礎上，每個節點再帶有一個value值。有兩種主要的應用：
(1)對應查找
利用到了二叉搜索樹搜素的性質。
BSTree<string, string> word;
word.InsertNode("man", "男人");
word.InsertNode("woman", "女人");
word.InsertNode("sort", "排序");
word.InsertNode("Earth", "地球");
word.InsertNode("birth", "出生");
word.InsertNode("die", "死亡");
string str;
while (cin >> str)
{
BSTreeNode<string, string>* ret = word.Find(str);
if (ret)
{
cout << "對應的中文解釋：" << ret->_v << endl;
}
else
{
cout << "無此單詞" << endl;
}
}
我們向二叉搜索樹中存入英文單詞和中文釋義，將英文單詞作為k來構建二叉搜索樹，如果搜索到了則打印中文釋義，這樣就簡單構成了一個字典。
(2)判斷出現次數
當我們判斷一個數組中各個元素出現的次數的時候，也可以使用到二叉搜索樹。
string arr[] = { "a","b","e","e","b","a","n","a","n","a","c","p","d","d","x","s","w","l" };
BSTree<string, int> counttree;
for (auto& str : arr)
{
auto ret = counttree.Find(str);
if (ret != nullptr)
{
(ret->_v)++;
}
else
{
counttree.InsertNode(str, 1);
}
}
counttree._InOrderv();
每一次出現一個元素我們就將它插入二叉搜索樹中，并把它的value賦值為1，當第二次遇到這個元素的時候，在二叉搜索樹中搜索該元素，人如果可以找到該元素則將該元素的value的值++。最終統計出各個元素出現的次數。
6.總結
對于二叉搜索樹的理解對以后學習AVL樹和紅黑樹具有很大的幫助
原文鏈接：https://blog.csdn.net/qq_51492202/article/details/124760051
相關推薦
- 2021-12-09 Linux內存管理和尋址詳細介紹_Linux
- 2022-07-25 C++細講深淺拷貝與初始化列表如何操作_C 語言
- 2022-09-22 matplotlib自定義風格
- 2022-08-02 Python+Selenium實現瀏覽器標簽頁的切換_python
- 2022-07-18 Liunx下使用SSH登錄遠程服務器
- 2022-03-26 Flutter構建自定義Widgets的全過程記錄_Android
- 2022-06-10 nginx.conf配置文件結構小結_nginx
- 2023-03-28 Unity3D開發之獲取所有的子對象的方法詳解_C#教程
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速