一、定義

? ? ? ? 二叉搜索樹(binary search tree)，又叫二叉查找樹、二叉排序樹。若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 它的左、右子樹也分別為二叉排序樹。二叉搜索樹作為一種經(jīng)典的數(shù)據(jù)結構，它既有鏈表的快速插入與刪除操作的特點，又有數(shù)組快速查找的優(yōu)勢；所以應用十分廣泛，例如在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)一般會采用這種數(shù)據(jù)結構進行高效率的排序與檢索操作。

二、特性? ? ? ?

????????在二叉搜索樹中：

????????1.若任意結點的左子樹不空，則左子樹上所有結點的值均不大于它的根結點的值。

????????2. 若任意結點的右子樹不空，則右子樹上所有結點的值均不小于它的根結點的值。

????????3.任意結點的左、右子樹也分別為二叉搜索樹。

三、操作

????????BStree *insertBST(BStree *pBST,Elementtype value);//遞歸插入
????????BStree *insertBST1(BStree *pBST,Elementtype value);//非遞歸插入?
????????BStree *delBST(BStree *pBST,Elementtype value);//遞歸刪除
????????BStree *delBST1(BStree *pBST,Elementtype value);//非遞歸刪除

????????BStree *min(BStree *pBST);//取樹中最小值?
????????BStree *max(BStree *pBST);//取樹中最大值
????????void cleanBST(BStree **pBST);//清空樹

????????void Preordertraversal(BStree *pBST);//前序遍歷
????????void Inordertraversal(BStree *pBST);//中序遍歷
????????void Postordertraversal(BStree *pBST);//后續(xù)遍歷

四、時間復雜度

????????不論哪一種操作，所花的時間都和樹的高度成正比。因此，如果共有n個元素，那么平均每次操作需要O(logn)的時間。

五、算法實現(xiàn)

????????二叉排序樹的操作主要有：

????????1.查找：遞歸查找是否存在key。

????????2.插入：原樹中不存在key，插入key返回true，否則返回false。

????????3.構造：循環(huán)的插入操作。

????????4.刪除：（1）葉子節(jié)點：直接刪除，不影響原樹。

????????（2）僅僅有左或右子樹的節(jié)點：節(jié)點刪除后，將它的左子樹或右子樹整個移動到刪除節(jié)點的位置就可以，子承父業(yè)。

????????（3）既有左又有右子樹的節(jié)點：找到須要刪除的節(jié)點p左子樹上的最大值或者右子樹上的最小值，賦給p，然后刪除該最大值或者最小值節(jié)點。

上代碼：

?頭文件：

#include <stdio.h> #include <stdlib.h> #ifndef BSTREE_H #define BSTREE_H typedef struct node BStree; typedef int Elementtype; struct node{Elementtype value;BStree *left;BStree *right; }; #endif BStree *insertBST(BStree *pBST,Elementtype value);//遞歸插入 BStree *insertBST1(BStree *pBST,Elementtype value);//非遞歸插入 BStree *delBST(BStree *pBST,Elementtype value);//遞歸刪除 BStree *delBST1(BStree *pBST,Elementtype value);//非遞歸刪除BStree *min(BStree *pBST);//取樹中最小值 BStree *max(BStree *pBST);//取樹中最大值 void cleanBST(BStree **pBST);//清空樹void Preordertraversal(BStree *pBST); void Inordertraversal(BStree *pBST); void Postordertraversal(BStree *pBST);

函數(shù)實現(xiàn)代碼?：

