【c++進階系列】：萬字詳解二叉搜索樹（附源碼實現）

🔥 本文專欄：c++
🌸作者主頁：努力努力再努力wz

在這里插入圖片描述

💪 今日博客勵志語錄： 你可以走得慢，但別回頭

1.概念

二叉搜索樹，從其名字我們就能知道該數據結構是一個特殊的二叉樹，而二叉搜索樹這個數據結構的核心不是在于存儲數據，而是在于高效的查找數據，那么如何高效的查找數據呢，那么就和二叉搜索樹結構本身的性質有關：

左孩子節點的值小于根節點的值，右孩子節點的值大于根節點的值，并且對于其左右子樹也遞歸的滿足該性質

所以從二叉搜索樹開始往后的數據結構的學習，那么我們就要更多接觸到關聯式容器而不是序列式容器，那么所謂的關聯式容器，就是存儲在容器中的數據之間是有聯系的，比如這里的二叉搜索樹中存儲在節點中的值的關系是左小右大，也就是左子樹中所有節點的值一定都是小于右子樹中所有節點的值，而所謂序列式容器就是存儲在容器中的元素彼此之間沒有任何聯系，那么序列式容器的代表就包括底層采取動態數組實現的vector以及底層采取帶頭雙向循環鏈表實現的list

那么二叉搜索樹之所以要滿足這個性質，目的就是為了方便查找，接下來我將引入一個場景，來讓讀者認識到二叉搜索樹的這個性質的意義：

假設現在有一個二叉搜索樹，其節點中存儲的數據的類型是整形，那么這里我們要查找該二叉搜索樹中是否存在值為80的節點，那么此時要查找這個值，那么我們就要遍歷這棵二叉樹，而如果這里我采取的是傳統的二叉樹來存儲數據，那么要查找該值是否存在，那么我就只能深度優先遍歷，依次訪問該二叉樹中的所有的節點，而如果這里采取的是二叉搜索樹來實現的話，那么這里我就可以利用二叉搜索樹的性質，先從根節點往下遍歷，遍歷之前，我會先比較該值與根節點的大小，因為二叉搜索樹的性質是左小右大，左孩子的值是小于根節點，右孩子的值是大于根節點，所以如果當前該值大于根節點，那么意味著我們接下來要去往右子樹遍歷，而如果小于根節點，那么意味著我們則要去往左子樹往下遍歷，而二叉樹是一個遞歸的結構，每一個子樹又可以視作看成由根節點和左子樹和右子樹三部分組成的二叉樹，那么接下來就重復上面的步驟，繼續比較根節點，確定遍歷的分支，直到找到匹配值的節點或者遍歷到空節點結束，而遍歷到空節點意味著當前二叉搜索樹中沒有該值的節點存在

那么在回顧上面的過程，我們可以發現二叉搜索樹能夠實現高效查找的原因就是因為其左小右大的性質，那么我們每一次遍歷都可以排除一個子樹分支，那么相比于傳統的二叉樹的遍歷，那么這里二叉搜索樹能夠極大的減少我們的搜索量，并且我們可以發現這個過程其實和我們的二分查找是一樣的，二分查找的思想就是在一個有序序列中，將查找的目標值與中間位置的值相比較，如果大于就到右側(假設為升序的有序序列），小于就到左側，每次比較，都會將查找的范圍給減半，所以二叉搜索樹的查詢的核心就是一個二分的思想，通過其結構本身的性質來實現

那么這里有的讀者可能會疑惑，那么他知道這里二叉搜索樹的優勢不在于存儲數據，而是在于查找數據，并且它理解到了二叉搜索樹查找數據的核心思想就是二分，那么這里為什么不直接選取數組作為底層存儲數據的容器，然后將數組中的元素排成有序，然后最后借助二分查找來實現元素的查找，這種方式也可以實現高效的查找，但是我們會發現很多關聯式容器底層并沒有采取這種方式，而是采取的是二叉搜索樹，那么原因或者說二叉搜索樹相比于剛才的這種實現方式的優點在哪里呢？

選擇數組作為底層的容器，那么首先你得將數組中存儲的所有元素給排序，那么如果采取的是快排來實現，那么快排的時間復雜度是o(N*logN)，而排序倒不是影響該實現方式的時間效率的主要因素，因為排序只用排一次，那么其付出的時間代價可以分攤到每一次的查找以及插入和刪除操作當中去，而真正影響效率的其實是插入和刪除操作
那么在插入和刪除某個元素之前，那么你得首先找到插入以及刪除的元素的位置，那么這個查找的時間代價就是o(logN)，也就是二分查找的時間復雜度，那么查找到元素的位置之后，那么接下來你要做的，就是插入以及刪除元素，由于是數組，那么必然要涉及大量元素的挪動，那么這部分的時間代價則是O(N),所以插入以及刪除總的時間代價是O(N+logN)

而對于二叉搜索樹來說，那么其也有元素的插入以及刪除操作，那么同樣在刪除之前，也得先找到目標元素在該二叉搜索樹中的位置，而這里的查找的次數最多就是二叉樹的高度次，所以很多讀者會誤認為這里的查找的時間復雜度是O(logN)，因為二叉樹的高度是logN,但事實上這里的時間復雜度是O(N)，因為如果二叉樹中存儲的節點的值是一個單調遞增或者遞減的一個序列，那么在這種情況下，會使該二叉搜索樹的結構成為一個類似于單鏈表的結構，那么其高度就是節點個數

而時間復雜度是估計最壞情況，所以這里的查找的時間復雜度應該是O(N),那么一旦查找到目標元素的位置，那么接下來由于二叉樹的節點之間直接是通過指針來連接，那么這里的插入和刪除只需要修改指針之間的鏈接關系即可，那么這部分的時間代價為O(1)，所以對于二叉搜索樹來說，那么插入和刪除的總代價就是O(N)，那么相比于上面的這種方式來說，綜合來說還是二叉搜索樹的效率更高

通過剛才的講解，那么讀者知道了，二叉搜索樹的查找效率其實取決于二叉樹的形態，那么我們更希望二叉樹的形態是趨近于扁平的形態而不是一種高瘦的形態，所以后面我們還會學習AVL樹以及紅黑樹，那么這兩個數據結構就是在傳統的二叉搜索樹的基礎上進行改善，來調整二叉搜索樹的結構

介紹完了二叉搜索樹的概念，那么接下來我們便要自己來嘗試實現一個二叉搜索樹，其中核心便是實現查找以及刪除和插入這三個操作，那么在寫代碼實現之前，那么我們還是會先認識原理，然后再來動手實現

2.實現

那么由于二叉搜索樹不一定是一棵完全二叉樹，所以這里底層實現該二叉搜索樹的時候，那么底層只能采取鏈式的二叉樹來實現，除非像堆這樣的特殊的二叉樹，那么其結構一定滿足是一棵完全二叉樹，那么其采取的就是數組方式實現

那么既然是鏈式結構，那么這里我們就要首先先定義出二叉樹的節點，那么該節點有兩個指針域，分別指向其左右孩子，還包括一個數據域，那么這里我們可以定義成一個struct BinaryTreenode結構體，也可以將其定義為BinaryTreenode類，但要注意類里面的成員變量以及構造函數都得是public修飾，因為接下來我們要再定義一個BinarysearchTree類，里面會封裝一個指向根節點的指針，那么我們會在該類的成員函數中比如insert插入函數以及remove刪除函數，直接訪問該節點的指向左右孩子節點的指針來遍歷該二叉搜索樹，以及修改節點之間的鏈接關系，需要在類外部直接訪問到Binarytreenode類中的指針成員變量

那么你也完全可以將該BinaryTreenode類中的所有成員變量設置為私有，然后對類外部提供一個公有的接口來訪問，而這里我們其實只需將BinarysearchTree類中將成員變量也就是指向根節點的指針以及將指向BinaryTreenode節點的指針類型的typedef的別名都設置為私有，那么你也不用擔心類外部能夠直接訪問以及創建該節點，所以建議還是將節點類的中成員變量設置為公有

template<typename T>
class  BinaryTreeNode
{
public:BinaryTreeNode<T>* left;BinaryTreeNode<T> * right;T key;BinaryTreeNode(T _key=T()):left(nullptr), right(nullptr), key(_key){}
};
template<typename T>
class BinarysearchTree
{private:typedef BinaryTreeNode<T>* Node;Node root;
};

那么接下來就是完善binarysearchTree類中的成員函數了，那么首先就是我們的構造函數

構造函數

那么這里二叉搜索樹的構造函數分為無參以及帶參的，那么帶參的就是開辟根節點并且給根節點一個初始值，而無參的構造函數就是開辟一棵空樹

BinarysearchTree():root(nullptr)
{}
BinarysearchTree(T key)
{root = new BinaryTreeNode<T>(key);
}

search函數

那么這里search函數就是該查找該二叉搜索樹中是否存在目標值的節點，如果存在，那么就返回true，不存在就返回false，那么search函數的實現有兩種方式，分別是遞歸以及非遞歸，那么這里我們先講解search函數的遞歸實現，那么由于我們知道二叉搜索樹的性質是左小右大，那么這里我們先比較目標值與根節點的值，然后確定遞歸的子樹，如果小于就遞歸到左子樹，大于就遞歸到右子樹然后再重復該步驟，而如果值匹配就直接返回true，而如果到達了空節點，那么則說明二叉搜索樹沒有該目標值，直接返回false，而遞歸版本的search函數要從根節點開始往下遍歷，也就是需要傳遞一個指向根節點的指針，而指向根節點的指針是給BinarysearchTree類中的私有成員變量，那么為了避免在類外面需要傳遞指向根節點的指針給改成員函數，所以這里我定義了一個共有的searchR成員函數，然后內部調用私有的SearchR成員函數，然后將指向根節點的指針直接傳遞給SearchR成員函數，那么后面的遞歸版本的插入以及刪除成員函數也會采取這種方式

bool searchR(const T&val)
{return SearchR(root, val);
}
bool SearchR(Node _root, const T& val)
{if (_root == nullptr){return false;}if (val < _root->key){return SearchR(_root->left, val);}else if (val > _root->key){return SearchR(_root->right, val);}else{return true;}
}

而非遞歸版本的思路和遞歸的思路是一樣的，就是利用二叉搜索樹的性質，每次與根節點比較，然后確定遍歷的子樹，只不過這里我們需要定義一個指針，然后用該指針來往下依次遍歷

bool search(const T& val)
{Node cur = root;while (cur){if (val < cur->key){cur = cur->left;}else if (val > cur->key){cur =cur->right;}else{return true;}}return false;
}

insert函數

那么insert函數就是向二叉搜索樹中插入一個目標值的節點，我們也可以采取使用非遞歸以及遞歸兩種方式來實現，那么我們先來說非遞歸的實現原理，那么insert函數的實現思路其實我們可以分為兩個步驟，第一步我們得確定插入的節點在二叉搜索樹的位置，不能隨意插入，因為要維護二叉搜索樹的左小右大的性質，那么這里就需要我們找到其新插入節點的父節點，找到父節點之后，第二步就是在開辟一個新節點，然后讓父節點的左指針或者右指針連接該節點即可

那么第一個步驟的原理和剛才講的search函數是一樣的，那么這里我們定義一個cur指針和parent，那么cur指針則用于遍歷，那么它最開始指向根節點，然后從根節點往下遍歷，那么往下遍歷之前，那么都需要將目標值與cur指向當前的根節點的值比較，確定下一次遍歷的分支是左分支還是右分支，那么確定好分支之后，那么在cur移動到左孩子節點或者右孩子節點之前，那么它會將值先賦值給parent，那么等cur指向空節點的時候，無法往下遍歷，那么此時parent指向的節點就是新插入節點的父節點，而如果cur指向的值與目標值匹配，那么說明該二叉搜索樹中已經存在了該目標值的節點，那么就沒必要往下遍歷以及執行后續的插入工作，直接return返回即可

Node parent = nullptr;
Node cur = root;
while (cur) {if (val < cur->key){parent = cur;cur = cur->left;}else if (val > cur->key){parent = cur;cur = cur->right;}else {return;}..................
}

那么第一個步驟結束，parentz會指向新插入節點的父節點，那么下一步就是開辟一個新的節點，然后讓父節點左指針或者右指針指向新開辟的節點從而將其連接進二叉搜索樹，但是這里有一個問題，就是新插入的節點究竟應該是父節點的左指針指向該節點還是右指針，所以這里就需要判斷，那么判斷方式的是利用二叉搜索樹的性質，我們直接將目標值與parent指向的父節點的值比較，小于就說明用左指針鏈接，其應該位于父節點的左子樹中，大于就用父節點的右指針連接

判斷完之后就開辟節點，然后連接即可

void insert(const T& val)
{if (root == nullptr){root = new BinaryTreeNode<T>(val);return;}Node parent = nullptr;Node cur =root;while (cur) {if (val < cur->key){parent = cur;cur = cur->left;}else if (val > cur->key){parent = cur;cur = cur->right;}else {return;}}cur = new BinaryTreeNode<T>(val);if (val < parent->key){parent->left = cur;}else{parent->right = cur;}
}

那么遞歸版本實現思路還是那兩個步驟，首先是找到新插入節點的父節點，然后再開辟新節點與父節點連接，那么第一個步驟其實可以復用search函數的遞歸實現的代碼，那么這里關鍵是第二個步驟，也就是連接，那么這里遞歸版本的InsertR函數接收兩個參數，分別是指向當前根節點的指針_root以及目標值val，假設該二叉搜索樹沒有該目標值的節點，那么當遍歷到空節點位置的時候，那么由于二叉樹的每一個節點只保存指向左右孩子的兩個指針，沒有指針指向父節點，那么要找到新插入節點的父節點，那么第一種方式是需要額外增加一個參數來保存 _root移動到左右孩子節點之前的值，但是采取這種方式，那么就和非遞歸的思路是一模一樣了，還不如直接用非遞歸

InsertR(Node* _root,const T& val)if (val < _root->key){return InsertR(_root->left, val);}else if (val > _root->key){return InsertR(_root->right, val);}else{return;}
.....................
}

而第二種方式則是最為推薦也是最巧妙的，那么就是將這里InsertR函數的第一個參數，也就是指向根節點的指針改為引用，因為這里每一次往下遞歸的時候，我傳遞的實參都是當前根節點的指向左孩子或者右孩子的指針，那么這里 _root引用就是父節點的左右指針的別名，那么對引用的修改就等同于對父節點的左右指針本身的修改，那么這里意味著我們要連接，直接將新開辟的節點賦值給該引用即可，那么就等同于將給父節點的左右指針賦值，甚至不用判斷應該連接到父節點的左分支還是右分支

void InsertR(Node& _root, const T& val)
{if (_root == nullptr){Node newnode = new BinaryTreeNode<T>(val);_root = newnode;return;}if (val < _root->key){return InsertR(_root->left, val);}else if (val > _root->key){return InsertR(_root->right, val);}else{return;}
}

remove函數

那么remove函數就是刪除二叉搜索樹中任意一個節點的函數，那么同樣也分為遞歸版本和非遞歸版本，那么插入和查找這兩個成員函數的實現還是較為容易，而真正有一點難度的則是刪除函數

那么這里要注意二叉搜索樹的刪除不是像鏈表那樣直接刪除某個節點，然后將后繼節點直接鏈接到刪除節點的前驅節點，那么這里二叉搜索樹的某個節點的刪除，那么刪完還要保證二叉搜索樹整體的一個性質，那么這里我們可以將二叉搜索樹的節點的刪除分為三種情況，那么第一種情況就是刪除的節點的左子樹為空，第二種情況是刪除的節點的右子樹為空，那么第三種情況就是刪除的節點的左右子樹都不為空

其中第一種以及第二種情況我們都可以歸為一種方式來處理，那么該方式便是托孤，所謂的托孤，就是將該節點刪除之后，而該刪除的節點之后的子樹我們可以直接連接到其被刪除節點的父節點的原有分支上，那么這里我舉一個例子：

假設刪除的節點a的左子樹不為空，刪除的節點a的父節點為b，并且節點a是節點b的左孩子，那么這里我們可以直接刪除節點a并且將節點a的左子樹直接連接到節點b的左分支上，那么這種方式就是托孤

托孤這個名字就很形象的體現了如何處理被刪除節點的左子樹或者右子樹，那么直接將其交給其父節點，也就是連接到父節點，原本父節點指向被刪除的節點的指針，將其修改來指向其非空子樹

那么這里我們再來說一下為什么這里能夠采取托孤的做法來刪除該節點，那么我們知道刪除的該節點包括其左子樹或者右子樹的所有節點一定是屬于其刪除節點的父節點的某個分支，如果屬于左分支，那么該刪除的該節點包括之后的左子樹或者右子樹的所有節點都小于刪除節點的父節點，而如果屬于右分支，那么則是都大于其刪除節點的父節點，而刪除的要求就是不能破壞二叉搜索樹的左小右大的性質，那么我們將被刪除節點的子樹還是連接到原有的分支上，那么這里局部還是滿足左大右小的性質，所以此時整個二叉搜索樹整體的性質并不會破壞，所以這里能夠采取這種托孤的方式

而有的讀者在想問那么這里為什么不討論葉子節點的刪除，那么其實葉子節點就可以歸為第一種或者第二種情況的特例，也就是左子樹為空或者右子樹為空，那么采取的方式一樣是托孤，只不過這里托付給被刪除節點的父節點的子樹是空

左子樹為空：

右子樹為空：

但是一旦刪除的節點的左右子樹都不為空，那么此時處理的方式就不同，那么這里我們就不能像上面那樣繼續采取托孤，因為刪除的父節點的左分支或者右分支只能接收一個子樹而不能同時接收左子樹和右子樹，如果可以那就成三叉樹了，而我們知道二叉樹結構最大的特點就是其是一個遞歸的結構，那么整棵二叉樹是由根節點以及左子樹和右子樹這三部分組成，而對于左子樹和右子樹，那么其同樣也可以視作由這三部分組成，而對于二叉搜索樹來說，那么其性質也是遞歸滿足的，整體滿足左小右大，并且再其左右子樹也滿足該性質

所以只要我們能夠讓二叉搜索樹的每一個局部都滿足該性質，那么自然整體就能滿足該性質，那么該思想其實就是分治的思想，所謂的分治可以將一個原問題給分解為若干個更小規模的子問題，那么只要將局部的子問題給解決，那么子問題的解作為下一個更大規模的子問題的解，那么最終將規模擴大到整個問題，那么原問題的解就能得出

