C++二叉查找樹實現過程詳解
什么是二叉查找樹
在數據結構中，有一個奇葩的東西，說它奇葩，那是因為它重要，這就是樹。而在樹中，二叉樹又是當中的貴族。二叉樹的一個重要應用是它們在查找中的應用，于是就有了二叉查找樹。 使二叉樹成為一顆二叉查找樹，需要滿足以下兩點：
- 對于樹中的每個節點X，它的左子樹中所有項的值都要小于X中的項；
- 對于樹中的每個節點Y，它的右子樹中所有項的值都要大于X中的項。 </ol>
- 對于樹中的每個節點X，它的左子樹中所有項的值都要小于X中的項；
- 對于樹中的每個節點Y，它的右子樹中所有項的值都要大于X中的項。 </ol>
- 一直沿著左節點往下找，直到子節點等于
NULL為止，這樣就可以找到最小值了； - 一直沿著右節點往下找，直到子節點等于
NULL為止，這樣就可以找到最大值了。
</ol>
- 使用遞歸實現；
- 使用非遞歸的方式實現。 </ol>
- 首先判斷需要查找的值與當前節點值的大小關系；
- 當小于當前節點值時，就在左節點中繼續查找；
- 當大于當前節點值時，就在右節點中繼續查找；
- 當找到該值時，直接返回true。 </ol>
- 首先判斷需要插入的值域當前節點值得大小關系；
- 當小于當前節點值時，就在左節點中繼續查找插入點；
- 當大于當前節點值時，就在右節點中繼續查找插入點；
- 當等于當前節點值時，什么也不干。 </ol>
- 需要刪除的子節點，它沒有任何子節點；例如圖中的節點9、節點17、節點21、節點56和節點88；這些節點它們都沒有子節點；
- 需要刪除的子節點，只有一個子節點（只有左子節點或右子節點）；例如圖中的節點16和節點40；這些節點它們都只有一個子節點；
- 需要刪除的子節點，同時擁有兩個子節點；例如圖中的節點66等。 </ol>
二叉查找樹的基本操作
以下是對于二叉查找樹的基本操作定義類，然后慢慢分析是如何實現它們的。
template
class BinarySearchTree{public:// 構造函數，初始化root值BinarySearchTree() : root(NULL){}// 析構函數，默認實現~BinarySearchTree() {}// 查找最小值，并返回最小值const T &findMin() const;// 查找最大值，并返回最大值const T &findMax() const;// 判斷二叉樹中是否包含指定值的元素bool contains(const T &x) const;// 判斷二叉查找樹是否為空bool isEmpty() const { return root ? false : true; }// 打印二叉查找樹的值void printTree() const;// 向二叉查找樹中插入指定值void insert(const T &x);// 刪除二叉查找樹中指定的值void remove(const T &x);// 清空整個二叉查找樹void makeEmpty() const;private:// 指向根節點BinaryNode*root; void insert(const T &x, BinaryNode*&t) const; void remove(const T &x, BinaryNode*&t) const; BinaryNode*findMin(BinaryNode *t) const; BinaryNode*findMax(BinaryNode *t) const; bool contains(const T &x, BinaryNode*t) const; void printTree(BinaryNode*t) const; void makeEmpty(BinaryNode*&t) const; };</blockquote>findMin和findMax實現
根據二叉查找樹的性質：
我們可以從
root節點開始：
如下圖所示：
在程序中實現時，有兩種方法：
對于
finMin的實現，我這里使用遞歸的方式，代碼參考如下：BinaryNode
*BinarySearchTree ::findMin(BinaryNode *t) const {if (t == NULL){return NULL;}else if (t->left == NULL){return t;}else{return findMin(t->left);}}</blockquote>在
findMin()的內部調用findMin(BinaryNode，這樣就防止了客戶端知道了*t) root根節點的信息。上面使用遞歸的方式實現了查找最小值，下面使用循環的方式來實現findMax。template
BinaryNode*BinarySearchTree ::findMax(BinaryNode *t) const {if (t == NULL){return NULL;}while (t->right){t = t->right;}return t;}</blockquote>在很多面試的場合下，面試官一般都是讓寫出非遞歸的版本；而在對樹進行的各種操作，很多時候都是使用的遞歸實現的，所以，在平時學習時，在理解遞歸版本的前提下，需要關心一下對應的非遞歸版本。
contains實現
contains用來判斷二叉查找樹是否包含指定的元素。代碼實現如下：template
bool BinarySearchTree::contains(const T &x, BinaryNode *t) const {if (t == NULL){return false;}else if (x > t->element){return contains(x, t->right);}else if (x < t->element){return contains(x, t->left);}else{return true;}}</blockquote>算法規則如下：
insert實現
insert函數用來向兒茶查找樹中插入新的元素，算法處理如下：
代碼實現如下：
template
void BinarySearchTree::insert(const T &x, BinaryNode *&t) const {if (t == NULL){t = new BinaryNode(x, NULL, NULL); }else if (x < t->element){insert(x, t->left);}else if (x > t->element){insert(x, t->right);}}</blockquote>remove實現
remove函數用來刪除二叉查找樹中指定的元素值，這個處理起來比較麻煩。在刪除子節點時，需要分以下幾種情況進行考慮（結合下圖進行說明）： 如下圖所示：
對于情況1，直接刪除對應的節點即可；實現起來時比較簡單的；
對于情況2，直接刪除對應的節點，然后用其子節點占據刪除掉的位置；
對于情況3，是比較復雜的。首先在需要被刪除節點的右子樹中找到最小值節點，然后使用該最小值替換需要刪除節點的值，然后在右子樹中刪除該最小值節點。
假如現在需要刪除包含值23的節點，步驟如下圖所示：
代碼實現如下：
template
void BinarySearchTree::remove(const T &x, BinaryNode *&t) const {if (t == NULL){return;}if (x < t->element){remove(x, t->left);}else if (x > t->element){remove(x, t->right);}else if (t->left != NULL && t->right != NULL){// 擁有兩個子節點t->element = findMin(t->right)->element;remove(t->element, t->right);}else if (t->left == NULL && t->right == NULL){// 沒有子節點，直接干掉delete t;t = NULL;}else if (t->left == NULL || t->right == NULL){// 擁有一個子節點BinaryNode *pTemp = t;t = (t->left != NULL) ? t->left : t->right;delete pTemp;}}</blockquote>makeEmpty實現
makeEmpty函數用來釋放整個二叉查找樹占用的內存空間，同理，也是使用的遞歸的方式來實現的。具體代碼請下載文中最后提供的源碼。總結
這篇文章對數據結構中非常重要的二叉查找樹進行了詳細的總結，雖然二叉查找樹非常重要，但是理解起來還是非常容易的，主要是需要掌握對遞歸的理解。 如果對遞歸有非常扎實的理解，那么對于樹的一些操作，那都是非常好把握的，而理解二叉查找樹又是后續的AVL平衡樹和紅黑樹的基礎，希望這篇文章對大家有 幫助。
</div> </div> </div> 原文來自： 果凍想本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！相關資訊
