二叉排序樹
二叉排序樹有稱之為二叉查找樹。它或是一顆空樹腿椎，或是一顆具有下面性質(zhì)的二叉樹:
若它的左子樹不為空思灌，則左子樹上所有的結(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值照激；
若它的右子樹不為空霎冯，則右子樹上所有的結(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值铃拇；
它的左右子樹也分別為二叉排序樹。
1.結(jié)點(diǎn)定義
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;
//二叉樹的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義
//結(jié)點(diǎn)結(jié)構(gòu)
typedef struct BiTNode
{
//結(jié)點(diǎn)數(shù)據(jù)
int data;
//左右孩子指針
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
2.二叉排序樹--查找
/*
遞歸查找二叉排序樹T中,是否存在key;
指針f指向T的雙親,器初始值為NULL;
若查找成功,則指針p指向該數(shù)據(jù)元素的結(jié)點(diǎn),并且返回TRUE;
若指針p指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)則返回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); /* 在左子樹中繼續(xù)查找 */
else
return SearchBST(T->rchild, key, T, p); /* 在右子樹中繼續(xù)查找 */
}
3.二叉排序樹-插入
/* 當(dāng)二叉排序樹T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)沈撞， */
/* 插入key并返回TRUE慷荔，否則返回FALSE */
Status InsertBST(BiTree *T, int key) {
BiTree p,s;
//1.查找插入的值是否存在二叉樹中;查找失敗則->
if (!SearchBST(*T, key, NULL, &p)) {
//2.初始化結(jié)點(diǎn)s,并將key賦值給s,將s的左右孩子結(jié)點(diǎn)暫時(shí)設(shè)置為NULL
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
//3.
if (!p) {
//如果p為空,則將s作為二叉樹新的根結(jié)點(diǎn);
*T = s;
}else if(key < p->data){
//如果key<p->data,則將s插入為左孩子;
p->lchild = s;
}else
//如果key>p->data,則將s插入為右孩子;
p->rchild = s;
return TRUE;
}
return FALSE;
}
3.二叉排序樹-刪除
//3.從二叉排序樹中刪除結(jié)點(diǎn)p,并重接它的左或者右子樹;
Status Delete(BiTree *p){
BiTree temp,s;
if((*p)->rchild == NULL){
//情況1: 如果當(dāng)前刪除的結(jié)點(diǎn),右子樹為空.那么則只需要重新連接它的左子樹;
//①將結(jié)點(diǎn)p臨時(shí)存儲(chǔ)到temp中;
temp = *p;
//②將p指向到p的左子樹上;
*p = (*p)->lchild;
//③釋放需要?jiǎng)h除的temp結(jié)點(diǎn);
free(temp);
}else if((*p)->lchild == NULL){
//情況2:如果當(dāng)前刪除的結(jié)點(diǎn),左子樹為空.那么則只需要重新連接它的右子樹;
//①將結(jié)點(diǎn)p存儲(chǔ)到temp中;
temp = *p;
//②將p指向到p的右子樹上;
*p = (*p)->rchild;
//③釋放需要?jiǎng)h除的temp結(jié)點(diǎn)
free(temp);
}else{
//情況③:刪除的當(dāng)前結(jié)點(diǎn)的左右子樹均不為空;
//①將結(jié)點(diǎn)p存儲(chǔ)到臨時(shí)變量temp, 并且讓結(jié)點(diǎn)s指向p的左子樹
temp = *p;
s = (*p)->lchild;
//②將s指針,向右到盡頭(目的是找到待刪結(jié)點(diǎn)的前驅(qū))
//-在待刪除的結(jié)點(diǎn)的左子樹中,從右邊找到直接前驅(qū)
//-使用`temp`保存好直接前驅(qū)的雙親結(jié)點(diǎn)
while (s->rchild) {
temp = s;
s = s->rchild;
}
//③將要?jiǎng)h除的結(jié)點(diǎn)p數(shù)據(jù)賦值成s->data;
(*p)->data = s->data;
//④重連子樹
//-如果temp 不等于p,則將S->lchild 賦值給temp->rchild
//-如果temp 等于p,則將S->lchild 賦值給temp->lchild
if(temp != *p)
temp->rchild = s->lchild;
else
temp->lchild = s->lchild;
//⑤刪除s指向的結(jié)點(diǎn); free(s)
free(s);
}
return TRUE;
}
//4.查找結(jié)點(diǎn),并將其在二叉排序中刪除;
/* 若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素結(jié)點(diǎn), */
/* 并返回TRUE缠俺；否則返回FALSE显晶。 */
Status DeleteBST(BiTree *T,int key)
{
//不存在關(guān)鍵字等于key的數(shù)據(jù)元素
if(!*T)
return FALSE;
else
{
//找到關(guān)鍵字等于key的數(shù)據(jù)元素
if (key==(*T)->data)
return Delete(T);
else if (key<(*T)->data)
//關(guān)鍵字key小于當(dāng)前結(jié)點(diǎn),則縮小查找范圍到它的左子樹;
return DeleteBST(&(*T)->lchild,key);
else
//關(guān)鍵字key大于當(dāng)前結(jié)點(diǎn),則縮小查找范圍到它的右子樹;
return DeleteBST(&(*T)->rchild,key);
}
}
測(cè)試
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 二叉排序樹(Binary Sort Tree)!\n");
int i;
int a[10]={62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i=0;i<10;i++)
{
InsertBST(&T, a[i]);
}
BiTree p;
int statusValue = SearchBST(T, 99, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",p->data,statusValue);
statusValue = DeleteBST(&T,93);
printf("二叉排序樹刪除93是否成功:%d (1->YES/0->NO)\n",statusValue);
statusValue = DeleteBST(&T,47);
printf("二叉排序樹刪除47是否成功:%d (1->YES/0->NO)\n",statusValue);
statusValue = DeleteBST(&T,12);
printf("二叉排序樹刪除12是否成功:%d (1->YES/0->NO)\n",statusValue);
statusValue = SearchBST(T, 93, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",93,statusValue);
statusValue = SearchBST(T, 47, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",47,statusValue);
statusValue = SearchBST(T, 99, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",99,statusValue);
printf("\n");
return 0;
}