所以這里我們可以將這里的刪除節點的左子樹和右子樹重新構建出一顆滿足性質的局部的二叉搜索樹，那么再將其連接到刪除的節點的父節點當中，而被刪除的節點包括其左右子樹中的所有節點都屬于被刪除節點的父節點的左分支或者右分支，那么這里構建完一棵局部的二叉搜索樹之后再連接到被刪除節點的所處的原分支下，那么此時這里更大規模的局部二叉搜索樹依然滿足其左小右大的性質，而其他部分都滿足該性質，那么自然整體就滿足該性質

而這里構建局部二叉搜索樹方方式就是找到左子樹最大的或者右子樹最小的節點 來替換被刪除的父節點，之所以選擇這兩個節點的原因就是替換之后該局部二叉搜索樹就符合左小右大的性質

那么左子樹最大的節點就是位于整個左子樹的最右側的節點，而右子樹的最小的節點就是位于整棵子樹的最左側，那么我們將左子樹的中最右側節點的值或者右子樹最左側節點的值與刪除節點的值交換

那么這種方式類似于堆的刪除根節點的處理方式，但是這里替換完之后，那么我們還要刪除被替換后的左子樹的最右側節點或者右子樹的最左側節點，而這里注意左子樹的最右側的節點一定要么是葉子節點要么是一個右子樹為空但左子樹不為空的節點，如果其還有右子樹，那么必然與其是最右側節點相矛盾，右子樹的最左側節點也同理，其一定是葉子節點或者只有右子樹非空的節點

所以這里要刪除替換之后的左子樹的最右側節點或者右子樹的最左側節點，那么就可以按照第一種方式，也就是托孤的方式來刪除

左右子樹都不為空：

那么接下來在說如何用代碼來具體實現了，首先是非遞歸版本的實現，那么這里第一個步驟還是找到被刪除的節點以及刪除節點的父節點，那么這部分代碼的邏輯的實現我們可以定義兩個指針變量parent和cur，那么cur用來往下遍歷，而每一次cur指向左孩子或者右孩子之前，那么都會現將值賦給parent，那么一旦找到目標值，那么此時cur指向的就是被刪除節點，而parent指向的就是其父節點

void remove(const T& val){
Node parent = nullptr;
Node cur =root;
while (cur)
{if (val < cur->key){parent = cur;cur = cur->left;}else if (val > cur->key){parent = cur;cur = cur->right;}else{break;}
}if(cur==nullptr){return;}.............................
}

而找到刪除的目標階段，下一步便是判斷此時刪除節點的情況，是左子樹為空還是右子樹為空還是左右子樹都不為空，而對于左子樹為空，那么處理方式就是將其右子樹連接到刪除節點的父節點，但是這里還是要額外判斷一下是連接到父節點的左側還是右側，那么可以比較一下刪除節點的值與父節點的值來確定，而右子樹為空，則是將左子樹連接到刪除節點的父節點，連接之前一樣判斷其是連接父節點的左側還是右側

if (cur->left == nullptr)
{if (cur == root){root = cur->right;delete cur;return;}else {if (cur->key < parent->key){parent->left = cur->right;}else if (cur->key > parent->key){parent->right = cur->right;}delete cur;return;}
}
else if (cur->right == nullptr)
{if (cur == root){root = cur->left;delete cur;return;}else {if (cur->key < parent->key){parent->left = cur->left;}else if (cur->key > parent->key){parent->right = cur->left;}delete cur;return;}
}

那么這里要注意如果這里是刪除的整個二叉搜索樹的根節點，那么這里進入while循環后會直接break退出，那么此時parent還是nullptr，所以這里我們如果我們不判斷當前刪除的節點是否是根節點，那么就會解引用空指針

而如果此時刪除的節點左右子樹不為空，那么就可以找左子樹的最右側節點或者右子樹的最左側節點，這里我是找左子樹的最右側節點，那么這里我定義了一個leftMax指針來遍歷找到左子樹的最右側節點，而leftMaxParent則是記錄其父節點，找到之后，左子樹的最右側節點再與刪除的節點進行值的交換，最后在刪除leftMax指向的節點，那么采取的方式就是托孤

Node leftMaxParent=cur;
Node leftMax = cur->left;
while (leftMax->right)
{leftMaxParent = leftMax;leftMax = leftMax->right;
}
std::swap(leftMax->key, cur->key);
if (leftMaxParent->key > leftMax->key)
{leftMaxParent->left = leftMax->left;
}
if (leftMaxParent->key < leftMax->key)
{leftMaxParent->right = leftMax->left;
}
delete leftMax

那么這里再來說一下遞歸實現，那么遞歸實現的第一個步驟還是找到刪除的目標節點與其父節點，那么遞歸的方式想必讀者現在已經很熟悉了：

void RemoveR(Node& _root,const T& val)
{if (_root == nullptr)
{return;
}
if (val < _root->key)
{return RemoveR(_root->left, val);
}
else if (val > _root->key)
{return RemoveR(_root->right, val);
}.......................
}

