對(duì)于已經(jīng)學(xué)習(xí)C++/C語言的朋友來說，二叉樹這個(gè)概念相信已經(jīng)再熟悉不過了，我們平時(shí)接觸的二叉樹可能都很簡單，今天我們來看一個(gè)比較有難度的二叉樹，他的名字就是——二叉搜索樹，只是聽名字就知道他其實(shí)是用來搜索數(shù)據(jù)用的，那么他到底有什么特別之處呢？下面讓我們一起來看看吧。
一、二叉搜索樹的概念二叉搜索樹又稱二叉排序樹(二叉查找樹)，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹:
1.若它的左子樹不為空，則左子樹上所有結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值。
2.若它的右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值都大于根結(jié)點(diǎn)的值。
3.他的左右子樹也分別為二叉樹搜索樹
上面的這棵樹就是一個(gè)典型的二叉搜索樹。
既然已經(jīng)大概知道一棵二叉搜索樹是什么樣子的了，那么就讓我們一起來實(shí)現(xiàn)一下吧。
1.節(jié)點(diǎn)類我們知道二叉樹其實(shí)就是一個(gè)一個(gè)的結(jié)點(diǎn)連接在一起，然后遵循我們前面所說的概念，就能夠形成一棵二叉搜索樹了，所以結(jié)點(diǎn)類是必不可少的。
重慶分公司
重慶分公司
template//模板參數(shù)
struct BSTreeNode
{
struct BSTreeNode* _left;//左指針
struct BSTreeNode* _right;//右指針
K _key; //結(jié)點(diǎn)存儲(chǔ)的值(節(jié)點(diǎn)值)
//構(gòu)造函數(shù)，實(shí)現(xiàn)對(duì)創(chuàng)建的結(jié)點(diǎn)的初始化
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
}; 注: 因?yàn)槲覀兒竺娑x的二叉搜索樹需要用到我們這里定義的結(jié)點(diǎn)類，所以直接將他定義為struct的形式，因?yàn)閟truct中的成員函數(shù)和成員變量默認(rèn)是共有的，這樣方便我們后面的調(diào)用。
2.二叉搜索樹類內(nèi)部定義templateclass BSTree
{
typedef BSTreeNodeNode; //typedef使代碼更簡潔
public:
//構(gòu)造函數(shù)
//這樣可以讓編譯器強(qiáng)制自己生成默認(rèn)構(gòu)造函數(shù)
BSTree() = default;
//拷貝構(gòu)造
BSTree(const BSTree& t){}
//析構(gòu)函數(shù)
~BSTree(){}
BSTree& operator=(BSTreet){}
//插入操作
bool Insert(const K& key){}
//刪除操作
bool Erase(const K& key){}
//中序遍歷
void InOrder(){}
//查找操作
bool Find(const K& key)
private:
//子函數(shù)
Node* _Copy(Node* root){}
void _InOrder(Node* root){}
void _Destory(Node* root){}
private:
Node* _root = nullptr;
}; 因?yàn)槲覀冎笠榭次覀儎?chuàng)建的樹到底符不符合我們的要求以及一些接口實(shí)現(xiàn)的正確性，所以我們需要將其中存儲(chǔ)的數(shù)據(jù)打印出來，這里還有一個(gè)細(xì)節(jié)，如果我們以中序遍歷的方式去遍歷整棵二叉樹的話，最后的打印結(jié)果是以升序的方式排布的，這樣方便我們查看。
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);//遍歷左子樹
cout<< root->_key<< " ";
_InOrder(root->_right);//遍歷右子樹
}
void InOrder()
{
_InOrder(_root);//調(diào)用子函數(shù)
cout<< endl;
}這里大家可以看到我們上面給出了兩個(gè)函數(shù)，其中_InOrder是用訪問限定符private修飾的，這里為什么要這么操作呢？
解釋:
這里的_InOrder是InOrder函數(shù)的子函數(shù)，因?yàn)開root是私有成員，用戶去調(diào)用這里的遍歷函數(shù)的話就需要傳入根結(jié)點(diǎn)，但是我們經(jīng)過封裝后，用戶是無法訪問_root這個(gè)成員變量的，所以才有了這里的子函數(shù)的誕生，類內(nèi)的函數(shù)是可以訪問類內(nèi)的所有成員變量的，我們可以通過子函數(shù)去實(shí)現(xiàn)函數(shù)的功能，用戶在調(diào)用函數(shù)的不需要傳入任何參數(shù)，這樣既沒有會(huì)暴露我們的底層實(shí)現(xiàn)，也實(shí)現(xiàn)了函數(shù)的功能。
在后面的操作中涉及到遞歸函數(shù)的時(shí)候，也會(huì)這樣使用。
這里得構(gòu)造函數(shù)是一定要自己實(shí)現(xiàn)的，因?yàn)楹竺嫖覀冃枰截悩?gòu)造函數(shù)，他其實(shí)也是一個(gè)構(gòu)造函數(shù)，根據(jù)我們前面所學(xué)的，當(dāng)我們自己寫了一個(gè)構(gòu)造函數(shù)的時(shí)候，編譯器是無法再自動(dòng)生成默認(rèn)構(gòu)造函數(shù)的。就不能再像下面的這種情況進(jìn)行樹的定義，所以構(gòu)造函數(shù)一定要自己顯示寫一個(gè)。
//沒有默認(rèn)構(gòu)造函數(shù)的話，就不能像這樣進(jìn)行構(gòu)造
BSTreet; 構(gòu)造函數(shù)有三種寫法:
//1.可以這么寫,順便進(jìn)行初始化
BSTree()
:_root(nullptr)//創(chuàng)建一個(gè)空樹
{}
//2.可以這么寫，內(nèi)置類型編譯器可以自動(dòng)初始化
BSTree(){}
//3.可以這么寫
//這樣可以讓編譯器強(qiáng)制自己生成默認(rèn)構(gòu)造函數(shù)
BSTree() = default;這里又要用到我們前面遍歷函數(shù)所講的子函數(shù)，道理是相同的，這里就不再進(jìn)行描述。
//利用遞歸實(shí)現(xiàn)拷貝構(gòu)造的子函數(shù)
Node* _Copy(Node* root)
{
//如果是空樹的話直接返回
if (root == nullptr)
return nullptr;
Node* copyRoot = new Node(root->_key);//先拷貝根結(jié)點(diǎn)
copyRoot->_left = _Copy(root->_left);//拷貝左子樹
copyRoot->_right = _Copy(root->_right);//拷貝右子樹
return copyRoot; //返回拷貝的樹的根結(jié)點(diǎn)
}
BSTree(const BSTree& t)
{
//因?yàn)樾枰猒root私有成員，所以需要一個(gè)子函數(shù)。
_root = _Copy(t._root); //拷貝子函數(shù)
} 注意: 這里的拷貝構(gòu)造函數(shù)實(shí)現(xiàn)的是深拷貝。
6.賦值運(yùn)算符重載關(guān)于賦值運(yùn)算符重載一般情況下是有兩種方法的，我們將其稱為現(xiàn)代寫法和傳統(tǒng)寫法。
現(xiàn)代寫法
BSTree& operator=(BSTreet)//函數(shù)在接收傳入的參數(shù)的時(shí)候會(huì)先自動(dòng)調(diào)用拷貝構(gòu)造函數(shù)創(chuàng)建t對(duì)象
{
swap(_root, t._root);//將本對(duì)象的_root結(jié)點(diǎn)與t對(duì)象中的_root進(jìn)行交換，就實(shí)現(xiàn)可兩棵樹數(shù)據(jù)互換，即拷貝成功
return *this; //這樣返回的話也就可以支持連續(xù)賦值
} 傳統(tǒng)寫法
傳統(tǒng)寫法就是將傳入的樹的結(jié)點(diǎn)一一進(jìn)行拷貝后再鏈接在一起就可以了。
BSTree& operator=(BSTree& t)
{
if (this != &t) //防止自己給自己賦值
{
_root = _Copy(t._root);
}
return *this;//支持連續(xù)賦值
} 這里也需要實(shí)現(xiàn)一個(gè)子函數(shù)，因?yàn)槲覀冊(cè)阡N毀樹的時(shí)候也需要傳入私有成員–根結(jié)點(diǎn)。
void _Destory(Node* root)
{
//空樹直接返回
if (root == nullptr)
{
return;
}
//轉(zhuǎn)化為子問題
_Destory(root->_left);//銷毀左子樹
_Destory(root->_right);//銷毀右子樹
delete root; //釋放根結(jié)點(diǎn)
root = nullptr;
}
//析構(gòu)函數(shù)
~BSTree()
{
//調(diào)用子函數(shù)
_Destory(_root);
}二叉搜索樹的插入
插入的具體過程如下：
a. 樹為空，則直接新增結(jié)點(diǎn)，賦值給root指針
b. 樹不空，按二叉搜索樹性質(zhì)查找插入位置，插入新結(jié)點(diǎn)
若樹不為空其具體操作如下:
1.若插入的結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值，則需要進(jìn)入左子樹進(jìn)行插入
2.若插入的結(jié)點(diǎn)的值大于根結(jié)點(diǎn)的值，則需要進(jìn)入右子樹進(jìn)行插入
3.若插入的結(jié)點(diǎn)的值與根結(jié)點(diǎn)的值相等，則插入失敗
重復(fù)上面的操作，找到與自己相等的結(jié)點(diǎn)，插入失敗，直接返回。若是走到了空結(jié)點(diǎn)的位置，則說明在該樹中沒有與之相等的值，進(jìn)行插入操作即可。
非遞歸實(shí)現(xiàn)下面的key變量即為我們要插入的值，因?yàn)槲覀冏詈筮€要將新建的節(jié)點(diǎn)與前面的結(jié)點(diǎn)(也就是父結(jié)點(diǎn))連接起來，所以還需要個(gè)結(jié)點(diǎn)記錄父結(jié)點(diǎn)(即parent)
bool Insert(const K& key)
{
//剛進(jìn)入查找時(shí)，根結(jié)點(diǎn)為空，說明是空樹，直接插入即可
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
//循環(huán)找空,cur走到空則找到了自己的位置
while (cur)//(cur != nullptr)
{
//key大于當(dāng)前結(jié)點(diǎn)的值，根據(jù)性質(zhì)需要到右子樹去尋找
if (key >cur->_key)
{
parent = cur;
cur = cur->_right;
}
//key小于當(dāng)前結(jié)點(diǎn)的值，根據(jù)性質(zhì)需要到左子樹去尋找
else if (key< cur->_key)
{
parent = cur;
cur = cur->_left;
}
//上面的兩種情況都不是的話，說明key值與當(dāng)前節(jié)點(diǎn)的值相等，插入失敗
else
return false;
}
//循環(huán)結(jié)束后說明找到了屬于自己的位置，創(chuàng)建結(jié)點(diǎn)
cur = new Node(key);
//此時(shí)還需要判斷一下節(jié)點(diǎn)與父結(jié)點(diǎn)的關(guān)系
//大于父結(jié)點(diǎn)的值，插入到父結(jié)點(diǎn)的右邊
if (key >parent->_key)
parent->_right = cur;
//否則插入父結(jié)點(diǎn)的左邊
else
parent->_left = cur;
//插入成功返回true
return true;
}//子函數(shù)實(shí)現(xiàn)遞歸
bool _InsertR(Node*& root, const K& key)//注意引用，十分重要
{
//查找時(shí)，根結(jié)點(diǎn)為空，說明是空樹或找到了插入的位置，直接插入
if (root == nullptr)
{
root = new Node(key);
//插入成功，返回true
return true;
}
//key大于當(dāng)前結(jié)點(diǎn)的值，根據(jù)性質(zhì)需要到右子樹去尋找
if (key >root->_key)
{
//進(jìn)入右子樹
return _InsertR(root->_right, key);
}
//key小于當(dāng)前結(jié)點(diǎn)的值，根據(jù)性質(zhì)需要到左子樹去尋找
else if (key< root->_key)
{
//進(jìn)入左子樹
return _InsertR(root->_left, key);
}
//上面的兩種情況都不是的話，說明key值與當(dāng)前結(jié)點(diǎn)的值相等，插入失敗
else
return false;
}
//外部函數(shù)對(duì)遞歸函數(shù)實(shí)現(xiàn)封裝
bool InsertR(const K& key)
{
//直接調(diào)用子函數(shù)
return _InsertR(_root, key);
}注意: 本函數(shù)中最精華的地方就是傳的是引用參數(shù)，因?yàn)橛幸玫拇嬖冢覀兙筒恍枰ビ涗浉腹?jié)點(diǎn)所在的位置，直接修改root的指向，同時(shí)也就修改了父結(jié)點(diǎn)的指向。
9.刪除函數(shù)在實(shí)現(xiàn)二叉搜索樹的函數(shù)中，刪除操作是最復(fù)雜的，其中的情況有很多。
首先查找元素是否在二叉搜索樹中，如果不存在，則返回，否則要?jiǎng)h除的結(jié)點(diǎn)可能分下面的四種情況:
a.要?jiǎng)h除的結(jié)點(diǎn)無孩子結(jié)點(diǎn)
b.要?jiǎng)h除的結(jié)點(diǎn)左子樹為空
c.要?jiǎng)h除的結(jié)點(diǎn)右子樹為空
d.要?jiǎng)h除的結(jié)點(diǎn)左右子樹均不為空
看起來要?jiǎng)h除結(jié)點(diǎn)是有4中情況，實(shí)際情況中情況a可以與情況b或者情況c合并起來，因此真正的刪除過程如下:
1.要?jiǎng)h除的結(jié)點(diǎn)左子樹為空(左右子樹均為空)
2.要?jiǎng)h除的結(jié)點(diǎn)右子樹為空
3.要?jiǎng)h除的結(jié)點(diǎn)左右子樹均不為空
只是這么看的話，可能比較抽象，下面我們將其分開剖析，然后再結(jié)合畫圖，一起看看如何實(shí)現(xiàn)其代碼。
情況1:要?jiǎng)h除的結(jié)點(diǎn)左子樹為空(左右子樹均為空)
這里我們將前面所說的情況a放入情況b中一起講解。
這里為了更好地演示，我會(huì)將幾個(gè)空結(jié)點(diǎn)也畫出來。
1.先來看左右子樹均為空的場(chǎng)景
2.再來看一下左子樹為空的場(chǎng)景
場(chǎng)景1:
通過上面兩個(gè)圖的對(duì)比，我們可以看出在情況a與情況b中的操作是相同的，所以我們可以將他們歸為一種情況去操作。
其實(shí)在刪除左子樹為空的結(jié)點(diǎn)的時(shí)候是有兩個(gè)場(chǎng)景的，上面的場(chǎng)景是要?jiǎng)h除的結(jié)點(diǎn)在父節(jié)點(diǎn)的左邊，下面的這種場(chǎng)景是要?jiǎng)h除的結(jié)點(diǎn)在父節(jié)點(diǎn)的右邊，但是他們共有的特性都是左子樹為空。所以只是在處理父節(jié)點(diǎn)的時(shí)候不同而已
場(chǎng)景2:
情況2:要?jiǎng)h除的結(jié)點(diǎn)右子樹為空
這種情況其實(shí)與情況1中的左子樹為空一樣，也有兩種場(chǎng)景，與父結(jié)點(diǎn)有關(guān)系，所以我們就直接放在一起了。
情況3.要?jiǎng)h除的結(jié)點(diǎn)左右子樹均不為空
其實(shí)除了我們上面舉出的例子外，還有刪除父結(jié)點(diǎn)的值的情況，其實(shí)他們的操作都是類似的，都是將要?jiǎng)h除的值換出去，進(jìn)而delete其他的結(jié)點(diǎn)。
bool Erase(const K& key)
{
//定義一個(gè)cur結(jié)點(diǎn)指針，進(jìn)行查找
Node* cur = _root;
//定義一個(gè)結(jié)點(diǎn)保存父結(jié)點(diǎn)的指針
Node* parent = nullptr;
//查找我們要?jiǎng)h除的結(jié)點(diǎn)
while (cur)
{
//key大于當(dāng)前結(jié)點(diǎn)的值，根據(jù)性質(zhì)需要到右子樹去尋找
if (key >cur->_key)
{
parent = cur;
cur = cur->_right;
}
//key小于當(dāng)前結(jié)點(diǎn)的值，根據(jù)性質(zhì)需要到左子樹去尋找
else if (key< cur->_key)
{
parent = cur;
cur = cur->_left;
}
//上面兩種情況都不是，就是已經(jīng)找到了，開始刪除
else
{
//1.左為空，只有右孩子
if (cur->_left == nullptr)
{
//如果是根結(jié)點(diǎn)，直接讓_root指向當(dāng)前結(jié)點(diǎn)的右結(jié)點(diǎn)
if (cur == _root)
{
_root = cur->_right;
}
//如果不是根結(jié)點(diǎn)，需要判斷要?jiǎng)h除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左結(jié)點(diǎn)還是右結(jié)點(diǎn)
else
{
//是父節(jié)點(diǎn)的左結(jié)點(diǎn)，則讓父親的左結(jié)點(diǎn)指向要?jiǎng)h除節(jié)點(diǎn)的右結(jié)點(diǎn)
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
//是父節(jié)點(diǎn)的右結(jié)點(diǎn)，則讓父親的右結(jié)點(diǎn)指向要?jiǎng)h除節(jié)點(diǎn)的右結(jié)點(diǎn)
else
{
parent->_right = cur->_right;
}
}
//釋放結(jié)點(diǎn)的空間
delete cur;
cur = nullptr;//置空
}
//2.右為空，只有左孩子
else if (cur->_right == nullptr)
{
//如果是根結(jié)點(diǎn)，直接讓_root指向當(dāng)前結(jié)點(diǎn)的右結(jié)點(diǎn)
if (cur == _root)
{
_root = cur->_left;
}
//如果不是根結(jié)點(diǎn)，需要判斷要?jiǎng)h除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左結(jié)點(diǎn)還是右結(jié)點(diǎn)
else
{
//是父節(jié)點(diǎn)的左結(jié)點(diǎn)，則讓父親的左結(jié)點(diǎn)指向要?jiǎng)h除節(jié)點(diǎn)的左結(jié)點(diǎn)
if (parent->_left = cur)
{
parent->_left = cur->_left;
}
//是父節(jié)點(diǎn)的右結(jié)點(diǎn)，則讓父親的右結(jié)點(diǎn)指向要?jiǎng)h除節(jié)點(diǎn)的左結(jié)點(diǎn)
else
{
parent->_right = cur->_left;
}
}
//釋放結(jié)點(diǎn)的空間
delete cur;
cur = nullptr;
}
//3.有左右孩子，替換法
//這里我們找右子樹的最小值
else
{
//定義一個(gè)結(jié)點(diǎn)記錄找到的最小值所在的結(jié)點(diǎn)
Node* min = cur->_right;
//定義一個(gè)結(jié)點(diǎn)記錄找到的最小值所在的結(jié)點(diǎn)的父節(jié)點(diǎn)
Node* minParent = cur;
//循環(huán)查找最小值所在的結(jié)點(diǎn)
while (min->_left)
{
minParent = min;//min結(jié)點(diǎn)發(fā)生變化的時(shí)候父節(jié)點(diǎn)也要變化
min = min->_left;//min結(jié)點(diǎn)變化
}
//循環(huán)結(jié)束表示已經(jīng)找到最小值所在的結(jié)點(diǎn)
swap(cur->_key, min->_key);//交換數(shù)據(jù)
//min結(jié)點(diǎn)在父結(jié)點(diǎn)的左邊
if (minParent->_left == min)
{
minParent->_left = min->_right;
}
//min結(jié)點(diǎn)在父節(jié)點(diǎn)的右邊
else
{
minParent->_right = min->_right;
}
//釋放結(jié)點(diǎn)的空間
delete min;
min = nullptr;//置空
}
//刪除成功返回true
return true;
}
}
//刪除失敗返回false
return false;
}遞歸實(shí)現(xiàn)刪除操作的思路:
1.若樹為空樹(這里所說的樹可能是整棵大樹，也可能是遞歸時(shí)的子樹)，則結(jié)點(diǎn)刪除失敗，直接返回false。
2.若所傳入的key值小于當(dāng)前樹的根節(jié)點(diǎn)的值，則問題變?yōu)閯h除左子樹中值為key的結(jié)點(diǎn)。
3.若所傳入的key值大于當(dāng)前樹的根節(jié)點(diǎn)的值，則問題變?yōu)閯h除右子樹中值為key的結(jié)點(diǎn)。
4.若所傳入的key值等于當(dāng)前樹的根節(jié)點(diǎn)的值，則分析該結(jié)點(diǎn)滿足的我們上面分析的哪一種情況，刪除該結(jié)點(diǎn)。
bool _EraseR(Node*& root, const K& key)//注意引用
{
//若根節(jié)點(diǎn)為空，直接返回false
if (root == nullptr)
return false;
//若傳入的key值大于當(dāng)前結(jié)點(diǎn)的值，則要?jiǎng)h除的結(jié)點(diǎn)在右子樹中
if (key >root->_key)
return _EraseR(root->_right, key);
//若傳入的key值小于當(dāng)前結(jié)點(diǎn)的值，則要?jiǎng)h除的結(jié)點(diǎn)在左子樹中
else if(key< root->_key)
return _EraseR(root->_left, key);
//走到這里這里表示當(dāng)前節(jié)點(diǎn)就為要?jiǎng)h除的的結(jié)點(diǎn)
else
{
//定義一個(gè)節(jié)點(diǎn)保存要?jiǎng)h除的結(jié)點(diǎn)的地址
Node* del = root;
//1.左為空，只有右孩子
if (root->_left == nullptr)
{
root = root->_right;
}
//2.右為空，只有左孩子
else if (root->_right == nullptr)
{
root = root->_left;
}
//3.有左右孩子
else
{
//定義一個(gè)結(jié)點(diǎn)記錄找到的最小值所在的結(jié)點(diǎn)
Node* min = root->_right;
//循環(huán)查找最小值，左為空，則當(dāng)前節(jié)點(diǎn)中的值就為最小值
while (min->_left)
{
min = min->_left;
}
//交換最小值與要?jiǎng)h除的值
swap(root->_key, min->_key);
//替換后轉(zhuǎn)化為刪除右子樹中的節(jié)點(diǎn)(轉(zhuǎn)化為子問題)。
//因?yàn)槲覀兊牟僮骶褪侨ビ易訕渲胁檎易钚≈?，所以要?jiǎng)h除的結(jié)點(diǎn)一定在右子樹中。
return _EraseR(root->_right, key);
}
//釋放要?jiǎng)h除的結(jié)點(diǎn)的空間
delete del;
del = nullptr;//置空
//刪除成功，返回true
return true;
}
}
bool EraseR(const K& key)
{
//調(diào)用子函數(shù)
return _EraseR(_root, key);
}注意: 本函數(shù)中最精華的地方就是傳的是引用參數(shù)，因?yàn)橛幸玫拇嬖?，我們就不需要去記錄父?jié)點(diǎn)所在的位置，直接修改root的指向，同時(shí)也就修改了父結(jié)點(diǎn)的指向。
10.查找函數(shù)查找函數(shù)就非常簡單了，我們只需要根據(jù)二叉搜索樹的性質(zhì)去進(jìn)行查找就可以了。
查找操作的思路:
1.若樹為空樹，則查找失敗，直接返回false
2.若所傳入的key值小于當(dāng)前樹的根節(jié)點(diǎn)的值，則應(yīng)該去左子樹中查找
3.若所傳入的key值大于當(dāng)前樹的根節(jié)點(diǎn)的值，則應(yīng)該去右子樹中查找
4.若所傳入的key值等于當(dāng)前樹的根節(jié)點(diǎn)的值，就找到了，直接返回true
bool Find(const K& key)
{
//定義一個(gè)cur負(fù)責(zé)查找我們要找的值
Node* cur = _root;
//如果cur!=nullptr，就可以一直進(jìn)行查找
while (cur)
{
//如果key的值大于當(dāng)前結(jié)點(diǎn)的值，則要找的值在右子樹中
if (key >cur->_key)
cur = cur->_right;
//如果key的值小于當(dāng)前結(jié)點(diǎn)的值，則要找的值在左子樹中
else if (key< cur->_key)
cur = cur->_left;
//走到這里表示當(dāng)前的值就為我們要找的值
else
//直接返回true，表示樹中存在key值
return true;
}
//循環(huán)結(jié)束，表示cur走到了空，即樹中沒有該key值
return false;
}bool _FindR(Node* root,const K& key)
{
//如果根節(jié)點(diǎn)為空，則直接返回
if (root = nullptr)
return false;
//如果key的值大于當(dāng)前結(jié)點(diǎn)的值，則要找的值在右子樹中
if (key >root->_key)
return _FindR(root->_right, key);
//如果key的值小于當(dāng)前結(jié)點(diǎn)的值，則要找的值在左子樹中
else if (key< root->_key)
return _Find(root->_left, key);
//到這一步則證明已經(jīng)找到與key值相同的值，返回true
else
return true;
}
bool FindR(const K& key)
{
//調(diào)用子函數(shù)
return _FindR(_root,key);
}K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲(chǔ)Key即可，關(guān)鍵碼即為需要搜索到的值。
比如：給一個(gè)單詞，判斷該單詞是否拼寫正確，具體方式如下：
以詞庫中所有單詞集合中的每個(gè)單詞作為key，構(gòu)建一棵二叉搜索樹
在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯(cuò)誤。
每一個(gè)關(guān)鍵碼key，都有與之對(duì)應(yīng)的值Value，即
該種方式在現(xiàn)實(shí)生活中非常常見：
比如英漢詞典就是英文與中文的對(duì)應(yīng)關(guān)系，通過英文可以快速找到與其對(duì)應(yīng)的中文，英文單詞與其對(duì)應(yīng)的中文
再比如統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)次數(shù)就是
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個(gè)操作的性能。
對(duì)有n個(gè)結(jié)點(diǎn)的二叉搜索樹，若每個(gè)元素查找的概率相等，則二叉搜索樹平均查找長度是結(jié)點(diǎn)在二叉搜索樹的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。
但對(duì)于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹，如下
最優(yōu)情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數(shù)為:logN
最差情況下，二叉搜索樹退化為單枝樹(或者類似單支)，其比較次數(shù)最壞能達(dá)到n。
如果退化成單枝樹，二叉搜索樹的性能就失去了。所以我們?cè)诤竺嬉獙?duì)其進(jìn)行改進(jìn)，不論按照什么次序插入關(guān)鍵碼，二叉搜索樹的性能都能達(dá)到最優(yōu)。這里就涉及到了我們后面要學(xué)習(xí)的AVL樹和紅黑樹。
以上就是我們所講的二叉搜索樹的全部內(nèi)容了，其中的重點(diǎn)和難點(diǎn)其實(shí)都是刪除操作，其他的一些操作還是比較容易理解的，后面我們還會(huì)講述更AVL樹、紅黑樹等更高階的樹的實(shí)現(xiàn)，大家可以先關(guān)注博主，方便以后查看。如果你覺得我的內(nèi)容對(duì)你有用的話，記得給波三連呦?。?！
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
