C++數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹(shù)的實(shí)現(xiàn)
零.前言
了解搜索二叉樹(shù)是為了STL中的map和set做鋪墊，我們所熟知的AVL樹(shù)和平衡搜索二叉樹(shù)也需要搜索二叉樹(shù)的基礎(chǔ)，本文就來(lái)建立一棵搜索二叉樹(shù)。
1.概念
搜索二叉樹(shù)又稱為二叉排序樹(shù)，它或者是一棵空樹(shù)，或者具有如下性質(zhì)：
1.若其左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值。
2.若其右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值。
3.它的左右子樹(shù)也分別為二叉搜索樹(shù)。
2.作用
1.搜索：通過(guò)搜索二叉樹(shù)的性質(zhì)來(lái)進(jìn)行搜索。
2.排序：二叉搜索樹(shù)的中序遍歷就是將所有數(shù)據(jù)進(jìn)行排序。
3.迭代實(shí)現(xiàn)
(1)查找
對(duì)二叉搜索樹(shù)的節(jié)點(diǎn)進(jìn)行查找：
1.定義查找節(jié)點(diǎn)指針cur
2.比較cur->_k與要查找的節(jié)點(diǎn)k的值的大小關(guān)系，當(dāng)_k<k的時(shí)候，cur指向該節(jié)點(diǎn)的右子樹(shù)，否則指向左子樹(shù)。
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.判斷根節(jié)點(diǎn)指針是否為空。如果為空則直接將該節(jié)點(diǎn)插入根節(jié)點(diǎn)位置。
2.定義遍歷節(jié)點(diǎn)cur與其父節(jié)點(diǎn)parent。
3.依次判斷插入節(jié)點(diǎn)的k與當(dāng)前節(jié)點(diǎn)cur的大小決定cur指向當(dāng)前節(jié)點(diǎn)的左或者右節(jié)點(diǎn)。并在改變cur指向之前將parent賦值為cur。
如果二叉搜索樹(shù)中已經(jīng)有該值，則返回false。
4.當(dāng)cur為空的時(shí)候，建立根據(jù)k在cur處建立節(jié)點(diǎn)。比較parent的_k與k的大小，判斷cur建立在parent的左子樹(shù)還是右子樹(shù)。并返回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.首先通過(guò)cur和parent查找該節(jié)點(diǎn)。
2.如果cur左為空，判斷cur相對(duì)于parent的位置，并將cur的右子樹(shù)賦值到cur相對(duì)于parent的位置處。并刪除cur。
3.如果cur右為空，判斷cur相對(duì)于parent的位置，并將cur的左子樹(shù)賦值到cur相對(duì)于parent的位置處。并刪除cur。
4.如果cur的左右都不為空：
(1)建立一個(gè)新的節(jié)點(diǎn)指針min賦值為cur->right作為遍歷指針，和其父節(jié)點(diǎn)指針minparent賦值為cur。
(2)一直向左遍歷直到min->left為空。并交換min與cur的_key。
(3)判斷min與minparent的位置關(guān)系，并將min的右子樹(shù)放在該處。
(4)刪除min，返回true。若沒(méi)找到返回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.遞歸實(shí)現(xiàn)
(1)查找
1.判空
2.判斷root->_k與k的大小，判斷遞歸的方向。
3.如果找到了返回root節(jié)點(diǎn)。
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.判斷節(jié)點(diǎn)是否為空，如果為空將該節(jié)點(diǎn)插入節(jié)點(diǎn)的位置。并返回true
2.判斷_k和k的大小，判斷遞歸的方向。
3.如果節(jié)點(diǎn)值等于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.如果節(jié)點(diǎn)為空則返回false
2.通過(guò)_k和k的大小來(lái)判斷遞歸方向。
3.找到該節(jié)點(diǎn)：
(1)定義del指針賦值為root。
(2)如果root左子樹(shù)為空，則將root指向該節(jié)點(diǎn)的右子樹(shù)。
(3)如果root右子樹(shù)為空，則將root指向該節(jié)點(diǎn)的左子樹(shù)。
(4)如果root左右子樹(shù)都不為空，將min賦值為root->right，并依次向左找，直到min->left為空。并交換min的k與root的k。 然后遞歸到右子樹(shù)來(lái)進(jìn)行刪除。
(5)刪除原root節(jié)點(diǎn)(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);
// 遞歸到右子樹(shù)去刪除
return _EraseR(root->_right, k);//3.(4)
}
delete del;
return true;//3.(5)
}
}
5.key/value模型的應(yīng)用
key/value模型，即在原來(lái)k的基礎(chǔ)上，每個(gè)節(jié)點(diǎn)再帶有一個(gè)value值。有兩種主要的應(yīng)用：
(1)對(duì)應(yīng)查找
利用到了二叉搜索樹(shù)搜素的性質(zhì)。
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 << "對(duì)應(yīng)的中文解釋?zhuān)? << ret->_v << endl;
}
else
{
cout << "無(wú)此單詞" << endl;
}
}
我們向二叉搜索樹(shù)中存入英文單詞和中文釋義，將英文單詞作為k來(lái)構(gòu)建二叉搜索樹(shù)，如果搜索到了則打印中文釋義，這樣就簡(jiǎn)單構(gòu)成了一個(gè)字典。
(2)判斷出現(xiàn)次數(shù)
當(dāng)我們判斷一個(gè)數(shù)組中各個(gè)元素出現(xiàn)的次數(shù)的時(shí)候，也可以使用到二叉搜索樹(shù)。
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();
每一次出現(xiàn)一個(gè)元素我們就將它插入二叉搜索樹(shù)中，并把它的value賦值為1，當(dāng)?shù)诙斡龅竭@個(gè)元素的時(shí)候，在二叉搜索樹(shù)中搜索該元素，人如果可以找到該元素則將該元素的value的值++。最終統(tǒng)計(jì)出各個(gè)元素出現(xiàn)的次數(shù)。
6.總結(jié)
對(duì)于二叉搜索樹(shù)的理解對(duì)以后學(xué)習(xí)AVL樹(shù)和紅黑樹(shù)具有很大的幫助
到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹(shù)的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++搜索二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語(yǔ)言游戲必備:光標(biāo)定位與顏色設(shè)置的實(shí)現(xiàn)方法
本篇文章是對(duì)c語(yǔ)言中光標(biāo)定位與顏色設(shè)置的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++雙線程調(diào)用網(wǎng)絡(luò)攝像頭與多線程調(diào)用多攝像頭同步執(zhí)行方法詳細(xì)講解
這篇文章主要介紹了C++雙線程調(diào)用網(wǎng)絡(luò)攝像頭與多線程調(diào)用多攝像頭同步執(zhí)行方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2022-11-11
這篇文章主要介紹了c++ 防止頭文件重復(fù)引入的三種方法，幫助大家更好的理解和學(xué)習(xí)使用c++，感興趣的朋友可以了解下2021-02-02
C語(yǔ)言實(shí)現(xiàn)俄羅斯方塊課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)俄羅斯方塊課程設(shè)計(jì)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
C++?STL容器詳解之紅黑樹(shù)部分模擬實(shí)現(xiàn)
本文主要對(duì)紅黑樹(shù)進(jìn)行了詳細(xì)介紹，并對(duì)其核心功能進(jìn)行了模擬實(shí)現(xiàn)。文中的代碼對(duì)我們的學(xué)習(xí)或工作有一定的價(jià)值，感興趣的小伙伴可以了解一下2021-12-12
C++實(shí)現(xiàn)的鏈表類(lèi)實(shí)例
這篇文章主要介紹了C++實(shí)現(xiàn)的鏈表類(lèi),以完整實(shí)例分析了C++實(shí)現(xiàn)鏈表類(lèi)的定義、插入、刪除、遍歷、統(tǒng)計(jì)等相關(guān)技巧,需要的朋友可以參考下2015-06-06
C/C++語(yǔ)言中結(jié)構(gòu)體的內(nèi)存分配小例子
當(dāng)未用 #pragma 指令指定編譯器的對(duì)齊位數(shù)時(shí)，結(jié)構(gòu)體按最長(zhǎng)寬度的數(shù)據(jù)成員的寬度對(duì)齊；當(dāng)使用了 #pragma 指令指定編譯器的對(duì)齊位數(shù)時(shí)，結(jié)構(gòu)體按最長(zhǎng)寬度的數(shù)據(jù)成員的寬度和 #pragma 指令指定的位數(shù)中的較小值對(duì)齊2013-10-10
這篇文章主要介紹了詳解C++中的菱形繼承問(wèn)題,在多繼承結(jié)構(gòu)中，存在著很多問(wèn)題，比如從不同基類(lèi)中繼承了同名成員，派生類(lèi)中也定義了同名成員，這種二義性問(wèn)題很好解決，加上要訪問(wèn)的基類(lèi)的類(lèi)名限制就可以了,需要的朋友可以參考下2023-08-08
C語(yǔ)言編程數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列的全面講解示例教程
本文介紹著重介紹數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)列的知識(shí)，由于本文也設(shè)計(jì)多個(gè)動(dòng)態(tài)內(nèi)存開(kāi)辟函數(shù)，小伙伴們?cè)趯W(xué)習(xí)本文之前，一定一定一定要把動(dòng)態(tài)內(nèi)存開(kāi)辟相關(guān)知識(shí)掌握牢固，這樣學(xué)習(xí)起本文才能事半功倍2021-10-10
C語(yǔ)言字符串左旋的兩種實(shí)現(xiàn)方法
匯編語(yǔ)言中有一種移位指令叫做循環(huán)左移（ROL）,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言字符串左旋的兩種實(shí)現(xiàn)方法,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-02-02