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

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

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