寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時最大的愛好就是聽聽歌，逛逛B站。博主很喜歡的一句話花開堪折直須折，莫待無花空折枝：博主的理解是頭一次為人，就應該做自己想做的事，做自己不后悔的事，做自己以后不會留有遺憾的事，做自己覺得有意義的事，不浪費這大好的青春年華。博主寫博客目的是記錄所學到的知識并方便自己復習，在記錄知識的同時獲得部分瀏覽量，得到更多人的認可，滿足小小的成就感，同時在寫博客的途中結交更多志同道合的朋友，讓自己在技術的路上并不孤單。

目錄:
1.二叉排序樹定義
2.二叉排序樹查找
3.二叉排序樹的插入
4.二叉排序樹的刪除
5.二叉排序樹全功能完整代碼實現
6.二叉排序樹小結

1.二插排序樹定義

二叉排序樹要么是空二叉樹，要么具有如下特點：

• 二叉排序樹中，如果其根結點有左子樹，那么左子樹上所有結點的值都小于根結點的值；
• 二叉排序樹中，如果其根結點有右子樹，那么右子樹上所有結點的值都大小根結點的值；
• 二叉排序樹的左右子樹也要求都是二叉排序樹；

如下圖就是一顆二叉排序樹：

2.二叉排序樹查找關鍵

二叉排序樹中查找某關鍵字時，查找過程類似于次優二叉樹，在二叉排序樹不為空樹的前提下，首先將被查找值同樹的根結點進行比較，會有 3 種不同的結果：

• 如果相等，查找成功；
• 如果比較結果為根結點的關鍵字值較大，則說明該關鍵字可能存在其左子樹中；
• 如果比較結果為根結點的關鍵字值較小，則說明該關鍵字可能存在其右子樹中； 實現函數為：（運用遞歸的方法）:

BiTree SearchBST(BiTree T,KeyType key){//如果遞歸過程中 T 為空，則查找結果，返回NULL；或者查找成功，返回指向該關鍵字的指針if (!T || key==T->data) {return T;}else if(key<T->data){//遞歸遍歷其左孩子return SearchBST(T->lchild, key);}else{//遞歸遍歷其右孩子return SearchBST(T->rchild, key);} }

3.二叉排序樹中插入

二叉排序樹本身是動態查找表的一種表示形式，有時會在查找過程中插入或者刪除表中元素，當因為查找失敗而需要插入數據元素時，該數據元素的插入位置一定位于二叉排序樹的葉子結點，并且一定是查找失敗時訪問的最后一個結點的左孩子或者右孩子。

例如，在下圖的二叉排序樹中做查找關鍵字 1 的操作，當查找到關鍵字 3 所在的葉子結點時，判斷出表中沒有該關鍵字，此時關鍵字 1 的插入位置為關鍵字 3 的左孩子

所以，二叉排序樹表示動態查找表做插入操作，只需要稍微更改一下上面的代碼就可以實現，具體實現代碼為：

BOOL SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){//如果 T 指針為空，說明查找失敗，令 p 指針指向查找過程中最后一個葉子結點，并返回查找失敗的信息if (!T){*p=f;return false;}//如果相等，令 p 指針指向該關鍵字，并返回查找成功信息else if(key==T->data){*p=T;return true;}//如果 key 值比 T 根結點的值小，則查找其左子樹；反之，查找其右子樹else if(key<T->data){return SearchBST(T->lchild,key,T,p);}else{return SearchBST(T->rchild,key,T,p);} } //插入函數 BOOL InsertBST(BiTree T,ElemType e){BiTree p=NULL;//如果查找不成功，需做插入操作if (!SearchBST(T, e,NULL,&p)) {//初始化插入結點BiTree s=(BiTree)malloc(sizeof(BiTree));s->data=e;s->lchild=s->rchild=NULL;//如果 p 為NULL，說明該二叉排序樹為空樹，此時插入的結點為整棵樹的根結點if (!p) {T=s;}//如果 p 不為 NULL，則 p 指向的為查找失敗的最后一個葉子結點，只需要通過比較 p 和 e 的值確定 s 到底是 p 的左孩子還是右孩子else if(e<p->data){p->lchild=s;}else{p->rchild=s;}return true;}//如果查找成功，不需要做插入操作，插入失敗return false; }

通過使用二叉排序樹對動態查找表做查找和插入的操作，同時在中序遍歷二叉排序樹時，可以得到有關所有關鍵字的一個有序的序列。

例如，假設原二叉排序樹為空樹，在對動態查找表 {3，5，7，2，1} 做查找以及插入操作時，可以構建出一個含有表中所有關鍵字的二叉排序樹，過程如：

當使用中序遍歷算法遍歷二叉排序樹時，得到的序列為：1 2 3 5 7 ，為有序序列。

一個無序序列可以通過構建一棵二叉排序樹，從而變成一個有序序列。

4.二叉排序樹的刪除

在查找過程中，如果在使用二叉排序樹表示的動態查找表中刪除某個數據元素時，需要在成功刪除該結點的同時，依舊使這棵樹為二叉排序樹。

假設要刪除的為結點 p，則對于二叉排序樹來說，需要根據結點 p 所在不同的位置作不同的操作，有以下 3 種可能：

結點 p 為葉子結點，此時只需要刪除該結點，并修改其雙親結點的指針即可；

結點 p 只有左子樹或者只有右子樹，此時只需要將其左子樹或者右子樹直接變為結點 p 雙親結點的左子樹即可；

結點 p 左右子樹都有，此時有兩種處理方式

當p左右孩子都有的情況下，第一種處理方式：令結點 p 的左子樹為其雙親結點的左子樹；結點 p 的右子樹為其自身直接前驅結點的右子樹

第二種方式：用結點 p 的直接前驅（或直接后繼）來代替結點 p，同時在二叉排序樹中對其直接前驅（或直接后繼）做刪除操作。如圖 4 為使用直接前驅代替結點 p：

在對左圖進行中序遍歷時，得到的結點 p 的直接前驅結點為結點 s，所以直接用結點 s 覆蓋結點 p，由于結點 s 還有左孩子，根據第 2 條規則，直接將其變為雙親結點的右孩子

第一種方法可能增加樹的高度，后一種方法是以刪除結點左子樹中關鍵字最大的結點替代被刪結點，然后從左子樹中刪除這個結點，此結點一定沒有右子樹，不會增加樹的高度，所以一般采用后一種方法處理

int Delete(BiTree *p) {BiTree q, s;//情況 1，結點 p 本身為葉子結點，直接刪除即可if(!(*p)->lchild && !(*p)->rchild){*p = NULL;}else if(!(*p)->lchild){ //左子樹為空，只需用結點 p 的右子樹根結點代替結點 p 即可；q = *p;*p = (*p)->rchild;free(q);}else if(!(*p)->rchild){//右子樹為空，只需用結點 p 的左子樹根結點代替結點 p 即可；q = *p;*p = (*p)->lchild;//這里不是指針 *p 指向左子樹，而是將左子樹存儲的結點的地址賦值給指針變量 pfree(q);}else{//左右子樹均不為空，采用第 2 種方式q = *p;s = (*p)->lchild;//遍歷，找到結點 p 的直接前驅while(s->rchild){q = s;s = s->rchild;}//直接改變結點 p 的值(*p)->data = s->data;//判斷結點 p 的左子樹 s 是否有右子樹，分為兩種情況討論if( q != *p ){q->rchild = s->lchild;//若有，則在刪除直接前驅結點的同時，令前驅的左孩子結點改為 q 指向結點的孩子結點}else{q->lchild = s->lchild;//否則，直接將左子樹上移即可}free(s);}return TRUE; } int DeleteBST(BiTree *T, int key) {if( !(*T)){//不存在關鍵字等于key的數據元素return FALSE;}else{if( key == (*T)->data ){Delete(T);return TRUE;}else if( key < (*T)->data){//使用遞歸的方式return DeleteBST(&(*T)->lchild, key);}else{return DeleteBST(&(*T)->rchild, key);}} }

5.二叉排序樹全功能完整代碼實現

#include<stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define ElemType int #define KeyType int /* 二叉排序樹的節點結構定義 */ typedef struct BiTNode {int data;struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;//二叉排序樹查找算法 int SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){//如果 T 指針為空，說明查找失敗，令 p 指針指向查找過程中最后一個葉子結點，并返回查找失敗的信息if (!T){*p=f;return FALSE;}//如果相等，令 p 指針指向該關鍵字，并返回查找成功信息else if(key==T->data){*p=T;return TRUE;}//如果 key 值比 T 根結點的值小，則查找其左子樹；反之，查找其右子樹else if(key<T->data){return SearchBST(T->lchild,key,T,p);}else{return SearchBST(T->rchild,key,T,p);} } int InsertBST(BiTree *T,ElemType e){BiTree p=NULL;//如果查找不成功，需做插入操作if (!SearchBST((*T), e,NULL,&p)) {//初始化插入結點BiTree s=(BiTree)malloc(sizeof(BiTree));s->data=e;s->lchild=s->rchild=NULL;//如果 p 為NULL，說明該二叉排序樹為空樹，此時插入的結點為整棵樹的根結點if (!p) {*T=s;}//如果 p 不為 NULL，則 p 指向的為查找失敗的最后一個葉子結點，只需要通過比較 p 和 e 的值確定 s 到底是 p 的左孩子還是右孩子else if(e < p->data){p->lchild=s;}else{p->rchild=s;}return TRUE;}//如果查找成功，不需要做插入操作，插入失敗return FALSE; } //刪除函數 int Delete(BiTree *p) {BiTree q, s;//情況 1，結點 p 本身為葉子結點，直接刪除即可if(!(*p)->lchild && !(*p)->rchild){*p = NULL;}else if(!(*p)->lchild){ //左子樹為空，只需用結點 p 的右子樹根結點代替結點 p 即可；q = *p;*p = (*p)->rchild;free(q);}else if(!(*p)->rchild){//右子樹為空，只需用結點 p 的左子樹根結點代替結點 p 即可；q = *p;*p = (*p)->lchild;//這里不是指針 *p 指向左子樹，而是將左子樹存儲的結點的地址賦值給指針變量 pfree(q);}else{//左右子樹均不為空，采用第 2 種方式q = *p;s = (*p)->lchild;//遍歷，找到結點 p 的直接前驅while(s->rchild){q = s;s = s->rchild;}//直接改變結點 p 的值(*p)->data = s->data;//判斷結點 p 的左子樹 s 是否有右子樹，分為兩種情況討論if( q != *p ){q->rchild = s->lchild;//若有，則在刪除直接前驅結點的同時，令前驅的左孩子結點改為 q 指向結點的孩子結點}else{q->lchild = s->lchild;//否則，直接將左子樹上移即可}free(s);}return TRUE; } int DeleteBST(BiTree *T, int key) {if( !(*T)){//不存在關鍵字等于key的數據元素return FALSE;}else{if( key == (*T)->data ){Delete(T);return TRUE;}else if( key < (*T)->data){//使用遞歸的方式return DeleteBST(&(*T)->lchild, key);}else{return DeleteBST(&(*T)->rchild, key);}} } void order(BiTree t)//中序輸出 {if(t == NULL){return ;}order(t->lchild);printf("%d ", t->data);order(t->rchild); } int main() {int i;int a[5] = {3,4,2,5,9};BiTree T = NULL;for( i = 0; i < 5; i++ ){InsertBST(&T, a[i]);}printf("中序遍歷二叉排序樹：\n");order(T);printf("\n");printf("刪除3后，中序遍歷二叉排序樹：\n");DeleteBST(&T,3);order(T); } // 中序遍歷二叉排序樹： 2 3 4 5 9 刪除3后，中序遍歷二叉排序樹： 2 4 5 9

6.二叉排序樹小結

使用二叉排序樹在查找表中做查找操作的時間復雜度同建立的二叉樹本身的結構有關。即使查找表中各數據元素完全相同，但是不同的排列順序，構建出的二叉排序樹大不相同。

例如：查找表 {45，24，53，12，37，93} 和表 {12，24，37，45，53，93} 各自構建的二叉排序樹圖下圖所示：

使用二叉排序樹實現動態查找操作的過程，實際上就是從二叉排序樹的根結點到查找元素結點的過程，所以時間復雜度同被查找元素所在的樹的深度（層次數）有關。

本篇博客轉載C語言中文網

總結

以上是生活随笔為你收集整理的二叉排序树(完整案例与完整C语言代码)的全部內容，希望文章能夠幫你解決所遇到的問題。

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