那么接下來就是判斷刪除節點的情況，那么這里注意由于我們將參數設置為了引用，那么我們每次調用該遞歸函數傳遞的參數都是節點的左指針或者右指針，那么該引用就是節點的左指針或者右指針的別名，那么我們對引用的各種行為就是對節點的左右指針本身進行修改，所以這里我們不需要判被刪除的節點的子樹是連接在其父節點的左側還是右側，那么直接賦值即可，并且對于根節點這里也不需要特判，如果刪除的是根節點，那么引用直接就是指向根節點的指針的別名

if (_root->left == nullptr)
{Node cur = _root;_root = _root->right;delete cur;return;
}
if (_root->right == nullptr)
{Node cur = _root;_root = _root->left;delete cur;return;
}

而如果刪除的節點的左右子樹都存在，那么這里還是定義一個變量leftMAx用來記錄左子樹的最右側節點，然后遍歷左子樹，找到到左子樹的最右側節點，然后再交換值，但是這里我的代碼并沒有選擇交換，而是直接將左子樹的最右側節點的值賦值給刪除的節點，由于我接下來要刪除左子樹的最右側節點，而上文我們就分析過，那么該節點要么是葉子節點，要么只有其左子樹不為空，那么這里我們可以直接復用RemoveR函數來刪除該節點，所以不能破壞其左子樹的左小右大的性質，所以這里我沒有選擇交換，但要注意這里再一次調用RemoveR函數時，傳遞給該函數的參數不能是leftMax，因為如果被刪除節點的左子樹只有一個節點，那么這里引用指向的是leftMax這個局部變量的別名，而不是刪除節點的左指針的別名，所以無法修改指針的連接關系，這點要注意

Node leftMax = _root->left;
while (leftMax->right)
{leftMax = leftMax->right;
}
_root->key = leftMax->key;
RemoveR(_root->left, leftMax->key);

拷貝構造函數

那么拷貝構造函數這里我們就是采取前序遍歷來依次拷貝目標對象中節點中的值，至于前序遍歷拷貝的這部分內容，我專門將其定義到了copy函數中

BinarysearchTree(const BinarysearchTree& T)
{copy(root, T.head);
}
void copy(Node& l1, const Node& l2)
{if (l2 == nullptr){l1=nullptr;return;}l1=new BinaryTreeNode<T>;l1->key = l2->key;copy(l1->left, l2->left);copy(l1->right, l2->right);return;
}

賦值運算符重載函數

那么賦值運算符重載函數，因為實參傳遞給形參會先將值拷貝給形參，那么這里我們直接與形參的head成員變量的值交換，那么一旦函數調用結束，那么形參被銷毀，而形參內的值是被交換后的值，所以這里可以采取這種方式巧妙的實現賦值運算符重載函數

	BinarysearchTree& operator=(BinarysearchTree T){std::swap(root, T.root);return *this;}

析構函數

那么由于這里二叉搜索樹中的每一個節點都是在堆上申請的，所以這里我們需要釋放每一個節點，那么我們釋放的順序就是采取后序遍歷，然后先釋放釋放左子樹中的所有節點，然后再釋放右子樹中的所有節點，最后再釋放根節點

~BinarysearchTree()
{destroyTree(root);
}
void destroyTree(Node _root)
{if (_root == nullptr){return;}destroyTree(_root->left);destroyTree(_root->right);delete _root;
}

源碼

BinarysearchTree.h

