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

1.二叉搜索樹概念

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

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

2.1.接口分析

2.1.1.查找

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

2.1.2.插入

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

2.1.3.刪除

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

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

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

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

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

   補充：實際上情況2找左子樹的最大節(jié)點也是可以的。

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

2.2.具體實現(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;//強制編譯器生成默認(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é)點就是根節(jié)點。至于數(shù)據(jù)冗余，我在這里定義不允許數(shù)據(jù)冗余，也就是不允許出現(xiàn)重復(fù)的數(shù)據(jù)節(jié)點。這樣的搜索二叉樹會受到數(shù)據(jù)先后順序插入的影響（您也可定義允許）*///1.查看是否根節(jié)點if (_root == nullptr){_root = new Node(key);return true;}//2.尋找存放的位置Node* parent = nullptr;//存放root的父節(jié)點Node* root = _root;//遍歷，從根節(jié)點開始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é)點及數(shù)據(jù)root = new Node(key);if (parent->_key < key)//注意不可以直接賦值給root，不僅內(nèi)存泄露還連接不上節(jié)點{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é)點，刪除后，如果是單子節(jié)點還好，如果是多子節(jié)點就需要找到一個托孤后依舊滿足二叉搜索樹性質(zhì)的節(jié)點，因此刪除有兩種情況：A.被刪除節(jié)點是葉子節(jié)點 或者 被刪除節(jié)點的左或右孩子為空，直接將孩子節(jié)點替換被刪除節(jié)點即可B.被刪除節(jié)點擁有兩個子節(jié)點，取右子樹中最小的節(jié)點替代被刪除的節(jié)點（當(dāng)然也可以取左子樹的最大節(jié)點）b1.最小節(jié)點沒有右孩子，最小節(jié)點直接替代被刪除節(jié)點，并且將最小節(jié)點的空孩子節(jié)點交給父節(jié)點領(lǐng)養(yǎng)b2.最小節(jié)點存在右孩子，最小節(jié)點直接替代被刪除節(jié)點，并且將最小節(jié)點的右孩子節(jié)點交給父節(jié)點領(lǐng)養(yǎng)最后還需要注意刪除根節(jié)點，根節(jié)點沒有父節(jié)點的問題*/Node* parent = nullptr;Node* cur = _root;//1.尋找節(jié)點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é)點（找到了）if (cur->_left == nullptr)//2.1.左為空{if (parent == nullptr)//避免cur是根節(jié)點，沒有父節(jié)點，例如：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é)點替代被刪除的節(jié)點{Node* pminRight = cur;//注意不能為nullptr，因為有可能出現(xiàn)不進循環(huán)的情況Node* minRight = cur->_right;//我們選擇找右數(shù)最小節(jié)點while (minRight->_left != nullptr)//找到最左節(jié)點，但是需要注意這個最左節(jié)點如果有右樹，那就需要最左節(jié)點的父節(jié)點接管{pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;//替換相當(dāng)于刪除if (pminRight->_left == minRight)//最左節(jié)點的父節(jié)點托管最左節(jié)點的右樹，注意可能有兩種情況{pminRight->_left = minRight->_right;}else if (pminRight->_right == minRight)//最左節(jié)點的父節(jié)點托管最左節(jié)點的右樹，注意可能有兩種情況{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é)點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é)點{maxleft = maxleft->_right;}swap(root->_key, maxleft->_key);return _eraseR(root->_left, key);//由于左樹的最大節(jié)點必有一個空孩子節(jié)點，因此使用遞歸刪除即可，可以看到遞歸的刪除比非遞歸及其的簡單明了（注意不可以直接傳遞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)作缺省值了，因為缺省值只能是常量或者全局變量，而_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)實中有很多。

3.2.Key/Value模型

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

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

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

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

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

4.二叉搜索樹分析

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