目錄

一，概念

二，實(shí)現(xiàn)分析

1. ?插入

（1.）非遞歸版本?

?（2.）遞歸版本

?2. 打印搜索二叉樹

3.查找函數(shù)

（1.）非遞歸版本

（2.）遞歸版本

4. 刪除函數(shù)（重難點(diǎn)）?

易錯(cuò)點(diǎn)分析，包你學(xué)會(huì)

（1.）刪除目標(biāo)，沒有左右孩子

（2.）刪除目標(biāo)，只有一個(gè)孩子

（3.）刪除目標(biāo)，有兩個(gè)孩子

代碼

（1.）非遞歸版本?

（2.）遞歸版本

5. 析構(gòu)函數(shù)

6.拷貝構(gòu)造?

?三，應(yīng)用

?四，搜索二叉樹的缺陷及優(yōu)化

五，代碼匯總

結(jié)語

---

一，概念

若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值

若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值

它的左右子樹也分別為二叉搜索樹

為啥又被稱作二叉排序樹呢？ 當(dāng)該樹被層序遍歷時(shí)，就是升序。

二，實(shí)現(xiàn)分析

實(shí)驗(yàn)例子：

int a[] = {8, 3, 1, 10, 6, 4, 5, 7, 14, 13};?

1. ?插入

（1.）非遞歸版本?

a、從根開始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。

b、最多查找高度次，走到到空，還沒找到，這個(gè)值不存在。

?比較簡(jiǎn)單這里就直接放代碼：

