數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)十

9i/n/Hoz:曜a09++OA:蜴燮將丁旱里++。：星里浦零嶇二凰去朝麗阿7敵工可爵：亦牟frSIZflOZ:備秦暮熟：gW4■魏物弱麟?實(shí)驗(yàn)內(nèi)容建立排序平衡二叉樹(shù)。輸入與輸出輸入：輸入一組節(jié)點(diǎn)，從而建立平衡排序二叉樹(shù)。輸出：輸出平衡二叉樹(shù)的先序，中序遍歷，以及每個(gè)節(jié)點(diǎn)的平衡因子，以便進(jìn)行還原二叉樹(shù)的形狀，判斷算法是否正確。關(guān)鍵數(shù)據(jù)結(jié)構(gòu)與核心算法關(guān)鍵數(shù)據(jù)結(jié)構(gòu)：因?yàn)槭嵌鏄?shù)，則要有基本的節(jié)點(diǎn)，左右孩子指針，因?yàn)橐判蛐D(zhuǎn)，則要知道平衡因子，注意此處可以根據(jù)需要來(lái)添加雙親指針，因?yàn)檫\(yùn)用了引用，則省去了此處。因此數(shù)據(jù)結(jié)構(gòu)為：typedefstructBSTNode{intdata;//信息intbf;//平衡因子structBSTNode*lchild,*rchild;〃平衡樹(shù)左右兒子指針}BSTNode,*BSTree;//平衡二叉排序樹(shù)結(jié)構(gòu)的定義核心算法:建立平衡排序二叉樹(shù)算是算法中比較復(fù)雜的一個(gè)了，但是找到核心之后，也就只是比較復(fù)雜一些罷了，多練習(xí)一下即可。那核心是什么呢？要回答這個(gè)問(wèn)題，就要深刻理解“平衡”和“排序"兩個(gè)詞的含義。顧名思義，平衡二叉樹(shù)加上排序二叉樹(shù)即是所要建的樹(shù)。1.平衡二叉樹(shù)要求每一個(gè)節(jié)點(diǎn)的左子樹(shù)深度減去右子樹(shù)的深度的絕對(duì)值要小于1。2.排序二叉樹(shù)要求按照中序遍歷該二叉樹(shù)得到從小到大排序的序列。因此在每插入一個(gè)結(jié)點(diǎn)的時(shí)候都要判斷是否平衡，1?若平衡則按照排序二叉樹(shù)的方法插入之，然后刷新平衡因子即可。2.重要是不平衡的時(shí)候就要從最接近的不平衡的地方旋轉(zhuǎn)的讓它平衡，這樣繼續(xù)下去，不斷插入就可以得到排序平衡二叉樹(shù)。下面主要解釋一下旋轉(zhuǎn)方法：旋轉(zhuǎn)共有4種方式，其實(shí)，最核心的只有兩種基本操作即是L_Rotate()和R_Rotate()，分別是左旋和右旋。對(duì)于LL型，即是最先出錯(cuò)的節(jié)點(diǎn)平衡因子是2,左兒子平衡因子是1，運(yùn)用一次右旋操作再刷新平衡因子即可。根據(jù)鏡像對(duì)稱(chēng)原則，RR型與此是對(duì)應(yīng)的，如法炮制即可。重要的并且復(fù)雜的是LR和RL操作，這兩個(gè)操作也是鏡像對(duì)稱(chēng)的只講一個(gè)即可。就比如LR吧，最先出錯(cuò)的節(jié)點(diǎn)的平衡因子是2,該節(jié)點(diǎn)的左孩子的平衡因子是?1?則要對(duì)左孩子為根的子樹(shù)進(jìn)行左旋，然后對(duì)該最近節(jié)點(diǎn)進(jìn)行右旋，刷新平衡因子即可。具體算法如下：■&s s s s s ■Ji*ZX-&&&&&&&&&&&&&&，/,mmmm*.兩個(gè)基本操作ummmm*/voidL_Rotate(BSTree&p){〃對(duì)以*p為根的二叉排序樹(shù)做左旋處理，處理之后p指向新的樹(shù)根結(jié)點(diǎn)//和R_Rotate()鏡像對(duì)稱(chēng)BSTreerc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;}voidR_Rotate(BSTree&p){〃對(duì)以*p為根的二叉排序樹(shù)做右旋處理，處理之后p指向新的樹(shù)根結(jié)點(diǎn)//注意此處引用的好處就是不用再出現(xiàn)雙親指針BSTreelc;lc=p->lchild;〃指向B的位置p->lchild=lc->rchild;/此處轉(zhuǎn)換仍保持中序遍歷不變性lc->rchild=p;//更改a的指針位置p=lc;//lc變成新的a/**********************四個(gè)旋轉(zhuǎn)操作，每?jī)蓚€(gè)在一起*****************/〃包含LL和LRvoidLeftBalance(BSTree&T){〃對(duì)已叮為根的二叉排序樹(shù)做左平衡旋轉(zhuǎn)處理BSTreelc,rd;lc=T->lchild;//lc調(diào)整左邊switch(lc->bf){caseLH://若是左邊高則為L(zhǎng)L型，只需旋轉(zhuǎn)即可T->bf=lc->bf=EH;//旋轉(zhuǎn)后平衡因子均為0R_Rotate(T);//LL型需要右旋轉(zhuǎn)break;case皿://若是右邊高，則為L(zhǎng)R型，需分兩步調(diào)整rd=lc->rchild;//找到不確定因子rdswitch(rd->bf)//對(duì)不確定因子進(jìn)行討論{case］日:〃左邊高調(diào)整后T->bf=RH;//根節(jié)點(diǎn)右邊變高lc->bf=EH;//lc變平衡break;caseEH://rd有左右節(jié)點(diǎn)T->bf=lc->bf=EH;//調(diào)整后持平break;case皿:〃右邊高T->bf=EH;//根節(jié)點(diǎn)平衡lc->bf=LH;//lc節(jié)點(diǎn)變成左邊高break;}rd->bf=EH;〃調(diào)整后rd節(jié)點(diǎn)一定平衡，且變成新的頭節(jié)點(diǎn)L_Rotate(T->lchild);//1.先左旋R_Rotate(T); //2.再右旋}}/*************右平衡操作，包含RR和RL*******************************/voidRightBalance(BSTree&T){〃對(duì)已*丁為根的二叉排序樹(shù)做右平衡旋轉(zhuǎn)處理〃因?yàn)闉長(zhǎng)eftBalance(BSTree&丁)的鏡像，注釋則省略BSTreelc,rd;lc=T->rchild;switch(lc->bf){case皿:〃右邊高，RR型T->bf=lc->bf=EH;L_Rotate(T);break;caseLHd/左邊高，RL型，分兩步旋轉(zhuǎn)rd=lc->lchild;switch(rd->bf){caseRH:T->bf=LH;lc->bf=EH;break;caseLH:T->bf=EH;lc->bf=RH;break;caseEH:T->bf=lc->bf=EH;break;}rd->bf=EH;R_Rotate(T->rchild);〃1先右旋L_Rotate(T); //2.再左旋}} 至于插入操作主要就是判斷樹(shù)是不是平衡，若不平衡是左邊還是右邊，對(duì)于添加的新節(jié)點(diǎn)改變了樹(shù)的平衡了沒(méi)有，改變了左邊的還是右邊的，然后進(jìn)行相應(yīng)的旋轉(zhuǎn)處理。具體算法如下：intInsertAVL(BSTree&T,intkey,bool&taller){//若在平衡二叉排序樹(shù)中不存在與關(guān)鍵字key相等的結(jié)點(diǎn)，則將關(guān)鍵字插入樹(shù)中//布爾變量taller表示樹(shù)是否“長(zhǎng)高”if(T==NULL){T=(BSTree)malloc(sizeof(BSTNode));T->data=key;T->bf=EH;//葉子結(jié)點(diǎn)其平衡因子肯定為0T->lchild=T->rchild=NULL;taller=1;//樹(shù)長(zhǎng)高了}else{if(key==T->data){//如果樹(shù)中已存放此關(guān)鍵字則不予插入taller=0;return0;}if(key<T->data){〃關(guān)鍵字小于根結(jié)點(diǎn)則插入其左子樹(shù)中if(!InsertAVL(T->lchild,key,taller))return0;if(taller){//如果樹(shù)長(zhǎng)高了，判斷是否平衡switch(T->bf){caseLHd/若左邊高，這次又加上一個(gè)左邊的節(jié)點(diǎn)，則肯定變?yōu)?,即需要調(diào)整LeftBalance(T);//不平衡時(shí)調(diào)用左平衡函數(shù)，使左子樹(shù)平衡taller=0;break;caseEH://若相等，在左邊加一個(gè)節(jié)點(diǎn)，則變?yōu)樽筮吀逿->bf=LH;taller=1;〃樹(shù)變高break;case皿://若右邊高，在左邊加一個(gè)節(jié)點(diǎn)，則持平T->bf=EH;taller=0;break;}}}else{//插入右子樹(shù)中if(!InsertAVL(T->rchild,key,taller))return0;if(taller){switch(T->bf){caseLH://同理，本來(lái)左邊高，在右邊加一個(gè)節(jié)點(diǎn)則持平T->bf=EH;taller=0;break;caseEH://右邊變高T->bf=RH;taller=1;break;case皿://右邊不平衡了，需要調(diào)整RightBalance(T);taller=0;break;}}}}return1;}理論與測(cè)試?yán)碚摚喝鐖D，給定一個(gè)序列的節(jié)點(diǎn)數(shù)組，按照幾種變換規(guī)則得到了圖示的排序二叉樹(shù)，可以得到三序遍歷和平衡因子。（由于圖形比較多，暫時(shí)為手工畫(huà)圖）該序列為：47,63,54,28,31,14,26,53,99,81先序遍歷：31，26，14,28,54,47,53,81，63，99中序遍歷：14,26,28,31,47,53,54,63,81,99平衡因子：31和47的平衡因子為-1，其他的都為0測(cè)試：運(yùn)行程序之后輸出為:

由先序和中序序列可以還原出樹(shù)的原型，對(duì)照可知結(jié)果是正確的。討論與體會(huì)排序二叉樹(shù)的中序遍歷結(jié)果即為升序排列，但是運(yùn)算速率不是最高的，為了尋找更好的方法，平衡排序二叉樹(shù)便誕生了。對(duì)于開(kāi)創(chuàng)者而言這是令人稱(chēng)贊的，但是對(duì)于后學(xué)者來(lái)說(shuō)，在學(xué)習(xí)算法的核心思想的同時(shí)，更重要的是別人是怎樣想到的，當(dāng)一個(gè)現(xiàn)實(shí)生活的需要放在眼前是，我們要有開(kāi)創(chuàng)的眼光，具有創(chuàng)新能力，這點(diǎn)是非常重要的，因?yàn)閷?duì)于應(yīng)用上來(lái)說(shuō)有了第一個(gè)其他的就不再令人驚奇了。同時(shí)，遞歸，引用，開(kāi)關(guān)、選擇分支語(yǔ)句的運(yùn)用也要引起注意。學(xué)習(xí)圖的最好方法，就是數(shù)形結(jié)合，一定要多畫(huà)圖。六?附錄（源代碼）#include<stdio.h>#include<stdlib.h>#include<iostream>usingnamespacestd;#defineLH1//左邊高#defineEH0//一樣高#defineRH-Uf右邊高typedefstructBSTNode{int《2也;〃信息intbf;//平衡因子structBSTNode*lchild,*rchild;〃平衡樹(shù)左右兒子指針}BSTNode,*BSTree;//平衡二叉排序樹(shù)結(jié)構(gòu)的定義voidR_Rotate(BSTree&p){〃對(duì)以*p為根的二叉排序樹(shù)做右旋處理，處理之后p指向新的樹(shù)根結(jié)點(diǎn)//注意此處引用的好處就是不用再出現(xiàn)雙親指針BSTreelc;lc=p->lchild;//指向B的位置p->lchild=lc->rchild;//此處轉(zhuǎn)換仍保持中序遍歷不變性lc->rchild=p;//更改a的指針位置p=lc;//lc變成新的a}voidL_Rotate(BSTree&p){〃對(duì)以*p為根的二叉排序樹(shù)做左旋處理，處理之后p指向新的樹(shù)根結(jié)點(diǎn)//和R_Rotate()鏡像對(duì)稱(chēng)BSTreerc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;}〃包含LL和LRvoidLeftBalance(BSTree&T){〃對(duì)已叮為根的二叉排序樹(shù)做左平衡旋轉(zhuǎn)處理BSTreelc,rd;lc=T->lchild;//lc調(diào)整左邊switch(lc->bf){caseLH://若是左邊高則為L(zhǎng)L型，只需旋轉(zhuǎn)即可T->bf=lc->bf=EH;/旋轉(zhuǎn)后平衡因子均為0R_Rotate(T);//LL型需要右旋轉(zhuǎn)break;case皿://若是右邊高，則為L(zhǎng)R型，需分兩步調(diào)整rd=lc->rchild;//找到不確定因子rdswitch(rd->bf)//對(duì)不確定因子進(jìn)行討論case1日:〃左邊高調(diào)整后T->bf=RH;//根節(jié)點(diǎn)右邊變高lc->bf=EH;//lc變平衡break;caseEH://rd有左右節(jié)點(diǎn)T->bf=lc->bf=EH;/調(diào)整后持平break;case皿:〃右邊高T->bf=EH;//根節(jié)點(diǎn)平衡lc->bf=LH;//lc節(jié)點(diǎn)變成左邊高break;}rd->bf=EH;//調(diào)整后rd節(jié)點(diǎn)一定平衡，且變成新的頭節(jié)點(diǎn)L_Rotate(T->lchild);//1先左旋R_Rotate(T); 〃2.再右旋/*************右平衡操作，包含RR和rl*******************************/voidRightBalance(BSTree&T){〃對(duì)已*T為根的二叉排序樹(shù)做右平衡旋轉(zhuǎn)處理〃因?yàn)闉長(zhǎng)eftBalance(BSTree&丁)的鏡像，注釋則省略BSTreelc,rd;lc=T->rchild;switch(lc->bf){case皿:〃右邊高，RR型T->bf=lc->bf=EH;L_Rotate(T);break;caseLHd/左邊高，RL型，分兩步旋轉(zhuǎn)rd=lc->lchild;switch(rd->bf){caseRH:T->bf=LH;lc->bf=EH;break;caseLH:T->bf=EH;lc->bf=RH;break;caseEH:T->bf=lc->bf=EH;break;}rd->bf=EH;R_Rotate(T->rchild);111先右旋L_Rotate(T); //2.再左旋}}intInsertAVL(BSTree&T,intkey,bool&taller){//若在平衡二叉排序樹(shù)中不存在與關(guān)鍵字key相等的結(jié)點(diǎn)，則將關(guān)鍵字插入樹(shù)中//布爾變量taller表示樹(shù)是否“長(zhǎng)高”if(T==NULL){T=(BSTree)malloc(sizeof(BSTNode));T->data=key;T->bf=EH;//葉子結(jié)點(diǎn)其平衡因子肯定為0T->lchild=T->rchild=NULL;taller=1;//樹(shù)長(zhǎng)高了}else{if(key==T->data){//如果樹(shù)中已存放此關(guān)鍵字則不予插入taller=0;return0;}if(key<T->data){〃關(guān)鍵字小于根結(jié)點(diǎn)則插入其左子樹(shù)中if(!InsertAVL(T->lchild,key,taller))return0;if(taller){//如果樹(shù)長(zhǎng)高了，判斷是否平衡switch(T->bf){case1任//若左邊高，這次又加上一個(gè)左邊的節(jié)點(diǎn)，則肯定變?yōu)?,即需要調(diào)整LeftBalance(T);//不平衡時(shí)調(diào)用左平衡函數(shù)，使左子樹(shù)平衡taller=0;break;caseEH://若相等，在左邊加一個(gè)節(jié)點(diǎn)，則變?yōu)樽筮吀逿->bf=LH;taller=1;//樹(shù)變高break;case皿://若右邊高，在左邊加一個(gè)節(jié)點(diǎn)，則持平T->bf=EH;taller=0;break;}}else{//插入右子樹(shù)中if(!InsertAVL(T->rchild,key,taller))return0;if(taller){switch(T->bf){caseLH://同理，本來(lái)左邊高，在右邊加一個(gè)節(jié)點(diǎn)則持平T->bf=EH;taller=0;break;caseEH://右邊變高T->bf=RH;taller=1;break;case皿: