|
http://blog.csdn.net/chenbolyfxinsui/article/details/25461817 2014/5/10 by lyf @七里外風(fēng)車磨坊 今天我們來討論討論二叉查找樹,首先我們來看看二叉查找樹的概念.
什么是二叉查找樹呢?顧名思義，二叉查找樹是按照二叉樹的結(jié)構(gòu)來進(jìn)行組織的，這樣的一棵二叉樹可以采用鏈表的形式來加以描述,這樣的鏈表包含兩個(gè)指針域 （left_child,right_child），以及一個(gè)數(shù)據(jù)域(data) 樹中的每個(gè)節(jié)點(diǎn)NODE，都采用鏈表中的節(jié)點(diǎn)加以表示，left_child與right_child分別指向樹中節(jié)點(diǎn)的左孩子與右孩子，若樹中的節(jié)點(diǎn)沒有左孩子或者右孩子，則對(duì)應(yīng)的left_child或者right_child為空NULL。樹的葉子節(jié)點(diǎn)左右孩子均為空。二叉查找樹除了滿足上述基本的性質(zhì)之外，還應(yīng)滿足如下的二叉查找樹的性質(zhì)： 設(shè)a為二叉查找樹中的一個(gè)節(jié)點(diǎn)（這里假設(shè)使用data(a)為取節(jié)點(diǎn)a對(duì)應(yīng)的數(shù)據(jù)域,后面的操作于此相同） 1. 若b為a的左子樹中的一個(gè)節(jié)點(diǎn),則必定有data(a)>data(b),即以a為根節(jié)點(diǎn)的左子樹中的任意節(jié)點(diǎn)b的數(shù)據(jù)域都不大于a節(jié)點(diǎn)的數(shù)據(jù)域。 2. 若b為a的右子樹中的一個(gè)節(jié)點(diǎn),則必定有data(a)<=data(b),即以a為根節(jié)點(diǎn)的右子樹中的任意節(jié)點(diǎn)b的數(shù)據(jù)與都不小于a節(jié)點(diǎn)的數(shù)據(jù)域。 3. 二叉查找樹，按照中序遍歷該二叉查找樹，其輸出結(jié)果是有序的。
如下圖所示即為滿足二叉查找樹的一棵樹  下面我們采用c語言來描述二叉查找樹以及對(duì)二叉查找樹的相關(guān)操作。
一、使用c語言定義二叉樹的數(shù)據(jù)結(jié)構(gòu) typedef struct TreeNode{ void *data; //數(shù)據(jù)域 struct TreeNode* left_child; //左指針域 struct TreeNode* right_child;//右指針域 }TreeNode,*BinaryTree; 根據(jù)二叉查找樹的定義，我們采用結(jié)構(gòu)體定義二叉查找樹,該結(jié)構(gòu)體中包含了一個(gè)數(shù)據(jù)域（data）,和兩個(gè)指向該結(jié)構(gòu)體類型的兩個(gè)指針域(left_child,right_child).分別用于指向當(dāng)前節(jié)點(diǎn)的左孩子和右孩子。其實(shí)在這個(gè)結(jié)構(gòu)體中我們還可以增加一個(gè)指針域,用于指向節(jié)點(diǎn)的父節(jié)點(diǎn)（parent)。
二.二叉查找樹的基本操作.
在二叉查找樹中，我們提供了創(chuàng)建一棵二叉查找樹，插入新的節(jié)點(diǎn)到二叉查找樹中,以及遍歷這顆二叉查找樹,刪除二叉查找樹中的某個(gè)節(jié)點(diǎn)，查找節(jié)點(diǎn)是否存在二叉查找樹中.
1.首先我么來討論插入一個(gè)節(jié)點(diǎn)到二叉查找樹中。 分析:既然要插入一個(gè)節(jié)點(diǎn)到二叉查找樹中，我們首先是要找到這個(gè)節(jié)點(diǎn)應(yīng)該插入到二叉查找樹的什么位置上。 顯而易見的是新插入的節(jié)點(diǎn)一定是作為一個(gè)葉子節(jié)點(diǎn)存在二叉查找樹中的。 繼續(xù)，怎樣找到這個(gè)節(jié)點(diǎn)應(yīng)該插入到二叉查找樹的什么位置上呢? 其實(shí)我們只需要用待插入的節(jié)點(diǎn)從二叉查找樹的根節(jié)點(diǎn)遍歷這顆二叉查找樹，用待插入的節(jié)點(diǎn)去和二叉查找樹中的節(jié)點(diǎn)進(jìn)行比較，若待插入的節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)的值小 則進(jìn)入到當(dāng)前節(jié)點(diǎn)的左子樹中進(jìn)行比較，否則進(jìn)入到當(dāng)前節(jié)點(diǎn)的右子樹中進(jìn)行比較,如此返回操作.直到當(dāng)前的節(jié)點(diǎn)的左或右孩子為空，根據(jù)當(dāng)前節(jié)點(diǎn)的大小判斷 待插入的節(jié)點(diǎn)應(yīng)該插入在當(dāng)前節(jié)點(diǎn)的左孩子(若當(dāng)前節(jié)點(diǎn)值大于待插入節(jié)點(diǎn)的值)，還是右孩子中。 注意:需要注意的是若二叉查找樹最開始就沒有，即為一棵空二叉查找樹,則我們就直接用待插入的新節(jié)點(diǎn)作為整個(gè)二叉查找樹的根節(jié)點(diǎn)即可.
如下圖模擬11插入到一棵二叉查找樹中
code:使用c語言實(shí)現(xiàn)二叉樹的插入操作。//插入節(jié)點(diǎn)到二叉查找樹中 //插入節(jié)點(diǎn)到二叉查找樹中 void InsertNode(BinaryTree* root,const void *data,int size,int(*comp)(const void*,const void*)){
if(*root==NULL){//二叉樹為一棵空樹
InitBinaryTree(root,data,size); //將當(dāng)前節(jié)點(diǎn)作為二叉查找樹的根節(jié)點(diǎn) return; } //分配待插入的新節(jié)點(diǎn) TreeNode*newNode=(TreeNode*)malloc(sizeof(TreeNode)); newNode->data=(void*)malloc(size); memcpy(newNode->data,data,size); newNode->left_child=newNode->right_child=NULL;
//對(duì)節(jié)點(diǎn)進(jìn)行遍歷操作，尋找查找位置 TreeNode*node=(*root); while(node->left_child!=newNode&&node->right_child!=newNode){ if(comp(data,node->data)<0){//待插入的節(jié)點(diǎn)值大于該節(jié)點(diǎn)的值 if(node->left_child==NULL) node->left_child=newNode; else node=node->left_child; }else{ if(node->right_child==NULL){ node->right_child=newNode; } else node=node->right_child; } } } //創(chuàng)建一棵二叉查找樹，即初始化根節(jié)點(diǎn) void InitBinaryTree(BinaryTree* root,const void *data,int size){ *root=(BinaryTree)malloc(sizeof(TreeNode)); (*root)->data=(void*)malloc(size); (*root)->left_child=(*root)->right_child=NULL; memcpy((*root)->data,data,size); }
2.二叉查找樹的遍歷操作。 根據(jù)二叉查找樹的性質(zhì)可以知道,按照中序的方式遍歷一棵二叉查找樹，遍歷出來的順序即為一個(gè)有序的序列. 遍歷操作的時(shí)候，我們按照遞歸的方式進(jìn)行遍歷，即先遍歷二叉查找樹的左子樹，在遍歷二叉查找樹的右子樹。 當(dāng)然我們也可以借助于棧進(jìn)行非遞歸遍歷操作.
code:c語言遍歷二叉查找樹(遞歸方式） //遍歷這顆二叉排序樹 void showTree(BinaryTree root,void (*print)(const void*)){ if(root!=NULL){ showTree(root->left_child,print); print(root->data); showTree(root->right_child,print); } } 3.查找值是否存在于二叉查找樹中. 查找值是否存在于二叉查找樹中只需要,只需要遍歷該二叉查找樹，使用二叉查找樹中的每個(gè)節(jié)點(diǎn)和帶查找的值進(jìn)行比較，若該節(jié)點(diǎn)的值小于待查找節(jié)點(diǎn)的值 則進(jìn)入到節(jié)點(diǎn)的左孩子中查找操作，否則進(jìn)入到右孩子節(jié)點(diǎn)中查找操作.直到找到節(jié)點(diǎn)的值為待查找的值,否則二叉查找樹中不存在待查找的節(jié)點(diǎn). cod:c 語言實(shí)現(xiàn)查找節(jié)點(diǎn)是否存在于二叉查找樹中 //查找指定的節(jié)點(diǎn)是否存在于二叉排序樹中 int findDataInBinarryTree(BinaryTreeroot,void *data,int(*comp)(const void*,const void*)){ TreeNode*node=root; while(NULL!=node){ if(comp(node->data,data)==0){ return 1; }else if(comp(node->data,data)>0){ node=node->left_child; }else{ node=node->right_child; } } return 0; } 遞歸方式實(shí)現(xiàn)查找: int findDataInBinarryTree(BinaryTree root,void *data,int (*comp)(const void*,const void*)){
if(NULL!=root){ if(comp(root->data,data)==0){ return 1; } if(comp(root->data,data)>0){ return findDataInBinarryTree(root->left_child,data,comp); }else{ return findDataInBinarryTree(root->right_child,data,comp); } } return 0; }
4.二叉查找樹的刪除操作 二叉查找樹的刪除，應(yīng)該算是這幾個(gè)操作中比較復(fù)雜的一個(gè)。 二叉查找樹在刪除節(jié)點(diǎn)后應(yīng)該保證二叉查找樹的性質(zhì),因此在執(zhí)行刪除操作后任然需要保證這一棵二叉樹為一棵二叉查找樹 刪除操作進(jìn)行的第一步操作是首先要查找到待刪除的節(jié)點(diǎn)。 （1）首先我們想到的是待刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，即我們只需要將待刪除節(jié)點(diǎn)（葉子節(jié)點(diǎn)）直接從二叉查找樹中刪除即可，因?yàn)閯h除葉子節(jié)點(diǎn)不會(huì)破壞二叉查找樹的性質(zhì)。 如下圖所示:（需要注意的是若待刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)，即只有一個(gè)節(jié)點(diǎn)的樹，直接將根節(jié)點(diǎn)賦值為空，刪除根節(jié)點(diǎn)即可)
(2) 若待刪除的節(jié)點(diǎn)不是葉子節(jié)點(diǎn),但是以待刪除節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹是一棵單子樹（即待刪除節(jié)點(diǎn)的左右孩子只有一個(gè)存在),則需要做的操作是將待刪除節(jié)點(diǎn)父節(jié)點(diǎn)的指向修改為待刪除節(jié)點(diǎn)的孩子節(jié)點(diǎn)(即左孩子或右孩子），然后刪除該節(jié)點(diǎn)即可（特別的當(dāng)刪除的節(jié)點(diǎn)為根節(jié)點(diǎn),則將待刪除節(jié)點(diǎn)的左孩子或右孩子的節(jié)點(diǎn)作為根節(jié)點(diǎn)即可)。 （3）若待刪除的節(jié)點(diǎn)的左右子樹均不為空，則我們?cè)谶M(jìn)行節(jié)點(diǎn)刪除操作后需要保持二叉查找樹的性質(zhì)，則需要做的操作是以待刪除節(jié)點(diǎn)的左孩子為根節(jié)點(diǎn)的子樹k中尋找最大的節(jié)點(diǎn)值r（遍歷子樹的右子樹），將節(jié)點(diǎn)r的值賦值給待刪除節(jié)點(diǎn)h的值，將節(jié)點(diǎn)r的左子樹賦值給節(jié)點(diǎn)r父節(jié)點(diǎn)的右孩子，刪除節(jié)點(diǎn)r即可.（如圖七所示)
特別地，當(dāng)子樹k的右孩子為空，則節(jié)點(diǎn)k即為待刪除節(jié)點(diǎn)h的左子樹中的最大節(jié)點(diǎn)，則將節(jié)點(diǎn)k的值賦給待刪除節(jié)點(diǎn)h,讓節(jié)點(diǎn)k的父節(jié)點(diǎn)的左孩子指向節(jié)點(diǎn)k的左孩子,刪除節(jié)點(diǎn)k即可。 實(shí)際上在子樹k的右孩子為空的時(shí)候我們還要另外的一種思考方式，即改變待刪除節(jié)點(diǎn)h的父節(jié)點(diǎn)c指向，若待刪除節(jié)點(diǎn)h,為父節(jié)點(diǎn)c的左孩子，則父節(jié)點(diǎn)c的左孩子指向?yàn)榇齽h除節(jié)點(diǎn)h的左孩子節(jié)點(diǎn)k，若待刪除節(jié)點(diǎn)h為右孩子，則父節(jié)點(diǎn)c的右孩子指向?yàn)榇齽h除節(jié)點(diǎn)h的左孩子節(jié)點(diǎn)k，將待刪除的節(jié)點(diǎn)h的右孩子m賦值給,待刪除節(jié)點(diǎn)h的左孩子k的右孩子，然后刪除節(jié)點(diǎn)h即可.(此種方式不需向圖八的方式給待刪除節(jié)點(diǎn)賦值操作).
code:c語言實(shí)現(xiàn)刪除二叉查找樹中的某個(gè)節(jié)點(diǎn) //刪除二叉查找樹中的某個(gè)節(jié)點(diǎn) void delTreeNode(BinaryTree* root,void *data,int size,int(*comp)(const void*,const void*)){ //在刪除一棵二叉查找樹的時(shí)候，需要保持二叉排序樹的特性，需要分幾種情況進(jìn)行刪除操作 //1.若待刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)直接將該節(jié)點(diǎn)刪除即可,并將父節(jié)點(diǎn)的對(duì)應(yīng)的指針賦值為空 TreeNode*delnode=(*root); //待刪除節(jié)點(diǎn) TreeNode*delnodeParent=(*root);//待刪除節(jié)點(diǎn)的父節(jié)點(diǎn) while(delnode!=NULL){ if(comp(data,delnode->data)<0){ delnodeParent=delnode; delnode=delnode->left_child; }else if(comp(data,delnode->data)>0){ delnodeParent=delnode; delnode=delnode->right_child; }else{ //查找到待刪除的節(jié)點(diǎn) break; } }
if(NULL==delnode) { printf("沒有查找到待刪除的節(jié)點(diǎn)!"); return; } //待刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn) if(delnode->left_child==NULL&&delnode->right_child==NULL){ //若待刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)，則直接刪除該節(jié)點(diǎn)即可，樹為空樹 if(delnode==*root) (*root)=NULL; else if(delnodeParent->left_child==delnode)//若待刪除的節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子 delnodeParent->left_child=NULL; else delnodeParent->right_child=NULL; //釋放該節(jié)點(diǎn)的內(nèi)存空間 free(delnode); delnode=NULL; }
//以待刪除節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹為單子樹，則修改待刪除節(jié)點(diǎn)父節(jié)點(diǎn)的孩子節(jié)點(diǎn)為待刪除節(jié)點(diǎn)的孩子 else if(delnode->left_child==NULL||delnode->right_child==NULL){ //同樣若待刪除的節(jié)點(diǎn)為根節(jié)點(diǎn),該變根節(jié)點(diǎn)的指針指向?yàn)榇齽h除節(jié)點(diǎn)的孩子節(jié)點(diǎn) if(delnode==*root){ if(delnode->left_child!=NULL) (*root)=delnode->left_child; else (*root)=delnode->right_child; } //待刪除節(jié)點(diǎn)不為根節(jié)點(diǎn) else{ if(delnodeParent->left_child==delnode){ if(delnode->left_child!=NULL) delnodeParent->left_child=delnode->left_child; else delnodeParent->left_child=delnode->right_child; }else{ if(delnode->left_child!=NULL) delnodeParent->right_child=delnode->left_child; else delnodeParent->right_child=delnode->right_child; } } free(delnode); delnode=NULL; }
//以待刪除節(jié)點(diǎn)的子樹都不為空,這里的做法是以待刪除節(jié)點(diǎn)的左孩子為根節(jié)點(diǎn)的子樹中尋找最大的節(jié)點(diǎn)， //即遍歷到該子樹最右邊的孩子節(jié)點(diǎn)將該節(jié)點(diǎn)的值賦值給待刪除節(jié)點(diǎn),刪除該節(jié)點(diǎn)即可 else if(delnode->left_child!=NULL&&delnode->right_child!=NULL){ TreeNode* tempNode=delnode->left_child; TreeNode*tempParentNode=delnode->left_child; while(tempNode->right_child!=NULL){ tempParentNode=tempNode; tempNode=tempNode->right_child; } memcpy(delnode->data,tempNode->data,size); if(tempNode==tempParentNode){ //待刪除節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的右子樹為空,則待刪除節(jié)點(diǎn)的左孩子即為尋找的節(jié)點(diǎn)，將尋找到的節(jié)點(diǎn)的左孩子連接到待刪除節(jié)點(diǎn)的左子樹上 delnode->left_child=tempNode->left_child; }else{ //找到待刪除節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的右子樹中較大節(jié)點(diǎn),將較大節(jié)點(diǎn)的父節(jié)點(diǎn)的右子樹連接到較大節(jié)點(diǎn)的左子樹 tempParentNode->right_child=tempNode->left_child; } free(tempNode); tempNode=NULL; } }
5.釋放二叉查找樹的內(nèi)存空間 二叉查找樹的空間是使用指針進(jìn)行內(nèi)存空間動(dòng)態(tài)分配的，所以在使用完畢之后我們不要忘記釋放所分配的內(nèi)存空間. 釋放一棵二叉查找樹的空間可以這樣操作，釋放這棵樹的左孩子，釋放這顆樹的右孩子，釋放根節(jié)點(diǎn).
code:c語言實(shí)現(xiàn)釋放二叉查找樹的動(dòng)態(tài)內(nèi)存空間
//釋放二叉查找樹的空間 void freeBinarySpace(BinaryTree* root){ //釋放二叉樹的內(nèi)存空間 if(*root!=NULL){ //釋放左子樹 freeBinarySpace(&(*root)->left_child); //釋放右子樹 freeBinarySpace(&(*root)->right_child); //釋放本身的內(nèi)存空間 free((*root)->data);//釋放數(shù)據(jù)域 (*root)->data=NULL; free((*root)); *root=NULL; } } 6.其他的一些輔助公共操作方法
int intBig(const void*data_one,const void*data_two){return *(int*)data_one-*(int*)data_two;} //打印輸出函數(shù) void printInt(const void*data){printf("%d",*(int*)data);}
三.二叉查找樹的算法分析 在二叉查找樹中查找一個(gè)關(guān)鍵字，恰好是走了一條從二叉樹的根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑的過程.在二叉查找樹中查找一個(gè)關(guān)鍵字與二叉樹中節(jié)點(diǎn)的比較次數(shù)最大不超過該二叉樹的深度. 當(dāng)含有n個(gè)節(jié)點(diǎn)的二叉查找樹的平均查找長(zhǎng)度是取決于二叉查找樹的形態(tài)的,當(dāng)在進(jìn)行二叉查找樹插入n個(gè)數(shù)據(jù)為有序的n個(gè)數(shù)據(jù)的時(shí)候，則得到的二叉查找樹為一棵單子樹,則樹的深度為n 則平均查找長(zhǎng)度為(n+1)/2.這是最極端的情況 最好的情況就是，建立的n個(gè)數(shù)據(jù)的二叉排序樹的形態(tài)與二分查找的判定樹相當(dāng),其平均查找長(zhǎng)度與log2(n) 成正比。 二叉查找樹的各項(xiàng)基本操作的運(yùn)行時(shí)間都是o(h)，h為二叉排序樹的高度，含有n個(gè)節(jié)點(diǎn)的二叉查找樹在最優(yōu)的情況下樹的高度為o(logn),所以要使得二叉查找樹最優(yōu)，就的使得 二叉查找樹的高度為o(logn),可以通過平衡二叉樹對(duì)其進(jìn)行優(yōu)化。
畢！
參考：算法導(dǎo)論第二版，數(shù)據(jù)結(jié)構(gòu)（c語言版) |
|
|