#pragma once
#include<algorithm>
#include<iostream>
using std::cout;
using std::endl;
template<typename T>
class  BinaryTreeNode
{
public:BinaryTreeNode<T>* left;BinaryTreeNode<T> * right;T key;BinaryTreeNode(T _key=T()):left(nullptr), right(nullptr), key(_key){}
};
template<typename T>
class BinarysearchTree
{
public:BinarysearchTree():root(nullptr){}BinarysearchTree(T key){root = new BinaryTreeNode<T>(key);}BinarysearchTree(const BinarysearchTree& t){copy(root, t.root);}~BinarysearchTree(){destroyTree(root);}BinarysearchTree& operator=(BinarysearchTree T){std::swap(root, T.root);return *this;}void insert(const T& val){if (root == nullptr){root = new BinaryTreeNode<T>(val);return;}Node parent = nullptr;Node cur = root;while (cur) {if (val < cur->key){parent = cur;cur = cur->left;}else if (val > cur->key){parent = cur;cur = cur->right;}else {return;}}cur = new BinaryTreeNode<T>(val);if (val < parent->key){parent->left = cur;}else{parent->right = cur;}}bool search(const T& val){Node cur = root;while (cur){if (val < cur->key){cur = cur->left;}else if (val > cur->key){cur =cur->right;}else{return true;}}return false;}void remove(const T& val){Node parent = nullptr;Node cur = root;while (cur){if (val < cur->key){parent = cur;cur = cur->left;}else if (val > cur->key){parent = cur;cur = cur->right;}else{break;}}if (cur == nullptr){return;}if (cur->left == nullptr){if (cur == root){root = cur->right;delete cur;return;}else {if (cur->key < parent->key){parent->left = cur->right;}else if (cur->key > parent->key){parent->right = cur->right;}delete cur;return;}}else if (cur->right == nullptr){if (cur == root){root = cur->left;delete cur;return;}else {if (cur->key < parent->key){parent->left = cur->left;}else if (cur->key > parent->key){parent->right = cur->left;}delete cur;return;}}Node leftMaxParent=cur;Node leftMax = cur->left;while (leftMax->right){leftMaxParent = leftMax;leftMax = leftMax->right;}std::swap(cur->key,leftMax->key);if (leftMaxParent->key > leftMax->key){leftMaxParent->left = leftMax->left;}if (leftMaxParent->key < leftMax->key){leftMaxParent->right = leftMax->left;}delete leftMax;}bool searchR(const T&val){return SearchR(root, val);}void insertR(const T& val){InsertR(root, val);}void removeR(const T& val){RemoveR(root, val);}void Inorder(){InorderTree(root);}
private:typedef BinaryTreeNode<T>* Node;Node root;void copy(Node& l1, const Node& l2){if (l2 == nullptr){l1 = nullptr;return;}l1 = new BinaryTreeNode<T>;l1->key = l2->key;copy(l1->left, l2->left);copy(l1->right, l2->right);return;}void InsertR(Node& _root, const T& val){if (_root == nullptr){Node newnode = new BinaryTreeNode<T>(val);_root = newnode;return;}if (val < _root->key){return InsertR(_root->left, val);}else if (val > _root->key){return InsertR(_root->right, val);}else{return;}}void InorderTree(Node cur){if (cur == nullptr){return;}InorderTree(cur->left);cout << cur->key << " ";InorderTree(cur->right);}void RemoveR(Node& _root, const T& val){if (_root == nullptr){return;}if (val < _root->key){return RemoveR(_root->left, val);}else if (val > _root->key){return RemoveR(_root->right, val);}else{if (_root->left == nullptr){Node cur = _root;_root = _root->right;delete cur;return;}if (_root->right == nullptr){Node cur = _root;_root = _root->left;delete cur;return;}Node leftMax = _root->left;while (leftMax->right){leftMax = leftMax->right;}_root->key = leftMax->key;RemoveR(_root->left, leftMax->key);}}bool SearchR(Node _root, const T& val){if (_root == nullptr){return false;}if (val < _root->key){return SearchR(_root->left, val);}else if (val > _root->key){return SearchR(_root->right, val);}else{return true;}}void destroyTree(Node _root){if (_root == nullptr){return;}destroyTree(_root->left);destroyTree(_root->right);delete _root;}
};

main.cpp

