第一篇：數(shù)據(jù)結(jié)構(gòu)作業(yè)——二叉樹(shù)

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告二

題目：

用先序遞歸過(guò)程監(jiān)理二叉樹(shù)（存儲(chǔ)結(jié)構(gòu)：二叉鏈表）

輸入數(shù)據(jù)按先序遍歷輸入，當(dāng)某節(jié)點(diǎn)左子樹(shù)或者右子樹(shù)為空時(shí)，輸入‘*’號(hào)，如輸入abc**d**e**時(shí)，得到的二叉樹(shù)為：

并用如下實(shí)力測(cè)試：

算法思路：

顯然，建立一個(gè)二叉鏈表存儲(chǔ)的二叉樹(shù)，如果不考慮效率要求，考慮到程序的簡(jiǎn)介性，遞歸建立和遞歸遍歷是一種很好的辦法。

利用C++的類(lèi)模板的方法實(shí)現(xiàn)建立，遍歷，輸出等二叉樹(shù)操作。首先利用構(gòu)造函數(shù)實(shí)現(xiàn)先序遍歷建立二叉樹(shù)，然后調(diào)用類(lèi)模板中已經(jīng)聲明好的四種遍歷函數(shù)，將遍歷結(jié)果輸出，檢驗(yàn)建立好的二叉樹(shù)是否為要求的二叉樹(shù)。

初始化：利用構(gòu)造函數(shù)建立二叉樹(shù)。采用先序遞歸的調(diào)用方法，構(gòu)造函數(shù)主體如下：

template BiTree::BiTree(){ this->root = Creat();//利用this指針調(diào)用creat函數(shù) }

template BiNode* BiTree::Creat()//定義構(gòu)造函數(shù) { BiNode* root;T aa;cout<<“請(qǐng)按前序序列方式輸入節(jié)點(diǎn)數(shù)據(jù)，每次輸入一個(gè)”<>aa;if(aa==“*”)root = NULL;else{

root = new BiNode;

//生成一個(gè)結(jié)點(diǎn) root->data=aa;

root->lchild = Creat();

//遞歸建立左子樹(shù)

root->rchild = Creat();

//遞歸建立右子樹(shù)

} return root;} 構(gòu)造這樣的函數(shù)，可以在輸入時(shí)，按先序遍歷順序每次輸入一個(gè)節(jié)點(diǎn)的數(shù)據(jù)，可以實(shí)現(xiàn)任意二叉樹(shù)的構(gòu)造。

為了檢驗(yàn)構(gòu)造的二叉樹(shù)是否為預(yù)先設(shè)想的二叉樹(shù)，需要遍歷二叉樹(shù)并進(jìn)行輸出?？紤]到單一的輸出并不能確定唯一的二叉樹(shù)，因此對(duì)遍歷二叉樹(shù)的四種常用發(fā)方法，即先序遍歷，中序遍歷，后續(xù)遍歷，層次遍歷分別實(shí)現(xiàn)，通過(guò)遍歷結(jié)果檢驗(yàn)構(gòu)造的二叉樹(shù)是否為預(yù)先設(shè)計(jì)好的二叉樹(shù)。

先序遍歷：采用遞歸的方法建立。template voidBiTree::xianxu(BiNode *root){ if(root==NULL)return;//如果節(jié)點(diǎn)為空，則返回空 else{ cout<data<<“ ”;//訪問(wèn)根節(jié)點(diǎn)

xianxu(root->lchild);//先序遍歷樹(shù)的左子樹(shù) xianxu(root->rchild);//先序遍歷樹(shù)的右子樹(shù)

} 中序遍歷：遞歸方法建立： template voidBiTree::zhongxu(BiNode *root){

if(root==NULL)return;

//如果節(jié)點(diǎn)為空，則返回空 else{ zhongxu(root->lchild);

//中序遞歸遍歷root的左子樹(shù) cout<data<<“ ”;

//訪問(wèn)根結(jié)點(diǎn)

zhongxu(root->rchild);

//中序遞歸遍歷root的右子樹(shù)

}

} 后序遍歷：遞歸方法建立： template voidBiTree::houxu(BiNode *root){

if(root==NULL)

return;

//如果節(jié)點(diǎn)為空，返回空 else{ houxu(root->lchild);

//后序遞歸遍歷root的左子樹(shù) houxu(root->rchild);

//后序遞歸遍歷root的右子樹(shù) cout<data<<“ ”;

//訪問(wèn)根節(jié)點(diǎn)

} } 層序遍歷：采用非遞歸方法。利用隊(duì)列的方法層序遍歷二叉樹(shù)。建立一個(gè)隊(duì)列，在訪問(wèn)一個(gè)節(jié)點(diǎn)的時(shí)候，把它的左孩子和右孩子入隊(duì)，并且將這個(gè)節(jié)點(diǎn)出隊(duì)。當(dāng)隊(duì)列為空時(shí)，就完成了對(duì)二叉樹(shù)的層序遍歷。

template voidBiTree::cengxu(BiNode *root){ constintMaxSize = 100;int front = 0;int rear = 0;//利用隊(duì)列的方法對(duì)樹(shù)進(jìn)行層序遍歷 BiNode* Q[MaxSize];BiNode* q;if(root==NULL)return;// 如果節(jié)點(diǎn)為空，返回空 else{

Q[rear++] = root;// 若節(jié)點(diǎn)不為空，則該節(jié)點(diǎn)入隊(duì) while(front!= rear)

{

q = Q[front++];//只要隊(duì)列不為空，則節(jié)點(diǎn)依次出隊(duì) cout<data<<“ ”;

if(q->lchild!= NULL)

Q[rear++] = q->lchild;

if(q->rchild!= NULL)

Q[rear++] = q->rchild;// 同時(shí)，該節(jié)點(diǎn)的雙子入隊(duì)

} } } 函數(shù)主體部分：聲明一個(gè)類(lèi)中的對(duì)象，調(diào)用構(gòu)造函數(shù)，建立二叉樹(shù)，并輸出四種遍歷結(jié)果，檢驗(yàn)輸出結(jié)果。

