本章主要是二叉樹的進(jìn)階部分，學(xué)習(xí)搜索二叉樹可以更好理解后面的map和set的特性。

1.二叉搜索樹概念

二叉搜索樹的遞歸定義為：非空左子樹所有元素都小于根節(jié)點(diǎn)的值，非空右子樹所有元素都大于根節(jié)點(diǎn)的值，而左右子樹也是二叉搜索樹。

2.二叉搜索樹實(shí)現(xiàn)

2.1.接口分析

2.1.1.查找

1. 從根開始比較查找，比根大則往右邊走查找，比根小則往左邊走查找。
2. 最多查找高度次，走到空，還沒找到，則該值不存在。

2.1.2.插入

1. 樹為空，則直接新增節(jié)點(diǎn)，賦值給root指針
2. 樹不空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點(diǎn)

2.1.3.刪除

首先查找元素是否在二叉搜索樹中，如果不存在，則返回false。否則要刪除的結(jié)點(diǎn)可能分下面四種情況：

1. 要刪除的結(jié)點(diǎn)無孩子結(jié)點(diǎn)
2. 要刪除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)
3. 要刪除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)
4. 要刪除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)

看起來有待刪除節(jié)點(diǎn)有四種情況，實(shí)際情況1可以與情況2或者3合并起來，因此真正的刪除過程如下：

1. 情況1：刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的左/右孩子結(jié)點(diǎn)（直接刪除））

2. 情況2：在它的右子樹中尋找中序下的第一個結(jié)點(diǎn)（關(guān)鍵碼最小，也就是右子樹中最小的結(jié)點(diǎn)），用它的值填補(bǔ)到被刪除節(jié)點(diǎn)中，再來處理該結(jié)點(diǎn)的刪除問題（替換法刪除）

   補(bǔ)充：實(shí)際上情況2找左子樹的最大節(jié)點(diǎn)也是可以的。

上述體現(xiàn)了一種“托孤”的現(xiàn)象，這和Linux中孤兒進(jìn)程的托孤很是類似。

2.2.具體實(shí)現(xiàn)

#include <iostream>
#include <string>
using namespace std;template<typename K>//這里更加習(xí)慣寫K，也就是關(guān)鍵值key的類型
struct BinarySearchTreeNode
{BinarySearchTreeNode<K>* _left;BinarySearchTreeNode<K>* _right;K _key; BinarySearchTreeNode(K key = K()) : _key(key), _left(nullptr), _right(nullptr) {}
};template<typename K>
class BinarySearchTree
{typedef BinarySearchTreeNode<K> Node;
public://BinarySearchTree() : _root(nullptr) {}BinarySearchTree() = default;//強(qiáng)制編譯器生成默認(rèn)的構(gòu)造函數(shù)BinarySearchTree(const BinarySearchTree<K>& b){_root = copy(b._root);}BinarySearchTree<K>& operator=(BinarySearchTree<K> b)//b拷貝了一份{swap(_root, b._root);return *this;}~BinarySearchTree(){destroy(_root);}//1.插入bool insert(const K& key){/*對于第一個插入的節(jié)點(diǎn)就是根節(jié)點(diǎn)。至于數(shù)據(jù)冗余，我在這里定義不允許數(shù)據(jù)冗余，也就是不允許出現(xiàn)重復(fù)的數(shù)據(jù)節(jié)點(diǎn)。這樣的搜索二叉樹會受到數(shù)據(jù)先后順序插入的影響（您也可定義允許）*///1.查看是否根節(jié)點(diǎn)if (_root == nullptr){_root = new Node(key);return true;}//2.尋找存放的位置Node* parent = nullptr;//存放root的父節(jié)點(diǎn)Node* root = _root;//遍歷，從根節(jié)點(diǎn)開始while (root)//直到空為止{parent = root;if (root->_key < key) {root = root->_right;}else if(root->_key > key){root = root->_left;}else//root->_key == key{return false;//默認(rèn)不允許重復(fù)數(shù)據(jù)}}//3.插入節(jié)點(diǎn)及數(shù)據(jù)root = new Node(key);if (parent->_key < key)//注意不可以直接賦值給root，不僅內(nèi)存泄露還連接不上節(jié)點(diǎn){parent->_right = root;}else{parent->_left = root;}return true;}bool insertR(const K& key){return _insertR(_root, key);}//2.刪除bool erase(const K& key){/*尋找被刪除的節(jié)點(diǎn)，刪除后，如果是單子節(jié)點(diǎn)還好，如果是多子節(jié)點(diǎn)就需要找到一個托孤后依舊滿足二叉搜索樹性質(zhì)的節(jié)點(diǎn)，因此刪除有兩種情況：A.被刪除節(jié)點(diǎn)是葉子節(jié)點(diǎn) 或者 被刪除節(jié)點(diǎn)的左或右孩子為空，直接將孩子節(jié)點(diǎn)替換被刪除節(jié)點(diǎn)即可B.被刪除節(jié)點(diǎn)擁有兩個子節(jié)點(diǎn)，取右子樹中最小的節(jié)點(diǎn)替代被刪除的節(jié)點(diǎn)（當(dāng)然也可以取左子樹的最大節(jié)點(diǎn)）b1.最小節(jié)點(diǎn)沒有右孩子，最小節(jié)點(diǎn)直接替代被刪除節(jié)點(diǎn)，并且將最小節(jié)點(diǎn)的空孩子節(jié)點(diǎn)交給父節(jié)點(diǎn)領(lǐng)養(yǎng)b2.最小節(jié)點(diǎn)存在右孩子，最小節(jié)點(diǎn)直接替代被刪除節(jié)點(diǎn)，并且將最小節(jié)點(diǎn)的右孩子節(jié)點(diǎn)交給父節(jié)點(diǎn)領(lǐng)養(yǎng)最后還需要注意刪除根節(jié)點(diǎn)，根節(jié)點(diǎn)沒有父節(jié)點(diǎn)的問題*/Node* parent = nullptr;Node* cur = _root;//1.尋找節(jié)點(diǎn)while (cur){if (cur->_key < key){parent = cur;//不可以和下一個if語句共用，會出現(xiàn)cur和parenat的情況，例如：test_1()中刪除10的時候cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//2.刪除節(jié)點(diǎn)（找到了）if (cur->_left == nullptr)//2.1.左為空{if (parent == nullptr)//避免cur是根節(jié)點(diǎn)，沒有父節(jié)點(diǎn)，例如：test_1()中刪除11的時候{_root = cur->_right;delete cur;return true;}if (parent->_left == cur){parent->_left = cur->_right;}else//parent->_right == cur{parent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr)//2.2.右為空{if (parent == nullptr){_root = cur->_left;delete cur;return true;}if (parent->_left == cur){parent->_left = cur->_left;}else//parent->_right == cur{parent->_right = cur->_left;}delete cur;}else//2.3.左右均不為空，取左子樹中最大的或者取右子樹中最小的節(jié)點(diǎn)替代被刪除的節(jié)點(diǎn){Node* pminRight = cur;//注意不能為nullptr，因?yàn)橛锌赡艹霈F(xiàn)不進(jìn)循環(huán)的情況Node* minRight = cur->_right;//我們選擇找右數(shù)最小節(jié)點(diǎn)while (minRight->_left != nullptr)//找到最左節(jié)點(diǎn)，但是需要注意這個最左節(jié)點(diǎn)如果有右樹，那就需要最左節(jié)點(diǎn)的父節(jié)點(diǎn)接管{pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;//替換相當(dāng)于刪除if (pminRight->_left == minRight)//最左節(jié)點(diǎn)的父節(jié)點(diǎn)托管最左節(jié)點(diǎn)的右樹，注意可能有兩種情況{pminRight->_left = minRight->_right;}else if (pminRight->_right == minRight)//最左節(jié)點(diǎn)的父節(jié)點(diǎn)托管最左節(jié)點(diǎn)的右樹，注意可能有兩種情況{pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;}bool eraseR(const K& key){return _eraseR(_root, key);}//3.查找bool find(const K& key){Node* root = _root;while (root){if (root->_key < key){root = root->_right;}else if (root->_key > key){root = root->_left;}else{return true;}}return false;}bool findR(const K& key){return _findR(_root, key);}//4.打印void inOrder(){_inOrder(_root);cout << endl;}private://1.銷毀（提供給析構(gòu)）void destroy(Node*& root){if (root == nullptr)return;destroy(root->_left);destroy(root->_right);delete root;root = nullptr;}//2.拷貝（提供給拷貝構(gòu)造）Node* copy(Node* root){if (root == nullptr){return nullptr;}Node* newroot = new Node(root->_key);newroot->_left = copy(root->_left);newroot->_right = copy(root->_right);return newroot;}//3.插入（提供給遞歸插入）bool _insertR(Node*& root, const K& key)//注意root是引用{if (root == nullptr){root = new Node(key);//這里由于傳遞的是引用，那么root就是上一級遞歸的root->_left或者root->_rightreturn true;}if (root->_key < key){return _insertR(root->_right, key);}else if (root->_key > key){return _insertR(root->_left, key);}else{return false;}}//4.刪除（提供給遞歸插入）bool _eraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _eraseR(root->_right, key);}else if (root->_key > key){return _eraseR(root->_left, key);}else//root->_key == key{Node* del = root;//保存要刪除的節(jié)點(diǎn)if (root->_right == nullptr){root = root->_left;}else if (root->_left == nullptr){root = root->_right;}else//左右均不為空{Node* maxleft = root->_left;while (maxleft->_right != nullptr)//找左樹的最大節(jié)點(diǎn){maxleft = maxleft->_right;}swap(root->_key, maxleft->_key);return _eraseR(root->_left, key);//由于左樹的最大節(jié)點(diǎn)必有一個空孩子節(jié)點(diǎn)，因此使用遞歸刪除即可，可以看到遞歸的刪除比非遞歸及其的簡單明了（注意不可以直接傳遞maxleft，這是一個局部變量）}delete del;return true;}}//5.查找（提供給遞歸查找）bool _findR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key == key)return true;if (root->_key < key){return _isRecursionFind(root->_left, key);}else//root->_key > key{return _isRecursionFind(root->_right, key);}}//6.打印（提供給遞歸打印）void _inOrder(Node* root)//注意這里不能直接就拿_root當(dāng)作缺省值了，因?yàn)槿笔≈抵荒苁浅Ａ炕蛘呷肿兞?#xff0c;而_root需要使用this->_root，而this指針是函數(shù)形參，不一定傳過來了，別談使用_root了{if (root == nullptr)return;_inOrder(root->_left);cout << root->_key << " ";_inOrder(root->_right);}//？.成員變量Node* _root;
};