template <class K>
class BinarySeaTree_node
{typedef BinarySeaTree_node<K> BST_node;
public:BinarySeaTree_node(const K& val): _val(val),_left(nullptr),_right(nullptr){}K _val;BST_node* _left;BST_node* _right;
};template <class T>
class BSTree
{typedef BinarySeaTree_node<T> BST_node;
private:BST_node* root = nullptr;public:bool Insert(const T& val){BST_node* key = new BST_node(val);BST_node* cur = root;BST_node* parent = nullptr;while (cur){if (key->_val < cur->_val){parent = cur;cur = cur->_left;}else if (key->_val > cur->_val){parent = cur;cur = cur->_right;}else{return 0;}}// 查詢好位置后，建立鏈接if (!root){root = key;return 0;}if (key->_val > parent->_val){parent->_right = key;}else{parent->_left = key;}return 1;}
};

?（2.）遞歸版本

這里面整了個(gè)活，大家注意了!!!

bool Re_Insert(const T& val){  return Re_Insert_table(root, val);}bool Re_Insert_table(BST_node*& node, const T& val){if (node == nullptr){node = new BST_node(val);return 1;}if (val < node->_left){return Re_Insert_table(node->_left, val);}else if (val > node->_right){ return Re_Insert_table(node->_right, val);}else{return 0;}}

這里方便大家理解，我給大家花一個(gè)遞歸展開圖。

?2. 打印搜索二叉樹

?

a. 樹為空，則直接新增節(jié)點(diǎn)，賦值給root指針

b. 樹不空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點(diǎn)

這里也是僅做代碼分享：?

void Print_table() { Re_Print(root); }void Re_Print(const BST_node* node){if (node == nullptr)return;Re_Print(node->_left);cout << node->_val << " ";Re_Print(node->_right);}

3.查找函數(shù)

思路：其實(shí)也沒啥思路，比父結(jié)點(diǎn)小，就找左邊，否則找右邊。?

（1.）非遞歸版本

BST_node* Find(const T& val){//直接跟尋找位置一樣BST_node* parent = nullptr;BST_node* cur = root; // 以返回cur的方式返回while (cur)   // 非遞歸版本{if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{return cur;}}return cur;}

（2.）遞歸版本

BST_node* Re_Find(const T& val){   return Re_Find_table(root, val); }BST_node* Re_Find_table(BST_node* node, const T& val){if (node == nullptr)return nullptr;if (val < node->_val){return Re_Find_table(node->_left, val);}else if (val > node->_val){return Re_Find_table(node->_right, val);}else{return node;}}

4. 刪除函數(shù)（重難點(diǎn)）?

我們簡(jiǎn)單尋找了一下思路，如下：

但這些思路只是大概方向，其中藏著許多的坑點(diǎn)，諾接下來我來帶大家，對(duì)這些易錯(cuò)點(diǎn)進(jìn)行分析。

首先是查詢到目標(biāo)：

這個(gè)比較簡(jiǎn)單，這里不做解釋。?

       //首先尋找到目標(biāo),并且記錄到parentBST_node* parent = nullptr;BST_node* cur = root;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{break;}}if (!cur){return 0;}

易錯(cuò)點(diǎn)分析，包你學(xué)會(huì)

（1.）刪除目標(biāo)，沒有左右孩子

?

（2.）刪除目標(biāo)，只有一個(gè)孩子

一般的思路：?

?但，這是有漏洞的！

諾：

（3.）刪除目標(biāo)，有兩個(gè)孩子

?好啦，前菜上完了來看看，本次的大菜。

代碼

（1.）非遞歸版本?

bool Erase(const T& val){//首先尋找到指定值,并且記錄到parentBST_node* parent = nullptr;BST_node* cur = root;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{break;}}if (!cur){return 0;}// 查詢成功,開始刪除if (!cur->_left && !cur->_right) // cur沒有左右孩子{   // 當(dāng)要?jiǎng)h除目標(biāo)是根if (cur == root){root = nullptr;delete cur;}// 判斷cur是左右孩子else if (cur->_val < parent->_val){parent->_left = nullptr;delete cur;}else{parent->_right = nullptr;delete cur;}return 1;}else if (!cur->_left || !cur->_right)  // 只有一個(gè)孩子{if (!parent)  // 判斷是否是目標(biāo)是根{root = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}// 判斷cur為啥孩子else if (cur->_val < parent->_val) // 左側(cè){parent->_left = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}else                          // 右側(cè){parent->_right = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}}else   // 有2個(gè)孩子{  // 使用左側(cè)最大的孩子來領(lǐng)養(yǎng)// 尋找左側(cè)最大BST_node* maxnode = cur->_left;BST_node* max_parent = cur;while (maxnode->_right){max_parent = maxnode;maxnode = maxnode->_right;}// 現(xiàn)在又進(jìn)入一種特殊情況,1.max_parent就沒進(jìn)入循環(huán)，2.進(jìn)入了循環(huán)if (max_parent == cur){max_parent->_left = maxnode->_left;}else{max_parent->_right = maxnode->_left;}// 值轉(zhuǎn)移cur->_val = maxnode->_val;delete maxnode;}return 1;}

（2.）遞歸版本

bool Re_Erease( const T& val){return Re_Erease_table(root, val);}bool Re_Erease_table(BST_node*& node, const T& val){// 首先我們先找到值if (node == nullptr){return 0; // 如果訪問到了空，則說明刪除失敗，原因是：不存在}if (val < node->_val){return Re_Erease_table(node->_left, val);}else if (val > node->_val){return Re_Erease_table(node->_right, val);}else{// 開始刪除目標(biāo)數(shù)據(jù)。方法如下；// 1. 就按照非遞歸的思路，不用改多少代碼 // 2. 使用遞歸方法，優(yōu)勢(shì)就是代碼簡(jiǎn)潔// 這里使用方法2BST_node* del = node;  // 保存每次訪問的對(duì)象，如果是目標(biāo)，就備份好了if (node->_left == nullptr){node = node->_right;}else if (node->_right == nullptr){node = node->_left;}else{//處理左右都有孩子的目標(biāo)// 左側(cè)查找最大值，右側(cè)查找最小值BST_node* max_node = node->_left;while (max_node->_right){max_node = max_node->_right;}// 完成循環(huán)后，max_node最多有左孩子，然后數(shù)據(jù)交換，我們以目標(biāo)左側(cè)樹為起點(diǎn)// 再次遞歸刪除替換數(shù)據(jù)。swap(max_node->_val, node->_val);return Re_Erease_table(node->_left, val); //已經(jīng)完成刪除，就直接退出，以免觸發(fā)刪除delete}			//處理前兩種情況delete del;}}

5. 析構(gòu)函數(shù)

思路：

~BSTree(){  Distroy_Re(root);root = nullptr;   }
void Distroy_Re(BST_node*& node) // 我們采用遞歸刪除{if (node == nullptr)return ;// 先處理左右孩子Distroy_Re(node->_left);Distroy_Re(node->_right);delete node;node = nullptr;}

6.拷貝構(gòu)造?

    // 我們實(shí)現(xiàn)了拷貝構(gòu)造，默認(rèn)構(gòu)造函數(shù)則不會(huì)生成 // 解決方案：1.實(shí)現(xiàn)構(gòu)造函數(shù) 2.使用default關(guān)鍵字，強(qiáng)制生成默認(rèn)構(gòu)造BSTree()                 {}// BSTree() = defaultBSTree(const BSTree& Tree) // 拷貝構(gòu)造{root = copy(Tree.root);}BST_node* copy(BST_node* root){if (root == nullptr)return nullptr;BST_node* new_node = new BST_node(root->_val);new_node->_left = copy(root->_left);new_node->_right = copy(root->_right);return new_node;}

?三，應(yīng)用

?四，搜索二叉樹的缺陷及優(yōu)化

最壞情況：N

平均情況：O(logN)

五，代碼匯總

namespace key
{
template <class K>
class BinarySeaTree_node
{typedef BinarySeaTree_node<K> BST_node;
public:BinarySeaTree_node(const K& val): _val(val),_left(nullptr),_right(nullptr){}K _val;BST_node* _left;BST_node* _right;
};template <class T>
class BSTree
{
public:typedef BinarySeaTree_node<T> BST_node;// 我們實(shí)現(xiàn)了拷貝構(gòu)造，默認(rèn)構(gòu)造函數(shù)則不會(huì)生成 // 解決方案：1.實(shí)現(xiàn)構(gòu)造函數(shù) 2.使用default關(guān)鍵字，強(qiáng)制生成默認(rèn)構(gòu)造BSTree(){}// BSTree() = defaultBSTree(const BSTree& Tree) // 拷貝構(gòu)造{root = copy(Tree.root);}BSTree<T>& operator=(BSTree<T> t){swap(root, t.root);return *this;}BST_node* copy(BST_node* root){if (root == nullptr)return nullptr;BST_node* new_node = new BST_node(root->_val);new_node->_left = copy(root->_left);new_node->_right = copy(root->_right);return new_node;}bool Re_Insert(const T& val) { return Re_Insert_table(root, val); }void Re_Print() { Re_Print_table(root); }bool Re_Erease(const T& val) { return Re_Erease_table(root, val); }BST_node* Re_Find(const T& val) { return Re_Find_table(root, val); }bool Insert(const T& val){BST_node* key = new BST_node(val);BST_node* cur = root;BST_node* parent = nullptr;while (cur){if (key->_val < cur->_val){parent = cur;cur = cur->_left;}else if (key->_val > cur->_val){parent = cur;cur = cur->_right;}else{return 0;}}// 查詢好位置后，建立鏈接if (!root){root = key;return 0;}if (key->_val > parent->_val){parent->_right = key;}else{parent->_left = key;}return 1;}BST_node* Find(const T& val){//直接跟尋找位置一樣BST_node* parent = nullptr;BST_node* cur = root; // 以返回cur的方式返回while (cur)   // 非遞歸版本{if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{return cur;}}return cur;}bool Erase(const T& val){//首先尋找到指定值,并且記錄到parentBST_node* parent = nullptr;BST_node* cur = root;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{break;}}if (!cur){return 0;}// 查詢成功,開始刪除if (!cur->_left && !cur->_right) // cur沒有左右孩子{   // 當(dāng)要?jiǎng)h除目標(biāo)是根if (cur == root){root = nullptr;delete cur;}// 判斷cur是左右孩子else if (cur->_val < parent->_val){parent->_left = nullptr;delete cur;}else{parent->_right = nullptr;delete cur;}return 1;}else if (!cur->_left || !cur->_right)  // 只有一個(gè)孩子{if (!parent)  // 判斷是否是目標(biāo)是根{root = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}// 判斷cur為啥孩子else if (cur->_val < parent->_val) // 左側(cè){parent->_left = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}else                          // 右側(cè){parent->_right = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}}else   // 有2個(gè)孩子{  // 使用左側(cè)最大的孩子來領(lǐng)養(yǎng)// 尋找左側(cè)最大BST_node* maxnode = cur->_left;BST_node* max_parent = cur;while (maxnode->_right){max_parent = maxnode;maxnode = maxnode->_right;}// 現(xiàn)在又進(jìn)入一種特殊情況,1.max_parent就沒進(jìn)入循環(huán)，2.進(jìn)入了循環(huán)if (max_parent == cur){max_parent->_left = maxnode->_left;}else{max_parent->_right = maxnode->_left;}// 值轉(zhuǎn)移cur->_val = maxnode->_val;delete maxnode;}return 1;}~BSTree(){Distroy_Re(root);root = nullptr;}protected:bool Re_Insert_table(BST_node*& node, const T& val){if (node == nullptr){node = new BST_node(val);return 1;}if (val < node->_val){return Re_Insert_table(node->_left, val);}else if (val > node->_val){return Re_Insert_table(node->_right, val);}else{return 0;}}void Re_Print_table(const BST_node* node){if (node == nullptr)return;Re_Print_table(node->_left);cout << node->_val << " ";Re_Print_table(node->_right);}BST_node* Re_Find_table(BST_node* node, const T& val){if (node == nullptr)return nullptr;if (val < node->_val){return Re_Find_table(node->_left, val);}else if (val > node->_val){return Re_Find_table(node->_right, val);}else{return node;}}bool Re_Erease_table(BST_node*& node, const T& val){// 首先我們先找到值if (node == nullptr){return 0; // 如果訪問到了空，則說明刪除失敗，原因是：不存在}if (val < node->_val){return Re_Erease_table(node->_left, val);}else if (val > node->_val){return Re_Erease_table(node->_right, val);}else{// 開始刪除目標(biāo)數(shù)據(jù)。方法如下；// 1. 就按照非遞歸的思路，不用改多少代碼 // 2. 使用遞歸方法，優(yōu)勢(shì)就是代碼簡(jiǎn)潔// 這里使用方法2BST_node* del = node;  // 保存每次訪問的對(duì)象，如果是目標(biāo)，就備份好了if (node->_left == nullptr){node = node->_right;}else if (node->_right == nullptr){node = node->_left;}else{//處理左右都有孩子的目標(biāo)// 左側(cè)查找最大值，右側(cè)查找最小值BST_node* max_node = node->_left;while (max_node->_right){max_node = max_node->_right;}// 完成循環(huán)后，max_node最多有左孩子，然后數(shù)據(jù)交換，我們以目標(biāo)左側(cè)樹為起點(diǎn)// 再次遞歸刪除替換數(shù)據(jù)。swap(max_node->_val, node->_val);return Re_Erease_table(node->_left, val); //已經(jīng)完成刪除，就直接退出，以免觸發(fā)刪除delete}// 查找到刪除數(shù)據(jù)delete del;}}void Distroy_Re(BST_node*& node) // 我們采用遞歸刪除{if (node == nullptr)return;// 先處理左右孩子Distroy_Re(node->_left);Distroy_Re(node->_right);delete node;node = nullptr;}
private:BST_node* root = nullptr;};
}

結(jié)語

? ?本小節(jié)就到這里了，感謝小伙伴的瀏覽，如果有什么建議，歡迎在評(píng)論區(qū)評(píng)論，如果給小伙伴帶來一些收獲請(qǐng)留下你的小贊，你的點(diǎn)贊和關(guān)注將會(huì)成為博主創(chuàng)作的動(dòng)力