#include"BinarysearchTree.h"
#include <iostream>
#include <cassert>
#include <string>using namespace std;void runTests() {// 1. 構造函數測試{// 默認構造函數BinarysearchTree<int> bst1;assert(bst1.search(1) == false);// 單元素構造函數BinarysearchTree<int> bst2(5);assert(bst2.search(5) == true);assert(bst2.search(1) == false);// 拷貝構造函數BinarysearchTree<int> bst3;bst3.insert(5);bst3.insert(3);bst3.insert(7);BinarysearchTree<int> bst4(bst3);assert(bst4.search(5) == true);assert(bst4.search(3) == true);assert(bst4.search(7) == true);assert(bst4.search(1) == false);cout << "Constructor tests passed!" << endl;}// 2. 賦值運算符測試{BinarysearchTree<int> bst1;bst1.insert(5);bst1.insert(3);bst1.insert(7);BinarysearchTree<int> bst2;bst2 = bst1;assert(bst2.search(5) == true);assert(bst2.search(3) == true);assert(bst2.search(7) == true);// 測試自我賦值bst2 = bst2;assert(bst2.search(5) == true);cout << "Assignment operator tests passed!" << endl;}// 3. 插入操作測試{// 插入空樹BinarysearchTree<int> bst1;bst1.insert(5);assert(bst1.search(5) == true);// 插入多個元素BinarysearchTree<int> bst2;bst2.insert(5);bst2.insert(3);bst2.insert(7);bst2.insert(6);bst2.insert(8);assert(bst2.search(5) == true);assert(bst2.search(3) == true);assert(bst2.search(7) == true);assert(bst2.search(6) == true);assert(bst2.search(8) == true);assert(bst2.search(1) == false);// 重復插入BinarysearchTree<int> bst3;bst3.insert(5);bst3.insert(5);assert(bst3.search(5) == true);bst3.remove(5);assert(bst3.search(5) == false);cout << "Insert tests passed!" << endl;}// 4. 搜索操作測試{// 空樹搜索BinarysearchTree<int> bst1;assert(bst1.search(5) == false);// 搜索存在的元素BinarysearchTree<int> bst2;bst2.insert(5);bst2.insert(3);bst2.insert(7);assert(bst2.search(5) == true);assert(bst2.search(3) == true);assert(bst2.search(7) == true);// 搜索不存在的元素assert(bst2.search(1) == false);assert(bst2.search(9) == false);cout << "Search tests passed!" << endl;}// 測試刪除操作{// 從空樹刪除BinarysearchTree<int> bst1;bst1.remove(5);assert(bst1.search(5) == false);// 刪除葉子節點BinarysearchTree<int> bst2;bst2.insert(5);bst2.insert(3);bst2.insert(7);bst2.remove(3);assert(bst2.search(3) == false);assert(bst2.search(5) == true);assert(bst2.search(7) == true);// 刪除有一個子節點的節點BinarysearchTree<int> bst3;bst3.insert(5);bst3.insert(3);bst3.insert(2);bst3.insert(7);bst3.remove(3); // 有一個左孩子assert(bst3.search(3) == false);assert(bst3.search(2) == true);bst3.insert(8);bst3.remove(7); // 有一個右孩子assert(bst3.search(7) == false);assert(bst3.search(8) == true);// 刪除有兩個子節點的節點 - 修改后的測試BinarysearchTree<int> bst4;bst4.insert(5);bst4.insert(3);bst4.insert(7);bst4.insert(6);bst4.insert(8);// 驗證樹仍然包含其他節點assert(bst4.search(3) == true);assert(bst4.search(7) == true);assert(bst4.search(6) == true);assert(bst4.search(8) == true);// 刪除根節點BinarysearchTree<int> bst5;bst5.insert(5);bst5.remove(5);assert(bst5.search(5) == false);bst5.insert(5);bst5.insert(3);bst5.remove(5);assert(bst5.search(5) == false);assert(bst5.search(3) == true);cout << "Remove tests passed!" << endl;}// 6. 遞歸操作測試{// 遞歸插入BinarysearchTree<int> bst1;bst1.insertR(5);bst1.insertR(3);bst1.insertR(7);bst1.insertR(6);bst1.insertR(8);assert(bst1.searchR(5) == true);assert(bst1.searchR(3) == true);assert(bst1.searchR(7) == true);assert(bst1.searchR(6) == true);assert(bst1.searchR(8) == true);assert(bst1.searchR(1) == false);// 遞歸刪除BinarysearchTree<int> bst2;bst2.insert(5);bst2.insert(3);bst2.insert(7);bst2.insert(6);bst2.insert(8);bst2.removeR(5);assert(bst2.searchR(5) == false);assert(bst2.searchR(3) == true);assert(bst2.searchR(7) == true);assert(bst2.searchR(6) == true);assert(bst2.searchR(8) == true);// 遞歸搜索BinarysearchTree<int> bst3;bst3.insert(5);bst3.insert(3);bst3.insert(7);assert(bst3.searchR(5) == true);assert(bst3.searchR(3) == true);assert(bst3.searchR(7) == true);assert(bst3.searchR(1) == false);cout << "Recursive operation tests passed!" << endl;}{// 大型樹測試BinarysearchTree<int> bst1;for (int i = 0; i < 1000; ++i) {bst1.insert(i);}for (int i = 0; i < 1000; ++i) {assert(bst1.search(i) == true);}for (int i = 0; i < 1000; i += 2) {bst1.remove(i);}for (int i = 0; i < 1000; ++i) {assert(bst1.search(i) == (i % 2 == 1));}// 字符串類型測試BinarysearchTree<string> bst2;bst2.insert("apple");bst2.insert("banana");bst2.insert("cherry");assert(bst2.search("apple") == true);assert(bst2.search("banana") == true);assert(bst2.search("cherry") == true);assert(bst2.search("date") == false);bst2.remove("banana");assert(bst2.search("banana") == false);cout << "Boundary tests passed!" << endl;}cout << "All tests passed successfully!" << endl;
}int main() {runTests();return 0;
}

運行截圖：
在這里插入圖片描述

應用

那么文章的最后，那么我就來談論一下二叉搜索樹的一個應用場景，那么二叉搜索樹是一個key模型，那么一般是用于判斷某個元素是否存在，所以二叉搜索樹可以用作人臉識別，那么將其身份信息作為二叉搜索樹的一個節點，而往后我們則還要學key-value模型，那么這里二叉搜索樹存儲的是一個元組，那么比較則是通過key值進行比較