歡迎來到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁 裝配圖網(wǎng) > 資源分類 > DOC文檔下載  

數(shù)據(jù)結(jié)構(gòu)C語言版 平衡二叉樹

  • 資源ID:61675534       資源大?。?span id="ca4oqko" class="font-tahoma">24KB        全文頁數(shù):7頁
  • 資源格式: DOC        下載積分:5積分
快捷下載 游客一鍵下載
會員登錄下載
微信登錄下載
三方登錄下載: 微信開放平臺登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要5積分
郵箱/手機:
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機號,方便查詢和重復下載(系統(tǒng)自動生成)
支付方式: 支付寶    微信支付   
驗證碼:   換一換

 
賬號:
密碼:
驗證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會被瀏覽器默認打開,此種情況可以點擊瀏覽器菜單,保存網(wǎng)頁到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無水印,預覽文檔經(jīng)過壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標題沒有明確說明有答案則都視為沒有答案,請知曉。

數(shù)據(jù)結(jié)構(gòu)C語言版 平衡二叉樹

/*數(shù)據(jù)結(jié)構(gòu)C語言版 平衡二叉樹 P236編譯環(huán)境:Dev-C+ 4.9.9.2日期:2011年2月15日 */#include <stdio.h>#include <malloc.h>#define LH +1/ 左高 #define EH 0/ 等高 #define RH -1/ 右高 #define N 5/ 數(shù)據(jù)元素個數(shù) typedef char KeyType; / 設(shè)關(guān)鍵字域為字符型 typedef structKeyType key;int order;ElemType; / 數(shù)據(jù)元素類型 / 平衡二叉樹的類型 typedef struct BSTNodeElemType data;/ bf結(jié)點的平衡因子,只能夠取0,-1,1,它是左子樹的深度減去/ 右子樹的深度得到的int bf; struct BSTNode *lchild,*rchild; / 左、右孩子指針 BSTNode,*BSTree;/ 構(gòu)造一個空的動態(tài)查找表DTint InitDSTable(BSTree *DT) *DT=NULL;return 1;/ 銷毀動態(tài)查找表DT void DestroyDSTable(BSTree *DT) if(*DT) / 非空樹 if(*DT)->lchild) / 有左孩子 DestroyDSTable(&(*DT)->lchild); / 銷毀左孩子子樹 if(*DT)->rchild) / 有右孩子 DestroyDSTable(&(*DT)->rchild); / 銷毀右孩子子樹 free(*DT); / 釋放根結(jié)點 *DT=NULL; / 空指針賦0 / 算法9.5(a) / 在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素, / 若查找成功,則返回指向該數(shù)據(jù)元素結(jié)點的指針,否則返回空指針。BSTree SearchBST(BSTree T,KeyType key)if(!T)| (key = T->data.key)return T; / 查找結(jié)束 else if(key < T->data.key) / 在左子樹中繼續(xù)查找 return SearchBST(T->lchild,key);elsereturn SearchBST(T->rchild,key); / 在右子樹中繼續(xù)查找 / 算法9.9 P236/ 對以*p為根的二叉排序樹作右旋處理,處理之后p指向新的樹根結(jié)點,即旋轉(zhuǎn) / 處理之前的左子樹的根結(jié)點。void R_Rotate(BSTree *p) BSTree lc;lc=(*p)->lchild; / lc指向p的左子樹根結(jié)點 (*p)->lchild=lc->rchild; / lc的右子樹掛接為p的左子樹 lc->rchild=*p;*p=lc; / p指向新的根結(jié)點 / 算法9.10 P236 / 對以*p為根的二叉排序樹作左旋處理,處理之后p指向新的樹根結(jié)點,即旋轉(zhuǎn) / 處理之前的右子樹的根結(jié)點。void L_Rotate(BSTree *p)BSTree rc;rc=(*p)->rchild; / rc指向p的右子樹根結(jié)點 (*p)->rchild=rc->lchild; / rc的左子樹掛接為p的右子樹 rc->lchild=*p;*p=rc; / p指向新的根結(jié)點 / 算法9.12 P238/ 對以指針T所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處理,本算法結(jié)束時, / 指針T指向新的根結(jié)點。void LeftBalance(BSTree *T)BSTree lc,rd;lc=(*T)->lchild; / lc指向*T的左子樹根結(jié)點 switch(lc->bf) / 檢查*T的左子樹的平衡度,并作相應(yīng)平衡處理 case LH: / 新結(jié)點插入在*T的左孩子的左子樹上,要作單右旋處理 (*T)->bf=lc->bf=EH;R_Rotate(T);break;case RH: / 新結(jié)點插入在*T的左孩子的右子樹上,要作雙旋處理 rd=lc->rchild; / rd指向*T的左孩子的右子樹根 switch(rd->bf) / 修改*T及其左孩子的平衡因子 case LH:(*T)->bf=RH;lc->bf=EH;break;case EH: (*T)->bf=lc->bf=EH;break;case RH:(*T)->bf=EH;lc->bf=LH;rd->bf=EH;L_Rotate(&(*T)->lchild); / 對*T的左子樹作左旋平衡處理 R_Rotate(T); / 對*T作右旋平衡處理 / 對以指針T所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理,本算法結(jié)束時, / 指針T指向新的根結(jié)點void RightBalance(BSTree *T)BSTree rc,rd;rc=(*T)->rchild; / rc指向*T的右子樹根結(jié)點 switch(rc->bf) / 檢查*T的右子樹的平衡度,并作相應(yīng)平衡處理 case RH: / 新結(jié)點插入在*T的右孩子的右子樹上,要作單左旋處理 (*T)->bf=rc->bf=EH;L_Rotate(T);break;case LH: / 新結(jié)點插入在*T的右孩子的左子樹上,要作雙旋處理 rd=rc->lchild; / rd指向*T的右孩子的左子樹根 switch(rd->bf) / 修改*T及其右孩子的平衡因子 case RH: (*T)->bf=LH;rc->bf=EH;break;case EH: (*T)->bf=rc->bf=EH;break;case LH: (*T)->bf=EH;rc->bf=RH;rd->bf=EH;R_Rotate(&(*T)->rchild); / 對*T的右子樹作右旋平衡處理 L_Rotate(T); / 對*T作左旋平衡處理 / 算法9.11 / 若在平衡的二叉排序樹T中不存在和e有相同關(guān)鍵字的結(jié)點,則插入一個 / 數(shù)據(jù)元素為e的新結(jié)點,并返回1,否則返回0。若因插入而使二叉排序樹 / 失去平衡,則作平衡旋轉(zhuǎn)處理,布爾變量taller反映T長高與否。 int InsertAVL(BSTree *T,ElemType e,int *taller)if(!*T) / 插入新結(jié)點,樹“長高”,置taller為1 *T=(BSTree)malloc(sizeof(BSTNode);(*T)->data=e;(*T)->lchild=(*T)->rchild=NULL;(*T)->bf=EH;*taller=1;elseif(e.key = (*T)->data.key) / 樹中已存在和e有相同關(guān)鍵字的結(jié)點則不再插入 *taller=0;return 0;if(e.key < (*T)->data.key) / 應(yīng)繼續(xù)在*T的左子樹中進行搜索 if(!InsertAVL(&(*T)->lchild,e,taller) / 未插入 return 0;if(*taller)/ 已插入到*T的左子樹中且左子樹“長高” switch(*T)->bf) / 檢查*T的平衡度 case LH:/ 原本左子樹比右子樹高,需要作左平衡處理 LeftBalance(T);*taller=0;/標志沒長高break;case EH:/ 原本左、右子樹等高,現(xiàn)因左子樹增高而使樹增高 (*T)->bf=LH;*taller=1;/標志長高break;case RH:/ 原本右子樹比左子樹高,現(xiàn)左、右子樹等高(*T)->bf=EH; *taller=0;/標志沒長高else/ 應(yīng)繼續(xù)在*T的右子樹中進行搜索 if(!InsertAVL(&(*T)->rchild,e,taller) / 未插入 return 0;if(*taller) / 已插入到T的右子樹且右子樹“長高” switch(*T)->bf) / 檢查T的平衡度 case LH: (*T)->bf=EH; / 原本左子樹比右子樹高,現(xiàn)左、右子樹等高 *taller=0; break; case EH: / 原本左、右子樹等高,現(xiàn)因右子樹增高而使樹增高 (*T)->bf=RH; *taller=1; break; case RH: / 原本右子樹比左子樹高,需要作右平衡處理 RightBalance(T); *taller=0;return 1;/ 按關(guān)鍵字的順序?qū)T的每個結(jié)點調(diào)用函數(shù)Visit()一次void TraverseDSTable(BSTree DT,void(*Visit)(ElemType) if(DT)TraverseDSTable(DT->lchild,Visit); / 先中序遍歷左子樹 Visit(DT->data); / 再訪問根結(jié)點 TraverseDSTable(DT->rchild,Visit); / 最后中序遍歷右子樹 void print(ElemType c)printf("(%d,%d)",c.key,c.order);int main()BSTree dt,p;int k;int i;KeyType j;ElemType rN=13,1,24,2,37,3,90,4,53,5; / (以教科書P234圖9.12為例) InitDSTable(&dt);/ 初始化空樹 for(i=0;i<N;i+)InsertAVL(&dt,ri,&k); / 建平衡二叉樹 TraverseDSTable(dt,print); / 按關(guān)鍵字順序遍歷二叉樹 printf("n請輸入待查找的關(guān)鍵字: ");scanf("%d",&j);p=SearchBST(dt,j); / 查找給定關(guān)鍵字的記錄 if(p)print(p->data);elseprintf("表中不存在此值");printf("n");DestroyDSTable(&dt);system("pause");return 0;/*輸出效果:(13,1)(24,2)(37,3)(53,5)(90,4)請輸入待查找的關(guān)鍵字: 53(53,5)請按任意鍵繼續(xù). . . */

注意事項

本文(數(shù)據(jù)結(jié)構(gòu)C語言版 平衡二叉樹)為本站會員(細水****9)主動上傳,裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng)(點擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因為網(wǎng)速或其他原因下載失敗請重新下載,重復下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!