int main(){

BiTreeshu;//聲明類(lèi)中一個(gè)對(duì)象，在構(gòu)造了一顆樹(shù)

BiNode* root = shu.Getroot();//獲取指向根結(jié)點(diǎn)的指針

cout<<“前序遍歷序列為 ”<

程序結(jié)構(gòu)：

主函數(shù)建立一個(gè)類(lèi)模板定義構(gòu)造函數(shù)，析構(gòu)函數(shù)，以及成員函數(shù)聲明類(lèi)中的一個(gè)對(duì)象調(diào)用構(gòu)造函數(shù)，構(gòu)造一顆二叉樹(shù)層序遍歷二叉樹(shù)后序遍歷二叉樹(shù)中序遍歷二叉樹(shù)前序遍歷二叉樹(shù)獲取該二叉樹(shù)的根節(jié)點(diǎn)將結(jié)果輸出，人工檢驗(yàn) 源代碼：

#include using namespace std;

template struct BiNode

{

T data;

BiNode *lchild, *rchild;};

template class BiTree

{ public: BiTree();

//構(gòu)造函數(shù)，初始化一棵二叉樹(shù) ~BiTree(void);

//析構(gòu)函數(shù)，釋放二叉鏈表中各結(jié)點(diǎn)的存儲(chǔ)空間

BiNode* Getroot();

//獲得指向根結(jié)點(diǎn)的指針

void xianxu(BiNode *root);

//前序遍歷二叉樹(shù)

void zhongxu(BiNode *root);

//中序遍歷二叉樹(shù)

void houxu(BiNode *root);

//后序遍歷二叉樹(shù)

void cengxu(BiNode *root);

//層序遍歷二叉樹(shù) private:

BiNode *root;

BiNode *Creat();

void Release(BiNode *root);

};template BiTree::BiTree(){ this->root = Creat();//利用this指針調(diào)用creat函數(shù) }

template BiNode* BiTree::Creat()//定義構(gòu)造函數(shù) { BiNode* root;T aa;cout<<“請(qǐng)按前序序列方式輸入節(jié)點(diǎn)數(shù)據(jù)，每次輸入一個(gè)”<>aa;

if(aa==“*”)root = NULL;

else{

root = new BiNode;

//生成一個(gè)結(jié)點(diǎn)

root->data=aa;

root->lchild = Creat();

//遞歸建立左子樹(shù)

root->rchild = Creat();

//遞歸建立右子樹(shù)

}

return root;}

template BiTree::~BiTree(void){ Release(root);//析構(gòu)函數(shù)，釋放存儲(chǔ)指針?biāo)枰目臻g }

template BiNode* BiTree::Getroot()//獲取根節(jié)點(diǎn)所在指針的位置 { return root;}

template void BiTree::xianxu(BiNode *root){ if(root==NULL)return;//如果節(jié)點(diǎn)為空，則返回空

else{

cout<data<<“ ”;//訪問(wèn)根節(jié)點(diǎn)

xianxu(root->lchild);//先序遍歷樹(shù)的左子樹(shù)

xianxu(root->rchild);//先序遍歷樹(shù)的右子樹(shù)

} }

template void BiTree::zhongxu(BiNode *root){

if(root==NULL)return;

//如果節(jié)點(diǎn)為空，則返回空

else{

zhongxu(root->lchild);

//中序遞歸遍歷root的左子樹(shù)

cout<data<<“ ”;

//訪問(wèn)根結(jié)點(diǎn)

zhongxu(root->rchild);

//中序遞歸遍歷root的右子樹(shù)

} }

template void BiTree::houxu(BiNode *root){

if(root==NULL)

return;

//如果節(jié)點(diǎn)為空，返回空

else{

houxu(root->lchild);

//后序遞歸遍歷root的左子樹(shù)

houxu(root->rchild);

//后序遞歸遍歷root的右子樹(shù)

cout<data<<“ ”;

//訪問(wèn)根節(jié)點(diǎn)

} }

template void BiTree::cengxu(BiNode *root){

const int MaxSize = 100;int front = 0;int rear = 0;//利用隊(duì)列的方法對(duì)樹(shù)進(jìn)行層序遍歷

BiNode* Q[MaxSize];

BiNode* q;if(root==NULL)return;// 如果節(jié)點(diǎn)為空，返回空

else{

Q[rear++] = root;// 若節(jié)點(diǎn)不為空，則該節(jié)點(diǎn)入隊(duì)

while(front!= rear)

{

q = Q[front++];//只要隊(duì)列不為空，則節(jié)點(diǎn)依次出隊(duì)

cout<data<<“ ”;

if(q->lchild!= NULL)

Q[rear++] = q->lchild;

if(q->rchild!= NULL)

Q[rear++] = q->rchild;// 同時(shí)，該節(jié)點(diǎn)的雙子入隊(duì)

} } }

template void BiTree::Release(BiNode* root)//析構(gòu)函數(shù)，釋放存儲(chǔ)空間 {

if(root!= NULL){

Release(root->lchild);

//釋放左子樹(shù)

Release(root->rchild);

//釋放右子樹(shù)

delete root;

}

}

int main(){

BiTree shu;//聲明類(lèi)中一個(gè)對(duì)象，在構(gòu)造了一顆樹(shù)

BiNode* root = shu.Getroot();//獲取指向根結(jié)點(diǎn)的指針

cout<<“前序遍歷序列為 ”<

cout<<“層序遍歷序列為”<

通過(guò)對(duì)結(jié)果的分析，發(fā)現(xiàn)輸出結(jié)果與建立二叉樹(shù)時(shí)的輸入完全符合，說(shuō)明程序的運(yùn)行結(jié)果是正確的。

心得體會(huì)：

1)函數(shù)遞歸的方法可以在相當(dāng)程度上使程序簡(jiǎn)潔，避免代碼的冗長(zhǎng)復(fù)雜。2)構(gòu)造函數(shù)如果帶參數(shù)，在聲明對(duì)象的時(shí)候應(yīng)該將實(shí)參指出來(lái)。但是本題中構(gòu)造函數(shù)位遞歸調(diào)用，初始的根節(jié)點(diǎn)的數(shù)據(jù)值由鍵盤(pán)輸入，因此無(wú)法在聲明對(duì)象時(shí)引入實(shí)參。所以最后選擇了無(wú)參但是引用了this指針的構(gòu)造函數(shù)。可見(jiàn)，對(duì)于構(gòu)造函數(shù)的含參調(diào)用應(yīng)該小心謹(jǐn)慎。

3)編程時(shí)，要不停得檢驗(yàn)自己的輸入與輸出，必要的時(shí)候需要人工進(jìn)行計(jì)算，以保證程序的運(yùn)行按照預(yù)先的設(shè)想。

第二篇：數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)操作驗(yàn)證實(shí)驗(yàn)報(bào)告

班級(jí)：計(jì)算機(jī)11-2 學(xué)號(hào)：40 姓名：朱報(bào)龍

成績(jī)：_________

實(shí)驗(yàn)七 二叉樹(shù)操作驗(yàn)證

一、實(shí)驗(yàn)?zāi)康?/p>

⑴ 掌握二叉樹(shù)的邏輯結(jié)構(gòu)；

⑵ 掌握二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)；

⑶ 掌握基于二叉鏈表存儲(chǔ)的二叉樹(shù)的遍歷操作的實(shí)現(xiàn)。

二、實(shí)驗(yàn)內(nèi)容

⑴ 建立一棵含有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用二叉鏈表存儲(chǔ)；

⑵ 前序（或中序、后序）遍歷該二叉樹(shù)。

三、設(shè)計(jì)與編碼

#include using namespace std;template class BTree;template //***********************二叉樹(shù)結(jié)點(diǎn)類(lèi)定義********************** class BTreeNode { friend class BTree ;T data;BTreeNode *lchild,*rchild;public: BTreeNode():lchild(NULL),rchild(NULL){} BTreeNode(T d,BTreeNode *r=NULL):data(d),lchild(l),rchild(r){}

*l=NULL,BTreeNode T getdata(){return data;} BTreeNode * getleft(){return lchild;} BTreeNode * getright(){return rchild;} };//***********************END******************************** //***********************二叉樹(shù)模板類(lèi)定義******************* template class BTree { public: BTree(T a[],int n);void preorder(void visit(BTreeNode *p));static void preorder(BTreeNode * p,void visit(BTreeNode *p));//遞歸前序遍歷

void inorder(void visit(BTreeNode *p));static void inorder(BTreeNode * p,void visit(BTreeNode *p));//遞歸中序遍歷

void postorder(void visit(BTreeNode *p));static void postorder(BTreeNode * p,void visit(BTreeNode * p));//遞歸后序遍歷

static void fun(BTreeNode *p){cout <

data;}//訪問(wèn)結(jié)點(diǎn) protected: BTreeNode * root;private: T* a;int n;BTreeNode * build0(int i);};

//***********************建樹(shù)******************************* template BTreeNode * BTree ::build0(int i)//遞歸建樹(shù) { BTreeNode *p;int l,r;if((i <=n)&&(a[i-1]!=' ')){ p=new BTreeNode ;p->data=a[i-1];l=2*i;r=2*i+1;p->lchild=build0(l);p->rchild=build0(r);return(p);} else return(NULL);}

template BTree ::BTree(T a[],int n){ this->a=a;this->n=n;root=build0(1);cout <<“遞歸建樹(shù)成功!”<

//***********************遍歷******************************* template void BTree ::preorder(void visit(BTreeNode *p))//遞歸前序遍歷 { preorder(root,visit);cout < void BTree ::preorder(BTreeNode * p,void visit(BTreeNode *p)){ if(p!=NULL){ visit(p);preorder(p->lchild,visit);preorder(p->rchild,visit);} } template void BTree ::inorder(void visit(BTreeNode *p)){ inorder(root,visit);cout < void BTree ::inorder(BTreeNode * p,void visit(BTreeNode *p)){ if(p!=NULL){ inorder(p->lchild,visit);visit(p);inorder(p->rchild,visit);} } template void BTree ::postorder(void visit(BTreeNode *p))//遞歸后序遍歷 { postorder(root,visit);cout < void BTree ::postorder(BTreeNode * p,void visit(BTreeNode *p)){ if(p!=NULL){ postorder(p->lchild,visit);postorder(p->rchild,visit);visit(p);} } void main(){ char *str=“abcd e”;cout<s(str,6);cout <>choice;cout <

{cout <<“遞歸先序遍歷二叉樹(shù)：”;s.preorder(s.fun);cout <

答：經(jīng)常忘記對(duì)頭結(jié)點(diǎn)的定義，以至于程序出錯(cuò)，經(jīng)定義頭結(jié)點(diǎn)，使程序正常運(yùn)行。

b)程序運(yùn)行的結(jié)果如何？

四、實(shí)驗(yàn)小結(jié) 多練習(xí)，多上機(jī)，耐心調(diào)試程序，找出錯(cuò)誤，多總結(jié)。

第三篇：數(shù)據(jù)結(jié)構(gòu)-二叉樹(shù)的遍歷實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告

課程名：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）實(shí)驗(yàn)名：二叉樹(shù)的遍歷 姓名：

班級(jí)：

學(xué)號(hào)：

時(shí)間：2014.11.03

一 實(shí)驗(yàn)?zāi)康呐c要求

1.掌握二叉樹(shù)的存儲(chǔ)方法 2.掌握二叉樹(shù)的三種遍歷方法

3.實(shí)現(xiàn)二叉樹(shù)的三種遍歷方法中的一種 二 實(shí)驗(yàn)內(nèi)容

? 接受用戶輸入一株二叉樹(shù)

? 輸出這株二叉樹(shù)的前根, 中根, 后根遍歷中任意一種的順序 三 實(shí)驗(yàn)結(jié)果與分析

//*********************************************************** //頭文件

#include #include //*********************************************************** //宏定義

#define OK 1 #define ERROR 0 #define OVERFLOW 0

//***********************************************************

typedef struct BiTNode { //二叉樹(shù)二叉鏈表存儲(chǔ)結(jié)構(gòu) char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//*********************************************************** int CreateBiTree(BiTree &T){ //按先序次序輸入二叉中樹(shù)結(jié)點(diǎn)的值，空格表示空樹(shù) //構(gòu)造二叉鏈表表示的二叉樹(shù)T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;CreateBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，先序遍歷二叉樹(shù)的遞歸算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，中序遍歷二叉樹(shù)的遞歸算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(T->rChild);} }

//*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，后序遍歷二叉樹(shù)的遞歸算法 if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild);printf(“%c”,T->data);} }

//*********************************************************** void main(){ //主函數(shù)分別實(shí)現(xiàn)建立并輸出先、中、后序遍歷二叉樹(shù)

printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍歷二叉樹(shù):”);PreOrderTraverse(Tree);printf(“n中序遍歷二叉樹(shù):”);InOrderTraverse(Tree);printf(“n后序遍歷二叉樹(shù):”);PostOrderTraverse(Tree);}

圖1:二叉樹(shù)的遍歷運(yùn)行結(jié)果

第四篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-_平衡二叉樹(shù)操作 - 副本

課 程 設(shè) 計(jì) 報(bào) 告

一． 需求分析

1、建立平衡二叉樹(shù)并進(jìn)行創(chuàng)建、增加、刪除、調(diào)平等操作。

2、設(shè)計(jì)一個(gè)實(shí)現(xiàn)平衡二叉樹(shù)的程序，可進(jìn)行創(chuàng)建、增加、刪除、調(diào)平等操作，實(shí)現(xiàn)動(dòng)態(tài)的輸入數(shù)據(jù)，實(shí)時(shí)的輸出該樹(shù)結(jié)構(gòu)。

3、測(cè)試數(shù)據(jù)：自選數(shù)據(jù)

二． 概要設(shè)計(jì)

平衡二叉樹(shù)是在構(gòu)造二叉排序樹(shù)的過(guò)程中，每當(dāng)插入一個(gè)新結(jié)點(diǎn)時(shí)，首先檢查是否因插入新結(jié)點(diǎn)而破壞了二叉排序樹(shù)的平衡性，若是，則找出其中的最小不平衡子樹(shù)，在保持二叉排序樹(shù)特性的前提下，調(diào)整最小不平衡子樹(shù)中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹(shù)。具體步驟如下：

⑴ 每當(dāng)插入一個(gè)新結(jié)點(diǎn)，從該結(jié)點(diǎn)開(kāi)始向上計(jì)算各結(jié)點(diǎn)的平衡因子，即計(jì)算該結(jié)點(diǎn)的祖先結(jié)點(diǎn)的平衡因子，若該結(jié)點(diǎn)的祖先結(jié)點(diǎn)的平衡因子的絕對(duì)值均不超過(guò)1，則平衡二叉樹(shù)沒(méi)有失去平衡，繼續(xù)插入結(jié)點(diǎn)；

⑵ 若插入結(jié)點(diǎn)的某祖先結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則找出其中最小不平衡子樹(shù)的根結(jié)點(diǎn)；

⑶ 判斷新插入的結(jié)點(diǎn)與最小不平衡子樹(shù)的根結(jié)點(diǎn)的關(guān)系，確定是哪種類(lèi)型的調(diào)整；

⑷ 如果是LL型或RR型，只需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過(guò)程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；如果是LR型或RL型，則需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹(shù)的根結(jié)點(diǎn)先不動(dòng)，調(diào)整插入結(jié)點(diǎn)所在子樹(shù)，第二次再調(diào)整最小不平衡子樹(shù)，在旋轉(zhuǎn)過(guò)程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；

⑸ 計(jì)算調(diào)整后的平衡二叉樹(shù)中各結(jié)點(diǎn)的平衡因子，檢驗(yàn)是否因?yàn)樾D(zhuǎn)而破壞其他結(jié)點(diǎn)的平衡因子，以及調(diào)整后的平衡二叉樹(shù)中是否存在平衡因子大于1的結(jié)點(diǎn)。

三． 詳細(xì)設(shè)計(jì)

樹(shù)的內(nèi)部變量

— 1 — typedef struct BTNode {

int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子

}BTNode,*BTree;調(diào)平二叉樹(shù)(左右調(diào)平方式大體雷同，之具體寫(xiě)出其中一種調(diào)平方式)if(插入元素與當(dāng)前根元素相等){ printf(“已存在相同關(guān)鍵字的結(jié)點(diǎn)n”);} if(插入元素小于當(dāng)前根元素)){ if(插入新結(jié)點(diǎn)不成功)

return 0;if(插入成功)

switch(查看根的平衡因子)

{

case +1:

進(jìn)行左平衡處理;

{

檢查*T的左子樹(shù)的平衡度，并作相應(yīng)平衡處理

{

case +1:

令根及其左孩子的平衡因子為0;

做右平衡處理;

{

BTree lc;

lc指向的結(jié)點(diǎn)左子樹(shù)根結(jié)點(diǎn);

rc的右子樹(shù)掛接為結(jié)點(diǎn)的左子樹(shù);

lc的右孩子為原結(jié)點(diǎn);

原結(jié)點(diǎn)指向新的結(jié)點(diǎn)lc;

}

break;

case-1:

rd指向*T的左孩子的右子樹(shù)根

switch(查看右孩子平衡因子)

{

case +1:

根的平衡因子為-1;

根左孩子的平衡因子為0;

break;

case 0:

令根和根左孩子的平衡因子為0;— 2 —

}

}

}

}

break;根平衡因子為0;根左孩子平衡因子為1;break;

case-1:

根右孩子的平衡因子為0;對(duì)*T的左子樹(shù)作左旋平衡處理;對(duì)*T作右旋平衡處理;break;令根的平衡因子為+1;break;令根的平衡因子為-1;break;case 0:

case-1:

四．調(diào)試分析

在進(jìn)行對(duì)插入新結(jié)點(diǎn)并調(diào)平時(shí)由于利用的是普通的插入方法進(jìn)行LL、LR、RL、RR型的轉(zhuǎn)換，使得在調(diào)試時(shí)經(jīng)常沒(méi)有更改內(nèi)部變量的值，導(dǎo)致編譯出錯(cuò)。

對(duì)于在空樹(shù)情況下刪除結(jié)點(diǎn)的考慮，是在后期的調(diào)試檢驗(yàn)過(guò)程中發(fā)現(xiàn)的。在沒(méi)有更改代碼前，如果按此操作，程序就會(huì)崩潰。原因就是在刪除函數(shù)中雖然考慮到了空樹(shù)的情況，但是在輸出樹(shù)的函數(shù)中沒(méi)有加入空樹(shù)的考慮而只是在創(chuàng)建樹(shù)函數(shù)中加入了if…else…的判斷。經(jīng)過(guò)反復(fù)的檢查，發(fā)現(xiàn)可以直接在輸出函數(shù)中加入判斷而不必再其他位置判斷，并且調(diào)試成功。

五．使用說(shuō)明和測(cè)試結(jié)果

測(cè)試數(shù)據(jù)：

創(chuàng)建二叉樹(shù)

增加二叉樹(shù)

直接創(chuàng)建平衡二叉樹(shù)

— 4 —平衡二叉樹(shù)加入新節(jié)點(diǎn)并調(diào)平

刪除結(jié)點(diǎn)

六．心得體會(huì)

了解了建立樹(shù)的方法；

學(xué)會(huì)了利用二分法建立樹(shù)結(jié)構(gòu)。、； 學(xué)習(xí)到了二叉樹(shù)的調(diào)平方法；

學(xué)會(huì)了向一個(gè)已知樹(shù)插入或刪除結(jié)點(diǎn)的方法。

— 6 —

第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-平衡二叉樹(shù)操作

課 程 設(shè) 計(jì) 報(bào) 告

課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目平衡二叉樹(shù)操作 指導(dǎo)教師 設(shè)計(jì)起止日 2010-5-16 學(xué) 院 計(jì)算機(jī)學(xué)院 專 業(yè)

軟件工程 學(xué)生姓名

班級(jí)/學(xué)號(hào)------------成 績(jī) _________________

一． 需求分析

1、建立平衡二叉樹(shù)并進(jìn)行創(chuàng)建、增加、刪除、調(diào)平等操作。

2、設(shè)計(jì)一個(gè)實(shí)現(xiàn)平衡二叉樹(shù)的程序，可進(jìn)行創(chuàng)建、增加、刪除、調(diào)平等操作，實(shí)現(xiàn)動(dòng)態(tài)的輸入數(shù)據(jù)，實(shí)時(shí)的輸出該樹(shù)結(jié)構(gòu)。

3、測(cè)試數(shù)據(jù)：自選數(shù)據(jù)

二． 概要設(shè)計(jì)

平衡二叉樹(shù)是在構(gòu)造二叉排序樹(shù)的過(guò)程中，每當(dāng)插入一個(gè)新結(jié)點(diǎn)時(shí)，首先檢查是否因插入新結(jié)點(diǎn)而破壞了二叉排序樹(shù)的平衡性，若是，則找出其中的最小不平衡子樹(shù)，在保持二叉排序樹(shù)特性的前提下，調(diào)整最小不平衡子樹(shù)中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹(shù)。具體步驟如下：

⑴ 每當(dāng)插入一個(gè)新結(jié)點(diǎn)，從該結(jié)點(diǎn)開(kāi)始向上計(jì)算各結(jié)點(diǎn)的平衡因子，即計(jì)算該結(jié)點(diǎn)的祖先結(jié)點(diǎn)的平衡因子，若該結(jié)點(diǎn)的祖先結(jié)點(diǎn)的平衡因子的絕對(duì)值均不超過(guò)1，則平衡二叉樹(shù)沒(méi)有失去平衡，繼續(xù)插入結(jié)點(diǎn)；

⑵ 若插入結(jié)點(diǎn)的某祖先結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則找出其中最小不平衡子樹(shù)的根結(jié)點(diǎn)；

⑶ 判斷新插入的結(jié)點(diǎn)與最小不平衡子樹(shù)的根結(jié)點(diǎn)的關(guān)系，確定是哪種類(lèi)型的調(diào)整；

⑷ 如果是LL型或RR型，只需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過(guò)程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；如果是LR型或RL型，則需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹(shù)的根結(jié)點(diǎn)先不動(dòng)，調(diào)整插入結(jié)點(diǎn)所在子樹(shù)，第二次再調(diào)整最小不平衡子樹(shù)，在旋轉(zhuǎn)過(guò)程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；

⑸ 計(jì)算調(diào)整后的平衡二叉樹(shù)中各結(jié)點(diǎn)的平衡因子，檢驗(yàn)是否因?yàn)樾D(zhuǎn)而破壞其他結(jié)點(diǎn)的平衡因子，以及調(diào)整后的平衡二叉樹(shù)中是否存在平衡因子大于1的結(jié)點(diǎn)。

三． 詳細(xì)設(shè)計(jì)

樹(shù)的內(nèi)部變量

typedef struct BTNode { — 2 —

int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子

}BTNode,*BTree;調(diào)平二叉樹(shù)(左右調(diào)平方式大體雷同，之具體寫(xiě)出其中一種調(diào)平方式)if(插入元素與當(dāng)前根元素相等){ printf(“已存在相同關(guān)鍵字的結(jié)點(diǎn)n”);} if(插入元素小于當(dāng)前根元素)){ if(插入新結(jié)點(diǎn)不成功)

return 0;if(插入成功)

switch(查看根的平衡因子)

{

case +1:

進(jìn)行左平衡處理;

{

檢查*T的左子樹(shù)的平衡度，并作相應(yīng)平衡處理

{

case +1:

令根及其左孩子的平衡因子為0;

做右平衡處理;

{

BTree lc;

lc指向的結(jié)點(diǎn)左子樹(shù)根結(jié)點(diǎn);

rc的右子樹(shù)掛接為結(jié)點(diǎn)的左子樹(shù);

lc的右孩子為原結(jié)點(diǎn);

原結(jié)點(diǎn)指向新的結(jié)點(diǎn)lc;

}

break;

case-1:

rd指向*T的左孩子的右子樹(shù)根

switch(查看右孩子平衡因子)

{

case +1:

根的平衡因子為-1;

根左孩子的平衡因子為0;

break;

case 0:

令根和根左孩子的平衡因子為0;

break;

case-1:

}

}

}

}

根平衡因子為0;根左孩子平衡因子為1;break;

根右孩子的平衡因子為0;對(duì)*T的左子樹(shù)作左旋平衡處理;對(duì)*T作右旋平衡處理;break;令根的平衡因子為+1;break;令根的平衡因子為-1;break;case 0:

case-1:

四．調(diào)試分析

在進(jìn)行對(duì)插入新結(jié)點(diǎn)并調(diào)平時(shí)由于利用的是普通的插入方法進(jìn)行LL、LR、RL、RR型的轉(zhuǎn)換，使得在調(diào)試時(shí)經(jīng)常沒(méi)有更改內(nèi)部變量的值，導(dǎo)致編譯出錯(cuò)。

對(duì)于在空樹(shù)情況下刪除結(jié)點(diǎn)的考慮，是在后期的調(diào)試檢驗(yàn)過(guò)程中發(fā)現(xiàn)的。在沒(méi)有更改代碼前，如果按此操作，程序就會(huì)崩潰。原因就是在刪除函數(shù)中雖然考慮到了空樹(shù)的情況，但是在輸出樹(shù)的函數(shù)中沒(méi)有加入空樹(shù)的考慮而只是在創(chuàng)建樹(shù)函數(shù)中加入了if…else…的判斷。經(jīng)過(guò)反復(fù)的檢查，發(fā)現(xiàn)可以直接在輸出函數(shù)中加入判斷而不必再其他位置判斷，并且調(diào)試成功。

五．使用說(shuō)明和測(cè)試結(jié)果

測(cè)試數(shù)據(jù)：

創(chuàng)建二叉樹(shù)

— 4 —

增加二叉樹(shù)

直接創(chuàng)建平衡二叉樹(shù)

平衡二叉樹(shù)加入新節(jié)點(diǎn)并調(diào)平

刪除結(jié)點(diǎn)

— 6 —

六．心得體會(huì)

了解了建立樹(shù)的方法；

學(xué)會(huì)了利用二分法建立樹(shù)結(jié)構(gòu)。、； 學(xué)習(xí)到了二叉樹(shù)的調(diào)平方法；

學(xué)會(huì)了向一個(gè)已知樹(shù)插入或刪除結(jié)點(diǎn)的方法。七．附錄 源代碼

#include “stdafx.h” #include #include #define EQ(a,b)((a)==(b))#define LT(a,b)((a)<(b))#define LQ(a,b)((a)>(b))#define LH +1 //左高 #define EH 0 //等高 #define RH-1 //右高 typedef struct BTNode { int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子

}BTNode,*BTree;

/*需要的函數(shù)聲明*/ void Right_Balance(BTree &p);void Left_Balance(BTree &p);void Left_Root_Balance(BTree &T);void Right_Root_Balance(BTree &T);bool InsertAVL(BTree &T,int i,bool &taller);void PrintBT(BTree T,int m);void CreatBT(BTree &T);void Left_Root_Balance_det(BTree &p,int &shorter);void Right_Root_Balance_det(BTree &p,int &shorter);void Delete(BTree q,BTree &r,int &shorter);int DeleteAVL(BTree &p,int x,int &shorter);void Adj_balance(BTree &T);bool SetAVL(BTree &T,int i,bool &taller);bool Insert_Balance_AVL(BTree &T,int i,bool &taller);/*主函數(shù)*/ void main(){

int input,search,m;bool taller=false;int shorter=0;BTree T;T=(BTree)malloc(sizeof(BTNode));T=NULL;while(1){

printf(“n請(qǐng)選擇需要的二叉樹(shù)操作n”);printf(“1.創(chuàng)建二叉樹(shù)2.增加新結(jié)點(diǎn)3.直接創(chuàng)建平衡二叉樹(shù)4.在平衡二叉樹(shù)上增加新結(jié)點(diǎn)并調(diào)平衡5.scanf(”%d“,&input);getchar();switch(input){ case 1:

CreatBT(T);break;printf(”請(qǐng)輸入你要增加的關(guān)鍵字“);scanf(”%d“,&search);getchar();InsertAVL(T,search,taller);m = 0;PrintBT(T,m);break;Adj_balance(T);刪除0.退出n”);case 2: case 3: — 8 —

break;

case 4:

printf(“請(qǐng)輸入你要增加的關(guān)鍵字”);

scanf(“%d”,&search);

getchar();

SetAVL(T,search,taller);

m = 0;

PrintBT(T,m);

break;

case 5:

printf(“請(qǐng)輸入你要?jiǎng)h除的關(guān)鍵字”);

scanf(“%d”,&search);

getchar();

DeleteAVL(T,search,shorter);

m=0;

PrintBT(T,m);

break;

case 0:

break;

default:

printf(“輸入錯(cuò)誤，請(qǐng)重新選擇?！?;

break;

}

if(input == 0)

break;

printf(“按任意鍵繼續(xù).”);

getchar();} } /*對(duì)以*p為根的二叉排序樹(shù)作右旋處理*/ void Right_Balance(BTree &p){ BTree lc;lc = p->lchild;//lc指向的*p左子樹(shù)根結(jié)點(diǎn)

p->lchild = lc->rchild;//rc的右子樹(shù)掛接為*p的左子樹(shù) lc->rchild = p;p = lc;//p指向新的結(jié)點(diǎn)

} /*對(duì)以*p為根的二叉排序樹(shù)作左旋處理*/ void Left_Balance(BTree &p){ BTree rc;rc = p->rchild;//指向的*p右子樹(shù)根結(jié)點(diǎn)

p->rchild = rc->lchild;//rc左子樹(shù)掛接到*p的右子樹(shù)

rc->lchild = p;p = rc;//p指向新的結(jié)點(diǎn)

— 9 — } /*對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理*/ void Left_Root_Balance(BTree &T){

} /*對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理*/ void Right_Root_Balance(BTree &T){

BTree rc,ld;rc = T->rchild;//指向*T的左子樹(shù)根結(jié)點(diǎn)

switch(rc->bf)//檢查*T的右子樹(shù)的平衡度，并作相應(yīng)平衡處理 { case RH: //新結(jié)點(diǎn)插入在*T的右孩子的右子樹(shù)上，要作單左旋處理

T->bf = rc->bf =EH;Left_Balance(T);break;ld = rc->lchild;//ld指向*T的右孩子的左子樹(shù)根 switch(ld->bf)//修改*T及其右孩子的平衡因子 BTree lc,rd;lc = T->lchild;//指向*T的左子樹(shù)根結(jié)點(diǎn)

switch(lc->bf)//檢查*T的左子樹(shù)的平衡度，并作相應(yīng)平衡處理 { case LH: //新結(jié)點(diǎn)插入在*T的左孩子的左子樹(shù)上，要作單右旋處理

} T->bf = lc->bf = EH;Right_Balance(T);break;rd = lc->rchild;//rd指向*T的左孩子的右子樹(shù)根 switch(rd->bf)//修改*T及其左孩子的平衡因子 { case LH:

} rd->bf = EH;Left_Balance(T->lchild);//對(duì)*T的左子樹(shù)作左旋平衡處理 Right_Balance(T);//對(duì)*T作右旋平衡處理 T->bf = RH;lc->bf = EH;break;T->bf = lc->bf = EH;break;T->bf = EH;lc->bf = LH;break;case RH: //新結(jié)點(diǎn)插入在*T的左孩子的右子樹(shù)上，要作雙旋處理

case EH: case RH: case LH: //新結(jié)點(diǎn)插入在*T的右孩子的左子樹(shù)上，要作雙旋處理

— 10 —

}

} { case LH:

} ld->bf = EH;Right_Balance(T->rchild);//對(duì)*T的右子樹(shù)作左旋平衡處理 Left_Balance(T);//對(duì)*T作左旋平衡處理 T->bf = EH;rc->bf = RH;break;T->bf = rc->bf =EH;break;T->bf = LH;rc->bf = EH;break;case EH: case RH: /*插入結(jié)點(diǎn)i,若T中存在和i相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為i的新結(jié)點(diǎn)，并返回１，否則返回０*/ bool InsertAVL(BTree &T,int i,bool &taller){

if(!T)//插入新結(jié)點(diǎn)，樹(shù)“長(zhǎng)高”，置taller為true {

} else {

if(EQ(i,T->data))//樹(shù)中已存在和有相同關(guān)鍵字的結(jié)點(diǎn) {

} if(LT(i,T->data))//應(yīng)繼續(xù)在*T的左子樹(shù)中進(jìn)行搜索 taller = false;printf(“已存在相同關(guān)鍵字的結(jié)點(diǎn)n”);return 0;T =(BTree)malloc(sizeof(BTNode));T->data = i;T->lchild = T->rchild =NULL;T->bf = EH;taller = true;{ if(!InsertAVL(T->lchild,i,taller))return 0;} else //應(yīng)繼續(xù)在*T的右子樹(shù)中進(jìn)行搜索 { if(!InsertAVL(T->rchild,i,taller))return 0;

— 11 — } } return 1;} /*按樹(shù)狀打印輸出二叉樹(shù)的元素,m表示結(jié)點(diǎn)所在層次*/ void PrintBT(BTree T,int m){

} /*創(chuàng)建二叉樹(shù)，以輸入-32767為建立的結(jié)束*/ void CreatBT(BTree &T){

} int m;int i;bool taller=false;T = NULL;printf(“n請(qǐng)輸入關(guān)鍵字(以-32767結(jié)束建立二叉樹(shù)):”);scanf(“%i”,&i);getchar();while(i!=-32767){

} m=0;printf(“您創(chuàng)建的二叉樹(shù)為：n”);PrintBT(T,m);InsertAVL(T,i,taller);printf(“n請(qǐng)輸入關(guān)鍵字(以-32767結(jié)束建立二叉樹(shù)):”);scanf(“%i”,&i);getchar();taller=false;if(T){

} else {

} printf(“這是一棵空樹(shù)！n”);getchar();int i;if(T->rchild)PrintBT(T->rchild,m+1);printf(“ ”);//打印i 個(gè)空格以表示出層次 for(i = 1;i<=m;i++)printf(“%dn”,T->data);//打印T 元素,換行 if(T->lchild)PrintBT(T->lchild,m+1);— 12 — /*刪除結(jié)點(diǎn)時(shí)左平衡旋轉(zhuǎn)處理*/ void Left_Root_Balance_det(BTree &p,int &shorter){

BTree p1,p2;if(p->bf==1)//p結(jié)點(diǎn)的左子樹(shù)高，刪除結(jié)點(diǎn)后p的bf減,樹(shù)變矮 {

} else if(p->bf==0)//p結(jié)點(diǎn)左、右子樹(shù)等高，刪除結(jié)點(diǎn)后p的bf減,樹(shù)高不變 {

} else //p結(jié)點(diǎn)的右子樹(shù)高 {

p1=p->rchild;//p1指向p的右子樹(shù)

if(p1->bf==0)//p1結(jié)點(diǎn)左、右子樹(shù)等高,刪除結(jié)點(diǎn)后p的bf為-2,進(jìn)行左旋處理，樹(shù)高不變 {

} else if(p1->bf==-1)//p1的右子樹(shù)高，左旋處理后，樹(shù)變矮 {

} else //p1的左子樹(shù)高,進(jìn)行雙旋處理(先右旋后左旋)，樹(shù)變矮 {

p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf==0){

} else if(p2->bf==-1){ p->bf=1;p1->bf=0;p->bf=0;p1->bf=0;Left_Balance(p);p1->bf=p->bf=0;shorter=1;Left_Balance(p);p1->bf=1;p->bf=-1;shorter=0;p->bf=-1;shorter=0;p->bf=0;shorter=1;

}

}

} } else {

} p2->bf=0;p=p2;shorter=1;p->bf=0;p1->bf=-1;/*刪除結(jié)點(diǎn)時(shí)右平衡旋轉(zhuǎn)處理*/ void Right_Root_Balance_det(BTree &p,int &shorter){

BTree p1,p2;if(p->bf==-1){

} else if(p->bf==0){

} else {

p1=p->lchild;if(p1->bf==0){

} else if(p1->bf==1){

} else { p2=p1->rchild;Right_Balance(p);p1->bf=p->bf=0;shorter=1;Right_Balance(p);p1->bf=-1;p->bf=1;shorter=0;p->bf=1;shorter=0;p->bf=0;shorter=1;— 14 —

p1->rchild=p2->lchild;

p2->lchild=p1;

p->lchild=p2->rchild;

p2->rchild=p;

if(p2->bf==0)

{

p->bf=0;

p1->bf=0;

}

else if(p2->bf==1)

{

p->bf=-1;

p1->bf=0;

}

else

{

p->bf=0;

p1->bf=1;

}

p2->bf=0;

p=p2;

shorter=1;

} } } /*刪除結(jié)點(diǎn)*/ void Delete(BTree q,BTree &r,int &shorter){ if(r->rchild==NULL){

q->data=r->data;

q=r;

r=r->lchild;

free(q);

shorter=1;} else {

Delete(q,r->rchild,shorter);

if(shorter==1)

Right_Root_Balance_det(r,shorter);} } /*二叉樹(shù)的刪除操作*/ int DeleteAVL(BTree &p,int x,int &shorter){

} int k;BTree q;if(p==NULL){

} else if(x

data)//在p的左子樹(shù)中進(jìn)行刪除 {

} else if(x>p->data)//在p的右子樹(shù)中進(jìn)行刪除 {

} else {

} q=p;if(p->rchild==NULL)//右子樹(shù)空則只需重接它的左子樹(shù) {

} else if(p->lchild==NULL)//左子樹(shù)空則只需重接它的右子樹(shù) {

} else//左右子樹(shù)均不空 {

} return 1;Delete(q,q->lchild,shorter);if(shorter==1)Left_Root_Balance_det(p,shorter);p=q;p=p->rchild;free(q);shorter=1;p=p->lchild;free(q);shorter=1;k=DeleteAVL(p->rchild,x,shorter);if(shorter==1)Right_Root_Balance_det(p,shorter);return k;k=DeleteAVL(p->lchild,x,shorter);if(shorter==1)Left_Root_Balance_det(p,shorter);return k;printf(“不存在要?jiǎng)h除的關(guān)鍵字！n”);return 0;— 16 — /*二叉樹(shù)調(diào)平操作*/ void Adj_balance(BTree &T){ int m;int i;bool taller=false;T = NULL;printf(“n請(qǐng)輸入關(guān)鍵字(以-32767結(jié)束建立平衡二叉樹(shù)):”);scanf(“%d”,&i);getchar();while(i!=-32767){

SetAVL(T,i,taller);

printf(“n請(qǐng)輸入關(guān)鍵字(以-32767結(jié)束建立平衡二叉樹(shù)):”);

scanf(“%d”,&i);

getchar();

taller=false;} m=0;printf(“平衡二叉樹(shù)創(chuàng)建結(jié)束.n”);if(T)

PrintBT(T,m);else

printf(“這是一棵空樹(shù).n”);} /*調(diào)平二叉樹(shù)具體方法*/ bool SetAVL(BTree &T,int i,bool &taller){ if(!T)//插入新結(jié)點(diǎn)，樹(shù)“長(zhǎng)高”，置taller為true {

T =(BTree)malloc(sizeof(BTNode));

T->data = i;

T->lchild = T->rchild =NULL;

T->bf = EH;

taller = true;} else {

if(EQ(i,T->data))//樹(shù)中已存在和有相同關(guān)鍵字的結(jié)點(diǎn)

{

taller = false;

printf(“已存在相同關(guān)鍵字的結(jié)點(diǎn)n”);

return 0;

}

if(LT(i,T->data))//應(yīng)繼續(xù)在*T的左子樹(shù)中進(jìn)行搜索 {

}

}

} if(!SetAVL(T->lchild,i,taller))

{

} case LH: //原本左子樹(shù)比右子樹(shù)高，需要作左平衡處理

Left_Root_Balance(T);taller = false;break;T->bf = LH;taller = true;break;T->bf = EH;taller = false;break;return 0;switch(T->bf)//檢查*T的平衡度 if(taller)//已插入到*T的左子樹(shù)中且左子樹(shù)“長(zhǎng)高”

case EH: //原本左子樹(shù)、右子等高，現(xiàn)因左子樹(shù)增高而使樹(shù)增高

case RH: //原本右子樹(shù)比左子樹(shù)高，現(xiàn)左、右子樹(shù)等高

else //應(yīng)繼續(xù)在*T的右子樹(shù)中進(jìn)行搜索 {

} return 1;if(!SetAVL(T->rchild,i,taller))

{

} case LH: //原本左子樹(shù)比右子樹(shù)高，現(xiàn)左、右子樹(shù)等高

T->bf = EH;taller = false;break;T->bf = RH;taller = true;break;Right_Root_Balance(T);taller = false;break;return 0;switch(T->bf)//檢查*T的平衡度 if(taller)//已插入到*T的右子樹(shù)中且右子樹(shù)“長(zhǎng)高”

case EH: //原本左子樹(shù)、右子等高，現(xiàn)因右子樹(shù)增高而使樹(shù)增高

case RH: //原本右子樹(shù)比左子樹(shù)高，需要作右平衡處理

— 18 —