這里我還為您提供了三個測試樣例：

//普通測試
void test_1()
{BinarySearchTree<int> b;b.insert(6);b.insert(2);b.insert(1);b.insert(4);b.insert(-2);b.insert(10);b.insert(9);b.insert(11);b.inOrder();b.erase(6);b.inOrder();b.erase(2);b.inOrder();b.erase(10);b.inOrder();b.erase(1);b.inOrder();b.erase(4);b.inOrder();b.erase(9);b.inOrder();b.erase(11);b.inOrder();b.erase(-2);b.inOrder();
}
//頭刪測試（需要該_root為公有成員才可以測試）
void test_2()
{BinarySearchTree<int> b;b.insert(6);b.insert(2);b.insert(1);b.insert(4);b.insert(-2);b.insert(10);b.insert(9);b.insert(11);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();
}
//遞歸測試
void test_3()
{BinarySearchTree<int> b;b.insertR(6);b.insertR(2);b.insertR(1);b.insertR(4);b.insertR(-2);b.insertR(10);b.insertR(9);b.insertR(11);BinarySearchTree<int> b1(b);b.inOrder();b.eraseR(6);b.inOrder();b.eraseR(2);b.inOrder();b.eraseR(10);b.inOrder();b.eraseR(1);b.inOrder();b.eraseR(4);b.inOrder();b.eraseR(9);b.inOrder();b.eraseR(11);b.inOrder();b.eraseR(-2);b.inOrder();b1.inOrder();b.inOrder();
}

3.二叉搜索樹應(yīng)用

3.1.Key模型

考慮“在不在”的問題，例如：

1. 門禁系統(tǒng)
2. 車庫系統(tǒng)
3. 單詞檢查、搜索…

查找對象是否在數(shù)據(jù)庫中存在，這樣的場景在現(xiàn)實(shí)中有很多。

3.2.Key/Value模型

通過一個值查找另外一個值，例如：

1. 中英文互譯
2. 電話號碼查詢快遞信息
3. 驗(yàn)證碼查詢信息…

只需要在一個節(jié)點(diǎn)中包含一個數(shù)據(jù)對即可。

另外我們之前說過二叉搜索樹一般不存儲重復(fù)的元素，如果相同的元素可以讓該元素綁定一個int元素形成鍵值對，這種情況的實(shí)際應(yīng)用有：統(tǒng)計高頻詞匯。

補(bǔ)充：實(shí)際上，上面的這兩種模型對標(biāo)的是C++的set和map容器，這些我們后續(xù)學(xué)習(xí)。

4.二叉搜索樹分析

由于缺失平衡性，二叉搜索樹在最不理想的狀態(tài)（一顆斜樹）查找的時間復(fù)雜度是$O(n)$，最好的效率是$O(lo{g}_2(N))$。