#include "BStree.h"//typedef struct node BStree; //typedef int Elementtype; //struct node{ // Elementtype value; // BStree *left; // BStree *right; //};BStree *insertBST(BStree *pBST,Elementtype value){//遞歸插入if(!pBST){BStree *pNode=(BStree*)malloc(sizeof(BStree));pNode->value=value;pNode->left=pNode->right=NULL;pBST=pNode;}else{if(value<pBST->value){pBST->left=insertBST(pBST->left,value);}else if(value>pBST->value){pBST->right=insertBST(pBST->right,value);}}return pBST; } BStree *insertBST1(BStree *pBST,Elementtype value){//非遞歸插入 BStree *ptemp=pBST;BStree *pNode=(BStree*)malloc(sizeof(BStree));pNode->value=value;pNode->left=pNode->right=NULL;BStree *parent=NULL;if(!pBST){ptemp=pNode;}else{while(pBST){parent=pBST;if(value<pBST->value){pBST=pBST->left;if(!pBST) parent->left=pNode;}else if(value>pBST->value){pBST=pBST->right;if(!pBST) parent->right=pNode;}}}return ptemp; } BStree *delBST(BStree *pBST,Elementtype value){//遞歸刪除 if(pBST){if(value<pBST->value){pBST->left=delBST(pBST->left,value);}else if(value>pBST->value){pBST->right=delBST(pBST->right,value);}else{if(pBST->left&&pBST->right){BStree *ptemp=min(pBST->right);pBST->value=ptemp->value;pBST->right=delBST(pBST->right,ptemp->value);}else if(!pBST->left){BStree *ptemp=pBST;pBST=pBST->right;free(ptemp);}else if(!pBST->right){BStree *ptemp=pBST;pBST=pBST->left;free(ptemp);}}}return pBST; } /*非遞歸刪除，當找到欲刪除結點ptemp時需同時記錄父節(jié)點parent，刪除后將parent和ptemp的后續(xù)節(jié)點鏈接*/ BStree *delBST1(BStree *pBST,Elementtype value){//非遞歸刪除BStree *parent=NULL;BStree *ptemp=pBST;while(ptemp){//循環(huán)條件ptemp不為空，當欲刪除值不存在則ptemp最終為空 parent=ptemp;//記錄當前節(jié)點的父節(jié)點 if(value<ptemp->value){//value小于當前節(jié)點值，向左查找 ptemp=ptemp->left;}else if(value>ptemp->value){//反之向右查找 ptemp=ptemp->right;}if(ptemp&&ptemp->value==value){//ptemp不為空，且value等于當前節(jié)點值，需要考慮節(jié)點同時有左右子樹，左子樹為空，右子樹為空三種情況 if(!ptemp->left){if(parent->left==ptemp){parent->left=ptemp->right;free(ptemp);}else if(parent->right==ptemp){parent->right=ptemp->right;free(ptemp); }}else if(!ptemp->right){if(parent->left==ptemp){parent->left=ptemp->left;free(ptemp);}else if(parent->right==ptemp){parent->right=ptemp->left;}}else if(ptemp->left&&ptemp->right){//當同時有左右子樹，可轉(zhuǎn)換為刪除右子樹上的最小值或者左子樹上的最大值 BStree *p=min(ptemp->right);ptemp->value=p->value;BStree *q=ptemp->right;parent=ptemp;while(q->value!=p->value){parent=q;q=q->left;}if(q==ptemp->right) parent->right=q->right;//父節(jié)點位于右子樹上父節(jié)點為ptemp兩種情況 else parent->left=q->right;free(q);break;//此種情況刪除了其他節(jié)點代替了ptemp，需要break跳出循環(huán)。 }}}if(!ptemp){printf("刪除值不存在\n");}return pBST; } BStree *min(BStree *pBST){//取樹中最小值 if(pBST){while(pBST->left){pBST=pBST->left;}return pBST;} } BStree *max(BStree *pBST){//取樹中最大值if(pBST){while(pBST->right){pBST=pBST->right;}return pBST;} } void cleanBST(BStree **pBST){//清空樹 if(*pBST){cleanBST(&(*pBST)->left);cleanBST(&(*pBST)->right);free(*pBST);*pBST=NULL;} } /*遍歷驗證程序*/ void Preordertraversal(BStree *pBST){if(pBST){printf("%d ",pBST->value);Preordertraversal(pBST->left);Preordertraversal(pBST->right);} } void Inordertraversal(BStree *pBST){if(pBST){Inordertraversal(pBST->left);printf("%d ",pBST->value);Inordertraversal(pBST->right);} } void Postordertraversal(BStree *pBST){if(pBST){Postordertraversal(pBST->left);Postordertraversal(pBST->right);printf("%d ",pBST->value);} }

main函數(shù) ：

#include <stdio.h> #include <stdlib.h> #include "BStree.h" /* run this program using the console pauser or add your own getch, system("pause") or input loop */int main(int argc, char *argv[]) {BStree *pBST=NULL;Elementtype value;scanf("%d",&value);while(value!=-1){pBST=insertBST1(pBST,value);scanf("%d",&value);}pBST=delBST(pBST,9);pBST=delBST1(pBST,5); pBST=delBST1(pBST,9);Preordertraversal(pBST);printf("\n");Inordertraversal(pBST);printf("\n");Postordertraversal(pBST);printf("\n");cleanBST(&pBST);if(!pBST) printf("樹已空\n"); return 0; }

總結

以上是生活随笔為你收集整理的数据结构——二叉搜索树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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