? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ?二叉排序樹(BST)構(gòu)造與應(yīng)用

? ? ? 本文取自《數(shù)據(jù)結(jié)構(gòu)與算法》(C語言版)(第三版)。出版社是清華大學(xué)出版社。

? ? ??本博文作為學(xué)習(xí)資料整理。

源碼是VC++ 6.0上可運行程序，我挪到了VS2010中運行。

? ? ??在VS2010中新建C++?Win32 控制臺應(yīng)用程序項目，創(chuàng)建結(jié)果截圖：

? ? ? ? ??

? ??二叉排序樹(BST)：又稱二叉查找樹，其定義為：二叉排序樹或者是空樹，或者是滿足下面性質(zhì)的二叉樹。
? ? ? ?(1) 若它的左子樹非空。則左子樹上全部記錄的keyword均小于根記錄的值。

? ? ? ?(2) 若它的右子樹非空，則右子樹上全部記錄的keyword均大于根記錄的值。

? ? ? ?(3) 左、右子樹本身又各是一棵二叉排序樹。
? ? ? ?按中序遍歷BST所得到的中序序列是一個遞增有序序列。

? ? ? ?二叉排序樹的類型定義：

typedef struct BSTNode{KeyType key; //數(shù)據(jù)域BSTNode *lchild;BSTNode *rchild;}? ? ?1.二叉排序樹的插入操作
? ? ? ?(1)假設(shè)二叉排序樹T為空，則創(chuàng)建一個keyword為k的結(jié)點。將其作為根結(jié)點。

? ? ? ?(2)否則將k和根結(jié)點的keyword進行比較，假設(shè)相等則返回，假設(shè)k小于根結(jié)點的keyword則插入根結(jié)點的左子樹中，否則插入根結(jié)點的右子樹中。

? ? ? ? 二叉排序樹的插入算法：

int InsertBST(BSTNode *p, KeyType k){if(p==NULL){p=(BSTNode*)malloc(sizeof(BSTNode));p->key=k;p->lchild=p->rchild=NULL;return 1;}else if(k==p->key)return 0;else if(k<p->key)return InsertBST(p->lchild, k);elsereturn InsertBST(p->rchild, k);}? ? ? ?二叉排序樹的生成算法：
BSTNode *CreateBST(KeyType A[], int n){BSTNode *bt=NULL;int i=0;while(i<n){InsertBST(bt, A[i]);i++;}return bt;}? ? ? ?演示樣例：輸入{50,16,56,52,8}生成二叉排序樹

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ?2.二叉排序樹的查找操作
? ? ? ?首先將須要查找的值與根結(jié)點比較，假設(shè)相等則查找成功，算法終止。假設(shè)比根結(jié)點小則左子樹中查找，假設(shè)比根結(jié)點大則到右子樹查找。
? ? ? ?二叉排序樹的查找算法的遞歸形式

BSTree SearchBST(BSTree t, int k){if(t==null || k==t->key)return t;else if(k<t->key)return SearchBST(t->lchild, k);elsereturn SearchBST(t->rchild, k);}? ? ? 二叉排序樹的查找算法的非遞歸形式
BSTree SearchBST2(BSTree t, int k){BSTree p=t;while(p!=null && p->key!=k){if(k<p->key)p=p->lchild;elsep=p->rchild;}return p;}

? ? ? ?查找過程演示圖：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? 3.二叉排序樹的刪除操作

? ? ? ? 刪除二叉排序樹的某一個結(jié)點的過程例如以下：
? ? ? ? 1)查找待刪除的結(jié)點
? ? ? ? ?查找結(jié)點時，令*p指向其訪問到的結(jié)點，*f指向其雙親結(jié)點。若樹中找不到被刪結(jié)點時返回NULL，否則被刪除結(jié)點是*p，返回*p。
? ? ? ? 2)刪除結(jié)點
? ? ? ? 如果要刪除二叉排序樹中的一個結(jié)點*p，其雙親結(jié)點為*f，則刪除結(jié)點*p時，需考慮下面3種情況：
? ? ? ? ? ?(1)*p為葉子結(jié)點。
? ? ? ? ? ?在這樣的情況下，能夠?qū)?p結(jié)點直接刪除。
? ? ? ? ? ?p為左子樹：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f->lchild=NULL;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? free(p);
? ? ? ? ? ?p為右子樹:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f->rclild=NULl;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? free(p);

? ? ? ? ? ?操作示意圖例如以下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ?(2)*p僅僅有左子樹，或僅僅有右子樹。
? ? ? ? ? ? 對于這樣的情況，能夠直接將*p的左子樹或右子樹與其雙親結(jié)點*f相連，然后刪除*p。
? ? ? ? ? ? p為f的左孩子。p的左子樹非空：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?f->lchild=p->lchild;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?free(p);
? ? ? ? ? ? p為f的左孩子。p的右子樹非空：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?f->lchild=p->rchild;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?free(p);?
? ? ? ? ? ? p為f的右孩子，p的左子樹非空：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?f->rchild=p->lchild;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?free(p);
? ? ? ? ? ? p為f的右孩子，p的右子樹非空：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?f->rchild=p->rchild;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?free(p);

? ? ? ? ? ??操作示意圖例如以下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ?(3)*p有左右子樹。

? ? ? ? ? ? 方法一：設(shè)*s為*p結(jié)點在中序序列中的直接前驅(qū)。將*p的左子樹改為*f的左子樹，將*p的右子樹改為*s的右子樹。

? ? ? ? ? ? ? ? ? ? ? f->lchild=p->lchild;
? ? ? ? ? ? ? ? ? ? ? s->rchild=p->rchild;

? ? ? ? ? ? ? ? ? ? ? free(p);

? ? ? ? ? ??操作示意圖例如以下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? 方法二：用*p結(jié)點在中序序列中的直接前驅(qū)(或后繼)*s取代*p，然后再從二叉排序樹中將*s刪除。

這時假設(shè)*s為*p的直接前驅(qū)，則*s僅僅有左子樹(或者沒有孩子)，則刪除*s能夠依照刪除*p的其余兩種情況處理。假設(shè)*s為*p的直接后繼，則*s僅僅有右子樹(或者沒有孩子)。刪除*s同理能夠依照刪除*p的其余兩種情況處理。?

附錄 ?

? ? ? A.二叉排序樹的構(gòu)造算法：

? ? ? 注:判定一棵二叉樹是二叉排序樹能夠採用中序遍歷算法將樹上的頂點輸出。假設(shè)得到的中序序列是有序的。則說明這棵二叉樹是二叉排序樹，否則不是二叉排序樹。 #include<stdio.h>#include<stdlib.h>#define MAX 100typedef struct tnode{int data;struct tnode *lchild, *rchild;}TNODE;void create();void insert(int m); //插入二叉排序樹的結(jié)點void inOrder(TNODE *ptr); //中序遍歷TNODE *root=NULL;void inOrder(TNODE *ptr){if(ptr!=NULL){inOrder(ptr->lchild);printf("%d ", ptr->data);inOrder(ptr->rchild);}}void create(){int n, i;int k[MAX];printf("Please input the node number:\n");scanf("%d", &n);for(i=0; i<n; i++)scanf("%d",&k[i]);for(i=0; i<n; i++)insert(k[i]);}void insert(int m){TNODE *p1, *p2;if(root==NULL){root=(TNODE *)malloc(sizeof(TNODE));root->data=m;root->lchild=root->rchild=NULL;}else{p1=root;while(m!=p1->data){if((m<p1->data) && (p1->lchild!=NULL))p1=p1->lchild;else if((m>p1->data) && (p1->rchild!=NULL))p1=p1->rchild;else if((m<p1->data) && (p1->lchild==NULL)){p2=(TNODE *)malloc(sizeof(TNODE));p2->data=m;p2->lchild=p2->rchild=NULL;p1->lchild=p2;return;}else if((m>p1->data) && (p1->rchild==NULL)){p2=(TNODE *)malloc(sizeof(TNODE));p2->data=m;p2->lchild=p2->rchild=NULL;p1->rchild=p2;return;}}}}int main(){create();printf("\n");inOrder(root);printf("\n");return 0;}? ? ?Ctrl+F5執(zhí)行SortTree.cpp輸出結(jié)果例如以下：

? ? ??

? ? ? B.求出二叉排序樹T中小于x的最大元素和大于x的最小元素

? ? ? 在二叉排序樹中。一個小于樹中某個結(jié)點的最大元素，是在中序序列中這個結(jié)點的直接前驅(qū)；大于這個
結(jié)點的最小元素，是在中序序列中這個結(jié)點的直接后繼。
? ? ? 其程序例如以下：

#include<stdio.h>#include<stdlib.h>#define MAX 100typedef struct tnode{int data;struct tnode *lchild, *rchild;}TNODE;int last=0;void create();void insert(int m); //插入二叉排序樹的結(jié)點void findMaxMin(int aim, TNODE *ptr);TNODE *root=NULL;void findMaxMin(int aim, TNODE *ptr){if(ptr!=NULL){findMaxMin(aim, ptr->lchild);if(last<aim && ptr->data>=aim) //找到小于aim的最大元素printf("a=%d\n",last);if(last<=aim && ptr->data>aim) //找到大于aim的最小元素printf("b=%d\n",ptr->data);last=ptr->data;findMaxMin(aim, ptr->rchild);}}void create(){int n, i;int k[MAX];printf("Please input the node number:\n");scanf("%d", &n);for(i=0; i<n; i++)scanf("%d",&k[i]);for(i=0; i<n; i++)insert(k[i]);}void insert(int m){TNODE *p1, *p2;if(root==NULL){root=(TNODE *)malloc(sizeof(TNODE));root->data=m;root->lchild=root->rchild=NULL;}else{p1=root;while(m!=p1->data){if((m<p1->data) && (p1->lchild!=NULL))p1=p1->lchild;else if((m>p1->data) && (p1->rchild!=NULL))p1=p1->rchild;else if((m<p1->data) && (p1->lchild==NULL)){p2=(TNODE *)malloc(sizeof(TNODE));p2->data=m;p2->lchild=p2->rchild=NULL;p1->lchild=p2;return;}else if((m>p1->data) && (p1->rchild==NULL)){p2=(TNODE *)malloc(sizeof(TNODE));p2->data=m;p2->lchild=p2->rchild=NULL;p1->rchild=p2;return;}}}}int main(){int toBeFind;create();printf("\n");printf("Input the record to be finded! \n");scanf("%d", &toBeFind);findMaxMin(toBeFind, root);printf("\n");return 0;}? ? ?Ctrl+F5執(zhí)行SortTree1.cpp輸出結(jié)果例如以下：

? ? ?

總結(jié)

以上是生活随笔為你收集整理的二叉排序树(BST)构造与应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。