深入學習二叉樹(四) 二叉排序樹

1 前言

數據結構中，線性表分為無序線性表和有序線性表。
無序線性表的數據是雜亂無序的，所以在插入和刪除時，沒有什么必須遵守的規則，可以插入在數據尾部或者刪除在數據尾部。但是在查找的時候，需要遍歷整個數據表，導致無序線性表的查找效率低。
有序線性表的數據則相反，查找數據時的時候因為數據是有序的，可以用二分法、插值法、斐波那契查找法來實現。但是，當進行插入和刪除操作時，需要維護表中數據的有序性，會耗費大量的時間。
那么，我們希望找到一種數據結構，既可以有較高的插入和刪除效率，并且具備較高的查找效率，因此，二叉排序樹應運而生。

2 二叉排序樹

2.1 定義

二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），也稱二叉搜索樹。二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：

（1）若左子樹不空，則左子樹上所有結點的值均小于或等于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；

2.2 構造一棵二叉排序樹

現有序列：61 87 59 47 35 73 51 98 37 93

構造過程如下：
1）索引 i = 0，A[i] = 61，結點61作為根結點，如圖2.1：

2）索引 i = 1，A[1] = 87, 87 > 61，且結點61右孩子為空，故81為61結點的右孩子，如圖2.2：

3）索引 i = 2，A[i] = 59，59 <61，且結點61左孩子為空，故59為61結點的左孩子，如圖2.3：

4）索引 i = 3，A[3] = 47，47 < 59，且結點59左孩子為空，故47為59結點的左孩子，如圖2.4：

5）索引 i = 4，A[4] = 35，35 < 47，且結點47左孩子為空，故35為47結點的左孩子，如圖2.5：

采用同樣規則遍歷整個數組得到如圖2.6所示的一棵排序二叉樹。

2.3 二叉排序樹查找

由二叉樹的遞歸定義性質，二叉排序樹的查找同樣可以使用如下遞歸算法查找。

如果樹是空的，則查找結束，無匹配。
如果被查找的值和根結點的值相等，查找成功。否則就在子樹中繼續查找。如果被查找的值小于根結點的值就選擇左子樹，大于根結點的值就選擇右子樹。

在理想情況下，每次比較過后，樹會被砍掉一半，近乎折半查找。
遍歷打印可以使用中序遍歷，打印出來的結果是從小到大的有序數組。
查找代碼：

typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */ /* 二叉樹的二叉鏈表結點結構定義 */ typedef struct BiTNode /* 結點結構 */ {int data; /* 結點數據 */struct BiTNode *lchild, *rchild; /* 左右孩子指針 */ } BiTNode, *BiTree;/* 遞歸查找二叉排序樹T中是否存在key, */ /* 指針f指向T的雙親，其初始調用值為NULL */ /* 若查找成功，則指針p指向該數據元素結點，并返回TRUE */ /* 否則指針p指向查找路徑上訪問的最后一個結點并返回FALSE */ Status SearchBST(BiTree t, int key, BiTree f, BiTree *p) { if (!t) /* 查找不成功 */{ *p = f; return FALSE; }else if (key == t->data) /* 查找成功 */{ *p = t; return TRUE; } else if (key < t->data) return SearchBST(t->lchild, key, t, p); /* 在左子樹中繼續查找 */else return SearchBST(t->rchild, key, t, p); /* 在右子樹中繼續查找 */ }

對于圖2.6所示的二叉排序樹，若查找結點key為47則可以查找成功，若查找結點key為75，樹中不存在key為75的結點，故查找失敗，則查找指針p指向查找路徑的最后一個結點，即結點73。

2.4 二叉排序樹插入

二叉排序的插入是建立在二叉排序的查找之上的，插入一個結點，就是通過查找發現該結點合適插入位置，把結點直接放進去。 其實在2.2節中一步步構造二叉排序樹的過程中就是結點插入過程。由此可以得出二叉排序樹插入規則如下：

若查找的key已經有在樹中，則p指向該數據結點。
若查找的key沒有在樹中，則p指向查找路徑上最后一個結點。

