二叉排序樹定義
二叉排序樹(Binary Sort Tree)朱灿，又稱二叉查找樹。它是一顆空樹聚谁，或者具有下列性質(zhì)：
- 若它的左子樹不為空母剥，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值滞诺；
- 若它的右子樹不為空形导，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
-
它的左习霹、右子樹分別為二叉排序樹朵耕。
二叉排序樹
構(gòu)造二叉排序樹的目的
- 提高查找和插入刪除關(guān)鍵字的速度。
一淋叶、二叉排序樹的查找
- 二叉排序樹的查找可以用遞歸來實現(xiàn)阎曹；
- 先將要查找的關(guān)鍵字和根節(jié)點進行比較;
- 若和根節(jié)點值相同，則返回根節(jié)點值煞檩；若比根節(jié)點小处嫌，就遞歸查找左子樹，若比根節(jié)點大斟湃，則遞歸查找右子樹熏迹。
二叉排序樹的查找代碼實現(xiàn)
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef struct BiTNode{// 二叉樹的兒二叉鏈表結(jié)點結(jié)構(gòu)
int data; // 結(jié)點結(jié)構(gòu)
struct BiTNode * lchild,* rchild; // 左右孩子指針
}BiTNode, * BiTree;
/**
* 遞歸查找二叉排序樹 T 中是否存在 key
* 指針 f 指向 T 的 雙親，其初始調(diào)用值為NULL
* 若查找成功凝赛，則指針 p 指向該數(shù)據(jù)元素結(jié)點注暗，并返回TRUE
* 若查找不成功， 則指針 p 指向查找路徑上訪問的最后一個結(jié)點并返回FALSE
*/
int 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){ // 在左子樹中繼續(xù)查找
return SearchBST(T->lchild, key, T, p);
}else{ // 在右子樹中雞血查找
return SearchBST(T->rchild, key, T, p);
}
}
二墓猎、二叉排序樹的插入操作
- 先調(diào)用查找操作將要插入的關(guān)鍵字進行比較
- 如果在原有的二叉排序樹中沒有要插入的關(guān)鍵字捆昏，則將關(guān)鍵字與查找的結(jié)點p（在查找操作中返回的結(jié)點）的值進行比較
- 若p為空，則插入關(guān)鍵字賦值給該節(jié)點毙沾；
- 若小于結(jié)點p的值骗卜，則插入關(guān)鍵字作為結(jié)點p的左子樹；
- 若大于結(jié)點p的值左胞，則插入關(guān)鍵字作為結(jié)點p的右子樹膨俐；
二叉排序樹的插入操作代碼實現(xiàn)
/**
* 二叉排序樹的插入
* 當(dāng)二叉排序樹中不存在關(guān)鍵字等于 key 的數(shù)據(jù)元素時，插入 key 并返回TRUE
*/
int InsertBST(BiTree * T, int key){
BiTree p,s;
if (!SearchBST( *T, key, NULL, &p)) { // 沒找到key
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
if (!p)
*T = s; // 插入 s 為新的根結(jié)點
else if (key < p->data)
p->lchild = s; //插入 s 為左孩子
else
p->rchild = s; // 插入 s 為右孩子
return TRUE;
}else
return FALSE;
}
三罩句、二叉排序樹的刪除操作
二叉排序樹的刪除操作相對復(fù)雜焚刺，因為不能因為刪除了結(jié)點，讓這顆二叉排序樹變得不滿足二叉排序樹的性質(zhì)门烂，所以對于二叉排序樹的刪除存在三種情況：
- 葉子結(jié)點乳愉；（很容易實現(xiàn)刪除操作兄淫，直接刪除結(jié)點即可）
- 僅有左或者右子樹的結(jié)點；（容易實現(xiàn)刪除操作蔓姚，刪除結(jié)點后捕虽，將它的左子樹或者右子樹整個移動到刪除結(jié)點的位置）
- 左右子樹都有的結(jié)點。（實現(xiàn)刪除操作很復(fù)雜）
對于要刪除的結(jié)點同時存在左右子樹的情況的解決辦法
核心思想
將它的直接前驅(qū)或者直接后繼作為刪除結(jié)點的數(shù)據(jù)
實現(xiàn)方法
- 如圖坡脐，要刪除的結(jié)點為47
- 47的直接前驅(qū)是37泄私，直接后繼是48
- 如果用直接前驅(qū)37作為刪除后結(jié)點的值，（由于結(jié)點37有一個左子樹）那么（左子樹）36就去替換到37結(jié)點上备闲。
-
如果用直接后繼47作為刪除后結(jié)點的值晌端，（由于結(jié)點47是葉子結(jié)點）那么直接將48替換到37結(jié)點上即可。
二叉排序樹的刪除操作代碼實現(xiàn)
/**
* 從二叉排序樹中刪除結(jié)點 p 恬砂， 并重接它的左/右子樹
*/
int 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) { // 向右到盡頭咧纠，找到待刪結(jié)點的前驅(qū)
q = s;
s = s->rchild;
}
(*p)->data = s->data; // s 指向被刪除結(jié)點的直接前驅(qū) （將被刪結(jié)點前驅(qū)的值取代被刪結(jié)點的值）
if (q != *p)
q->rchild = s->lchild; // 重接 q 的右子樹
else
q->lchild = s->lchild; // 重接 q 的左子樹
free(s);
}
return TRUE;
}
/**
* 二叉排序樹的刪除
* 當(dāng)二叉排序樹中存在關(guān)鍵字等于 key 的數(shù)據(jù)元素時，刪除該數(shù)據(jù)元素并返回TRUE
*/
int DeleteBST(BiTree * T, int key){
if (!*T) // 不存在關(guān)鍵字等于 key 的元素
return FALSE;
else{
if (key == (*T)->data)
return Delete(T);
else if (key < (*T)->data)
return DeleteBST(&(*T)->lchild, key);
else
return DeleteBST(&(*T)->rchild, key);
}
}
四泻骤、測試代碼
對于二叉排序樹的建立漆羔，可以通過二叉排序樹的插入操作來實現(xiàn)。
通過中序遍歷二叉排序樹狱掂，結(jié)果是從小到大輸出演痒。
/**
* 中序遞歸遍歷
*/
void InOrderTraverse(BiTree T){
if (!T)
return;
InOrderTraverse(T->lchild);
printf("%d ", T->data);
InOrderTraverse(T->rchild);
}
int main(int argc, const char * argv[]) {
int i;
int a[10] ={62,88,58,47,35,73,51,99,37,93};
BiTree T = NULL;
for (i = 0; i < 10; i++) { // 通過插入操作來構(gòu)建二叉排序樹
InsertBST(&T, a[i]);
}
printf("中序遞歸遍歷二叉排序樹：\n");
InOrderTraverse(T);
printf("\n\n");
DeleteBST(&T, 93);
printf("刪除結(jié)點 93 后的結(jié)果為：\n");
InOrderTraverse(T);
printf("\n\n");
printf("插入 91 后的結(jié)果為：\n");
InsertBST(&T, 91);
InOrderTraverse(T);
printf("\n\n");
return 0;
}
二叉排序樹總結(jié)
- 二叉排序樹是以鏈接的方式存儲，保持了鏈接存儲結(jié)構(gòu)在執(zhí)行插入或刪除操作時不用移動元素的優(yōu)點趋惨。只要找到合適的插入和刪除位置后鸟顺，僅需要修改鏈接指針即可。插入刪除的時間性能比較好希柿。
- 對于二叉排序樹的查找诊沪，走的是根結(jié)點到要查找結(jié)點的路徑，其比較次數(shù)等于給定值的結(jié)點在二叉排序樹的層次曾撤。