例如：若在圖2.6展示的二叉排序樹中插入結點數據為60的結點。
首先查找結點數據為60的結點，二叉排序樹中不存在結點為60的結點，因此查找失敗。此時查找指針p指向查找路徑最后一個結點即指向59結點。由于60>59且59結點右子樹為空，故將60結點作為59結點的右孩子，插入完成。插入后的二叉排序樹如圖2.8所示。

插入代碼：

struct BiTree {int data;BiTree *lchild;BiTree *rchild; };//在二叉排序樹中插入查找關鍵字key BiTree* InsertBST(BiTree *t,int key) {if (t == NULL){t = new BiTree();t->lchild = t->rchild = NULL;t->data = key;return t;}if (key < t->data) t->lchild = InsertBST(t->lchild, key);elset->rchild = InsertBST(t->rchild, key);return t; }//n個數據在數組d中，tree為二叉排序樹根 BiTree* CreateBiTree(BiTree *tree, int d[], int n) {for (int i = 0; i < n; i++)tree = InsertBST(tree, d[i]); }

2.5 二叉排序樹刪除

二叉樹的刪除可不再像二叉樹的插入那么容易了，以為刪除某個結點以后，會影響到樹的其它部分的結構。
刪除的時候需要考慮以下幾種情況：

1）刪除結點為葉子結點；
2）刪除的結點只有左子樹；
3）刪除的結點只有右子樹
4）刪除的結點既有左子樹又有右子樹。

考慮前三種情況，處理方式比較簡單。
例如：若要刪除圖2.8中的結點93，則直接刪除該結點即可。刪除后二叉排序樹如圖2.9所示：

若要刪除的結點為結點35，結點35只有右子樹，只需刪除結點35，將右子樹37結點替代結點35即可。刪除后的二叉排序樹如圖2.10所示：

刪除只有左子樹的結點與此情況類似。

情況4相對比較復雜，對于待刪除結點既有左子樹又有右子樹的情形，最佳辦法是在剩余的序列中找到最為接近的結點來代替刪除結點。這種代替并不會影響到樹的整體結構。那么最為接近的結點如何獲取呢？
可以采用中序遍歷的方式來得到刪除結點的前驅和后繼結點。選取前驅結點或者后繼結點代替刪除結點即可。
例如：待刪除的結點為47，圖2.8中二叉排序樹的中序遍歷序列為35 37 47 51 59 60 61 73 87 93 98。則結點47的前驅結點為37，則直接將37結點替代47結點即可。替換后的二叉排序樹如圖2.11所示：

刪除代碼：

/* 若二叉排序樹T中存在關鍵字等于key的數據元素時，則刪除該數據元素結點, */ /* 并返回TRUE；否則返回FALSE。 */ Status DeleteBST(BiTree *T,int key) { if(!*T) /* 不存在關鍵字等于key的數據元素 */ return FALSE;else{if (key==(*T)->data) /* 找到關鍵字等于key的數據元素 */ return Delete(T);else if (key<(*T)->data)return DeleteBST(&(*T)->lchild,key);elsereturn DeleteBST(&(*T)->rchild,key);} } /* 從二叉排序樹中刪除結點p，并重接它的左或右子樹。 */ Status Delete(BiTree *p) {BiTree q,s;if((*p)->rchild==NULL) /* 右子樹空則只需重接它的左子樹（待刪結點是葉子也走此分支) */{q=*p; *p=(*p)->lchild; free(q);}else if((*p)->lchild==NULL) /* 只需重接它的右子樹 */{q=*p; *p=(*p)->rchild; free(q);}else /* 左右子樹均不空 */{q=*p; s=(*p)->lchild;while(s->rchild) /* 轉左，然后向右到盡頭（找待刪結點的前驅） */{q=s;s=s->rchild;}(*p)->data=s->data; /* s指向被刪結點的直接前驅（將被刪結點前驅的值取代被刪結點的值） */if(q!=*p)q->rchild=s->lchild; /* 重接q的右子樹 */ elseq->lchild=s->lchild; /* 重接q的左子樹 */free(s);}return TRUE; }

3 結語

二叉排序樹是一種查找與插入效率均較為高效的數據結構，同時，二叉排序樹也是二叉樹學習中的重點與難點。希望通過本篇的學習能夠掌握二叉排序樹的查找、插入與刪除等基本操作，也希望讀者給出指導意見。

總結

以上是生活随笔為你收集整理的深入学习二叉树(四) 二叉排序树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。