數(shù)據(jù)結(jié)構(gòu)試驗報告

1、數(shù)據(jù)結(jié)構(gòu)實驗報告班級姓名學號實驗三一.實驗內(nèi)容：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預先編碼， 在接收端將傳來的數(shù)據(jù)進行譯碼(復原)。對于雙工信道(即可以雙向傳輸信息 的信道)，每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈 夫曼的編/譯碼系統(tǒng)。一個完整的系統(tǒng)應(yīng)具有以下功能：(1) I :初始化(Initialization )。從終端讀入字符集大小n,以及n個字符 和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。(2) E：編碼(Encoding)。利用以建好的哈夫曼樹(如不在

2、內(nèi)存，則從文件 hfmTree中讀入)，對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入 文件CodeFile中。(3) D:譯碼(Decoding)。利用已經(jīng)建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件 TextFile中。(4) P：打印代碼文件(Print )。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼，同時將此字符形式的編碼寫入文件CodePrint中。T:打印哈夫曼樹(Tree printing )。將已經(jīng)在內(nèi)存中的哈夫曼樹以直觀的 方式(樹或凹入表形式)顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件 TreePrint 中。二.實驗目

3、的(1)掌握二叉樹的存儲結(jié)構(gòu)及其相關(guān)操作。(2)掌握構(gòu)造哈夫曼樹的基本思想，及其編碼/譯碼過程。三.程序清單#include <stdio.h>#include <stdlib.h>#include <string.h>/定義赫夫曼樹結(jié)點的結(jié)構(gòu)體typedef structchar ch;/增加一個域，存放該節(jié)點的字符int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode; /指向赫夫曼編碼的指針void tips(); /打印操作選擇界面void H

4、uffmanCoding(HuffmanTree &,char *,int *,int);/建立赫夫曼樹的算法void select(HuffmanTree HT,int j,int *x,int *y);/從已建好的赫夫曼樹中選擇parent為0, weight最小的兩個結(jié)點void Init();void Coding。； / 編碼void Decoding。； / 譯碼void Print_code(); /打印譯碼好的代碼void Print_tree(); /打印哈夫曼樹譯碼時根據(jù) 01將內(nèi)存中的122887'n");int Read_tree(Huffma

5、nTree &); 從文件中讀入赫夫曼樹void find(HuffmanTree &HT,char *code,char *text,int i,int m); /字符串尋找相應(yīng)葉子節(jié)點的遞歸算法void Convert_tree(unsigned char T100100,int s,int *i,int j); /赫夫曼樹轉(zhuǎn)換成凹凸表形式的赫夫曼樹HuffmanTree HT; /全局變量int n=0; /全局變量，存放赫夫曼樹葉子結(jié)點的數(shù)目int main()printf(" 班級：中法121姓名：郝雨微學號:char select;while(1)tips

6、();scanf("%c",&select);switch(select) /選擇操作，根據(jù)不同的序號選擇不同的操作case T:Init();break;case 'E':Coding();break;case 'D':Decoding();break;case 'P':Print_code();break;case T:Print_tree();break;case 'Q':exit；default :printf("Input error!n");getchar();retur

7、n 0;void tips() /操作選擇界面printf("n");printf("-請選擇操作-'n")；printf("n");printf("n");printf("1初始化赫夫曼樹 n");printf("E編碼 n");printf("D譯碼 n");printf("P打印代碼文件 n");printf("T打印赫夫曼樹 n");printf("Q退出 n");printf(&

8、quot;n");/初始化函數(shù)，輸入 n個字符及其對應(yīng)的權(quán)值，根據(jù)權(quán)值建立哈夫曼樹，并將其存于文件hfmtree 中void Init()FILE *fp;int i,n,w52; /數(shù)組存放字符的權(quán)值char character52; / 存放 n 個字符printf("n輸入字符個數(shù) n:");scanf("%d",&n);/輸入字符集大小printf("輸入d個字符及其又應(yīng)的權(quán)值：n",n);for (i=0;i<n;i+)char b=getchar();scanf("%c",&am

9、p;characteri);scanf("%d”,&wi);/輸入n個字符和對應(yīng)的權(quán)值HuffmanCoding(HT,character,w,n); /建立赫夫曼樹if(fp=fopen("hfmtree.txt","w")=NULL)printf("Open file hfmtree.txt error!n");for (i=1;i<=2*n-1;i+)if(fwrite(&HTi,sizeof(HTNode),1,fp)!=1)/ 將建立 的赫夫曼樹存 入文件 hfmtree.txt 中print

10、f("File write error!n");printf("n赫夫曼樹建立成功，并已存于文件 hfmtree.txt 中n");fclose(fp);/建立赫夫曼樹的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)int m,i,x,y;HuffmanTree p;if(n<=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;i<=n;+i,+p,

11、+character,+w)p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0; for(;i<=m;+i,+p) p->ch=0;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0; for(i=n+1;i<=m;+i)select(HT,i-1,&x,&y);HTx.parent=i;HTy.parent=i;HTi.lchild=x;HTi.rchild=y;HTi.weight

12、=HTx.weight+HTy.weight;從HT1到HTj中選擇parent為0, weight最小的兩個結(jié)點，用 x和y返回其序號 void select(HuffmanTree HT,int j,int *x,int *y) int i;/查找weight最小的結(jié)點for (i=1;i<=j;i+)if (HTi.parent=0)*x=i;break; for (;i<=j;i+)if (HTi.parent=0)&&(HTi.weight<HT*x.weight)x=i;HT*x.parent=1;/查找weight次小的結(jié)點 for (i=1;i

13、<=j;i+)if (HTi.parent=0)*y=i;break;for (;i<=j;i+)if (HTi.parent=0)&&(i!=*x)&&(HTi.weight<HT*y.weight)*y=i;/對文件tobetrans中的正文進行編碼，然后將結(jié)果存入文件codefile 中void Coding。FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;if(n=0)n=Read_tree(HT);/從文件hfmtree.txt中讀入赫夫曼樹，返回葉子結(jié)點數(shù)/求赫夫曼樹中各葉子

14、節(jié)點的字符對應(yīng)的的編碼，并存于HC指向的空間中HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char *)malloc(n*sizeof(char);cdn-1='0'for(i=1;i<=n;+i)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start='0'else cd-start='1'HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi,

15、&cdstart);free(cd);if(fp=fopen("tobetrans.txt","rb")=NULL)printf("Open file tobetrans.txt error!n");if(fw=fopen("codefile.txt","wb+")=NULL)printf("Open file codefile.txt error!n");char temp;fscanf(fp,"%c",&temp); /從文件讀入第一個

16、字符while(!feof(fp)在赫夫曼樹中查找字符所在的位置將字符對應(yīng)的編碼存入文件從文件讀入下一個字符成功編碼，并已存入codefile.txt 中！ nn");for(i=1;i<=n;i+) if(HTi.ch=temp) break; / for(int r=0;HCir!='0'r+) / fputc(HCir,fw);fscanf(fp,"%c",&temp); / fclose(fw);fclose(fp);printf("n 已將文件 hfmtree.txt /將文件codefile 中的代碼進行譯碼，結(jié)

17、果存入文件 textfile 中void Decoding。 FILE *fp,*fw;int m,i;char *code,*text,*p;if(n=0)n=Read_tree(HT);/從文件hfmtree.txt中讀入赫夫曼樹，返回葉子結(jié)點數(shù)if(fp=fopen("codefile.txt","rb")尸NULL)printf("Open file codefile.txt error!n");if(fw=fopen("textfile.txt","wb+")=NULL)printf(

18、"Open file textfile.txt error!n");code=(char *)malloc(sizeof(char);fscanf(fp,"%c",code); /從文件讀入一個字符for(i=1;!feof(fp);i+) code=(char *)realloc(code,(i+1)*sizeof(char); /增加空間fscanf(fp,"%c",&codei); /從文件讀入下一個字符 codei-1='0' / codefile.txt文件中的字符已全部讀入，存放在 code數(shù)組中t

19、ext=(char *)malloc(100*sizeof(char);p=text;m=2*n-1;if(*code='0')find(HT,code,text,HTm.lchild,m); /從根節(jié)點的左子樹去找elsefind(HT,code,text,HTm.rchild,m); /從根節(jié)點的右子樹去找for(i=0;pi!='0'i+) /把譯碼好的字符存入文件textfile.txt 中fputc(pi,fw);fclose(fp);fclose(fw);printf("n 已將 codefile.txt文件成功譯碼，兵已存入 textfi

20、le.txt 文件！ nn");將文件codefile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文 件寫入文件codeprint 中。void Print_code()FILE *fp,*fw;char temp;int i;if(fp=fopen("codefile.txt","rb")=NULL)printf("Open file codefile.txt error!n");if(fw=fopen("codeprint.txt","wb+")=NULL)pri

21、ntf("Open file codeprint.txt error!n");printf("n 文件 codefi1e 顯示如下：n");fscanf(fp,"%c",&temp); /從文件讀入一個字符for (i=1;!feof(fp);i+)printf("%c",temp);if(i%50=0) printf("n");fputc(temp,fw); /將該字符存入文件codeprint.txt 中fscanf(fp,"%c",&temp); /從文

22、件讀入一個字符printf("nn已將此字符形式的編碼寫入文件codeprint.txt 中！ nn");fclose(fp);fclose(fw);/將已在內(nèi)存中的哈夫曼樹顯示在屏幕上，并將此字符形式的哈夫曼樹寫入文件treeprint中。void Print_tree()unsigned char T100100;int i,j,m=0;FILE *fp;if(n=0)n=Read_tree(HT); / 從文件hfmtree.txt中讀入赫夫曼樹，返回葉子結(jié)點數(shù)存于數(shù)組Convert_tree(T,0,&m,2*n-1); /將內(nèi)存中的赫夫曼樹轉(zhuǎn)換成凹凸表形式

23、的樹，T中if(fp=fopen("treeprint.txt","wb+")=NULL)printf("Open file treeprint.txt error!n");printf("n打印已建好的赫夫曼樹：n");for(i=1;i<=2*n-1;i+)for (j=0;Tij!=0;j+)if(Tij=' ') printf(" ");fputc(Ti吐fp);elseprintf("%d",Tij);fprintf(fp,"%dn&

24、quot;,Tij);printf("n");fclose(fp);printf("n已將該字符形式的哈夫曼樹寫入文件treeprint.txt 中！ nn");/從文件hfmtree.txt中讀入赫夫曼樹，返回葉子節(jié)點數(shù)int Read_tree(HuffmanTree &HT)FILE *fp;int i,n;HT=(HuffmanTree)malloc(sizeof(HTNode);if(fp=fopen("hfmtree.txt","r")=NULL)printf("Open file h

25、fmtree.txt error!n");for (i=1;!feof(fp);i+)HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode); /增加空間fread(&HTi,sizeof(HTNode),1,fp); /讀入一個節(jié)點信息fclose(fp);n=(i-1)/2;return n;/譯碼時根據(jù)01字符串尋找相應(yīng)葉子節(jié)點的遞歸算法 void find(HuffmanTree &HT,char *code,char *text,int i,int m) if(*code!='0') /若譯碼未結(jié)束 c

26、ode+;if(HTi.lchild=0&&HTi.rchild=0) /若找到葉子節(jié)點*text=HTi.ch; /將葉子節(jié)點的字符存入text中text+;if(*code='0')從根節(jié)點的左子樹找從根節(jié)點的右子樹找從該節(jié)點的左子樹去找從該節(jié)點的右子樹去找find(HT,code,text,HTm.lchild,m); / else find(HT,code,text,HTm.rchild,m); /else /如果不是葉子節(jié)點if(*code='0')find(HT,code,text,HTi.lchild,m); / else find

27、(HT,code,text,HTi.rchild,m); /else*text='0' /譯碼結(jié)束/將文件中的赫夫曼樹轉(zhuǎn)換成凹凸表形式的赫夫曼樹打印出來 void Convert_tree(unsigned char T100100,int s,int *i,int j) int k,l;l=+(*i);for(k=0;k<s;k+)Tlk=''Tlk=HTj.weight;if(HTj.lchild)Convert_tree(T,s+1,i,HTj.lchild);if(HTj.rchild)Convert_tree(T,s+1,i,HTj.rchild

28、);Tl+k='0'； 四.調(diào)試步驟1. 赫夫曼樹節(jié)點的數(shù)據(jù)類型定義為：typedef struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild; HTNode,*HuffmanTree;2. void HuffmanCoding(HuffmanTree &,char *,int *,int);建立赫夫曼樹的算法，此函數(shù)塊調(diào)用了 Select ()函數(shù)。void select(HuffmanTree HT,int j,int *x,int *y);從已建好的赫夫曼樹中選擇 parent為0, weig

29、ht最小的兩個結(jié)點。3. 利用已建好的哈夫曼樹從文件hfmtree.txt中讀入，對文件中的正文進行編碼，然后將結(jié)果存入文件codefile.txt 中。4. coding編碼功能：對輸入字符進行編碼5. Decoding譯碼功能：利用已建好的哈夫曼樹將文件codefile.txt中的代碼進行譯碼，結(jié)果存入文件texfile.txt 中。6. Print()打印功能函數(shù)：輸出哈夫曼樹以及對應(yīng)的編碼。word教育資料D:codeblockcodeHaoYuweihafumanbinDebughafuman.exeTOTr去121-n ：122BB7請選擇操作翁化赫夫曼樹D:codeblockco

30、deHaoYuweihafumanbinDebughafuman.exe18G I 804751F l'> R 48 0 &3 GS4市夫曼樹建立成功.并已存于文件kF m七ye da中D:codeblockcodeHaoYuweihafumanbinDebughafuman.exe打印已建好的赫夫曼樹: 1348129576314，64801261B619695474H101se203015D:codeblockcodeHaoYuweihafumanbinDebughafuman.exe已將該字符形式的哈夫曼樹寫入文件七PC C m* in t / 乂七中!曼 4 夫

31、文曼 瀚 M夫 化 ffw 始碼碼印國 蕾譯I E D p T Qion tine * 310.342 星Pi*BS8 any key to cent inue半：tobetsns -記事本文件/編輯格式查看業(yè)程助（生 THIS PROGRAMtreeprint -記事本文件的遍與任】格式（。）萱看M幫助（H）47301551codefile -記事本文件的編輻任】格式（。）萱看凹幫助（H）01111000001111101110101101001111011110101011100六.分析與思考我的課程設(shè)計題目是赫夫曼編譯碼器。最初做這個程序的時候，讓我覺得 完成這次程序設(shè)計真的是太難了，

32、然后我查閱了課本，并去圖書館借了資料，在 寫這個程序的時候也參考了網(wǎng)上的設(shè)計流程，寫完剛運行時出現(xiàn)了很多問題。尤其是編碼錯誤，導致內(nèi)存無法read,通過同組人員的交流請教，逐漸明白過來， 然后經(jīng)過不知道多少次修改才順利運行。本次試驗也讓我明白了理論與實際相結(jié) 合的重要性，并提高了自己組織數(shù)據(jù)及編寫大型程序的能力，培養(yǎng)了基本的、良好的程序設(shè)計技能以及合作能力。通過對各個步驟各個流程的控制，逐漸讓我產(chǎn)生了興趣，在實際編寫過程中，和同學們相互討論讓我學到的不僅僅是一些解 決問題的方法，更是解決問題的思想。數(shù)據(jù)結(jié)構(gòu)實驗報告實驗五一.實驗內(nèi)容：查找表是數(shù)據(jù)處理的重要操作，試建立有100個結(jié)點的二叉排序樹

33、進行查找，然后用原數(shù)據(jù)建立 AVL樹，并比較兩者的平均查找長度?！净疽蟆?1)以鏈表作為存儲結(jié)構(gòu)，實現(xiàn)二叉排序樹的建立、查找和刪除。(2)根據(jù)給定的數(shù)據(jù)建立平衡二叉樹。(3)比較二叉排序樹和平衡二叉樹的平均查找長度。二.實驗目的熟練掌握順序查找、折半查找及二叉排序樹、平衡二叉樹上的查找、插入和 刪除的方法，比較它們的平均查找長度。三.程序清單#include<iostream>#include<stdlib.h>#include<string.h>#define EQ(a,b) (a)=(b)#define LT(a,b) (a)<(b)#defi

34、ne LQ(a,b) (a)>(b) using namespace std; typedef int Keytype;typedef struct Keytype key; /關(guān)鍵字域ElemType;typedef struct BSTnode ElemType data; int bf;struct BSTnode *lchild,*rchild;BSTnode,*BSTree;void InitBSTree(BSTree &T)T=NULL;void R_Rotate(BSTree &p)BSTnode *lc;lc=p->lchild;p->lchi

35、ld=lc->rchild;lc->rchild=p;p=lc;void L_Rotate(BSTree &p) BSTnode *rc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc；void Leftbalance(BSTree &T) BSTnode *lc,*rd;lc=T->lchild;switch(lc->bf)case +1:T->bf=lc->bf=0;R_Rotate(T);break;case -1:rd=lc->rchild;swit

36、ch(rd->bf) case 1:T->bf=-1;lc->bf=0;break;case 0:T->bf=lc->bf=0;break;case -1:T->bf=0;lc->bf=1;break;rd->bf=0;L_Rotate(T->lchild);R_Rotate(T);void Rbalance(BSTree &T)BSTnode *lc,*ld;lc=T->rchild;switch(lc->bf) case 1:ld=lc->lchild;switch(ld->bf) case 1:T-&g

37、t;bf=0;lc->bf=-1;break;case 0:T->bf=lc->bf=0;break;case -1:T->bf=1;lc->bf=0;break;ld->bf=0;R_Rotate(T->rchild);L_Rotate(T);case -1:T->bf=lc->bf=0;L_Rotate(T);break;int InsertAVL(BSTree &T,ElemType e,bool &taller) if(!T) T=(BSTree)malloc(sizeof(BSTnode);T->data=e

38、;T->lchild=T->rchild=NULL;T->bf=0;taller=true; else if(EQ(e.key,T->data.key) taller=false;cout<<" 結(jié)點"<<e.key<<"不存在。"<<endl;return 0;if(LT(e.key,T->data.key) if(!InsertAVL(T->lchild,e,taller) return 0;if(taller)switch(T->bf) case 1:Left

39、balance(T);taller=false;break;case 0:T->bf=+1; taller=true;break;case -1:T->bf=0;taller=false;break;else if(!InsertAVL(T->rchild,e,taller) return 0;if(taller) switch(T->bf) case 1:T->bf=0;taller=false;break;case 0:T->bf=-1;taller=true;break;case -1:Rbalance(T);taller=false;break;re

40、turn 1;bool SearchBST(BSTree T,ElemType key,BSTree f,BSTree &p) if(!T) P=f;cout<<"結(jié)點不存在。"<<endl;return false;else if( EQ(key.key,T->data.key) P=T;cout<<"查找成功，存在結(jié)點"cout<<p->data.key<<endl;return true;else if(LT(key.key,T->data.key)return

41、SearchBST(T->lchild,key,T,p);elsereturn SearchBST(T->rchild,key,T,p);void Leftbalance_div(BSTree &p,int &shorter) BSTree p1,p2; if(p->bf=+1) p p->bf=0;shorter=1;else if(p->bf=0)/p p->bf=-1;shorter=0;else p1=p->rchild;/p1 if(p1->bf=0)/p1不變 L_Rotate(p);p1->bf=1;p->

42、;bf=-1;shorter=0;else if(p1->bf=-1)/p1 L_Rotate(p); p1->bf=p->bf=0; shorter=1; else p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p; if(p2->bf=0) p->bf=0;p1->bf=0;else if(p2->bf=-1) p->bf=+1;p1->bf=0;結(jié)點的左子樹高，刪除結(jié)點后p的b

43、f減1,樹變矮結(jié)點左、右子樹等高，刪除結(jié)點后p的bf減1,樹高不變指向p的右子樹結(jié)點左、右子樹等高，刪除結(jié)點后p的bf為-2,進行左旋處理，樹高的右子樹高，左旋處理后，樹變矮)else p->bf=0;p1->bf=-1;)p2->bf=0;P=P2；shorter=1;)void Rbalance_div(BSTree &p,int &shorter) BSTree p1,p2;if(p->bf=-1) p->bf=0;shorter=1;)else if(p->bf=0) p->bf=+1;shorter=0;)else p1=p-

44、>lchild;if(p1->bf=0) R_Rotate(p);p1->bf=-1;p->bf=+1;shorter=0;)else if(p1->bf=+1) R_Rotate(p);p1->bf=p->bf=0;shorter=1;)else p2=p1->rchild;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

45、->bf=1) p->bf=-1; p1->bf=0; else p->bf=0; p1->bf=1;p2->bf=0;p=p2； shorter=1;void Delete(BSTree q,BSTree &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)Rbalance_div(r,shorter

46、);ElemType DeleteAVL(BSTree &p,ElemType key,int &shorter) ElemType k,a,b;a.key=1;b.key=0;BSTree q;if(p=NULL) cout<<"結(jié)點不存在。"<<endl;return b;else if(LT(key.key,p->data.key) )/在 p 的左子樹中進行刪除 k=DeleteAVL(p->lchild,key,shorter);if(shorter=1)Leftbalance_div(p,shorter);re

47、turn k;else if(LQ(key.key,p->data.key) )/在 p 的右子樹中進行刪除 k=DeleteAVL(p->rchild,key,shorter);if(shorter=1)Rbalance_div(p,shorter);return k;elseq=p;if(p->rchild=NULL) 右子樹空則只需重接它的左子樹 p=p->lchild; free(q)； shorter=1;else if(p->lchild=NULL)/左子樹空則只需重接它的右子樹 p=p->rchild;free(q);shorter=1; el

48、se Delete(q,q->lchild,shorter);if(shorter=1)Leftbalance_div(p,shorter);p=q; return a;void Print_BSTTree(BSTree T,int i) if(T) if(T->rchild)Print_BSTTree(T->rchild,i+1);for(int j=1;j<=i;j+) cout<<""cout<<T->data.key<<endl;if(T->lchild)Print_BSTTree(T->

49、lchild,i+1);int main()cout<<” 班級：中法121姓名：郝雨微學號：122887"<<endl;BSTree T;ElemType e;InitBSTree(T);bool tall=false;bool choice=true;chary; while(choice) cout<<"輸入要插入結(jié)點(數(shù)字):"；cin>>e.key;InsertAVL(T,e,tall);Print_BSTTree(T,0);cout<<"是否繼續(xù)，是選 y,否選n:"cin

50、>>y;if(y='Y'|y='y') choice=true;else choice=false;BSTree f,p;choice=true;while(choice) cout<<" 輸入要查找的結(jié)點："； cin>>e.key;SearchBST( T,e,f,p);cout<<"是否繼續(xù)，是選 y,否選n:cin>>y;if(y='Y'|y='y') choice=true;else choice=false;int shorter

51、; choice=true;while(choice) cout<<" 輸入要刪除的結(jié)點：”； cin>>e.key;DeleteAVL(T,e,shorter);Print_BSTTree(T,0);cout<<"是否繼續(xù)，是選 y,否選n:cin>>y;if(y='Y'|y='y') choice=true;else choice=false;return 0;#include<iostream>#include<stdlib.h>#include<string

52、.h>#define EQ(a,b) (a)=(b)#define LT(a,b) (a)<(b)#define LQ(a,b) (a)>(b) using namespace std;typedef int Keytype;typedef struct Keytype key; / 關(guān)鍵字域 ElemType;typedef struct BSTnode ElemType data;int bf;struct BSTnode *lchild,*rchild;BSTnode,*BSTree;void InitBSTree(BSTree &T)T=NULL;void R

53、_Rotate(BSTree &p)BSTnode *lc;lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;void L_Rotate(BSTree &p)BSTnode *rc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;void Leftbalance(BSTree &T)BSTnode *lc,*rd;lc=T->lchild;switch(lc->bf)case +1:T->bf=l

54、c->bf=0;R_Rotate(T);break;case -1:rd=lc->rchild;switch(rd->bf) case 1:T->bf=-1;lc->bf=0;break;case 0:T->bf=lc->bf=0;break;case -1:T->bf=0;lc->bf=1;break;rd->bf=0;L_Rotate(T->lchild);R_Rotate(T);void Rbalance(BSTree &T)BSTnode *lc,*ld;lc=T->rchild;switch(lc->

55、;bf) case 1:ld=lc->lchild;switch(ld->bf) case 1:T->bf=0;lc->bf=-1;break;case 0:T->bf=lc->bf=0;break;case -1:T->bf=1;lc->bf=0;break;ld->bf=0;R_Rotate(T->rchild);L_Rotate(T);case -1:T->bf=lc->bf=0;L_Rotate(T);break;int InsertAVL(BSTree &T,ElemType e,bool &ta

56、ller) if(!T) T=(BSTree)malloc(sizeof(BSTnode);T->data=e;T->lchild=T->rchild=NULL;T->bf=0;taller=true;else if(EQ(e.key,T->data.key) taller=false;cout<<" 結(jié)點"<<e.key<<"不存在。"<<endl;return 0;if(LT(e.key,T->data.key) if(!InsertAVL(T->lchild,

57、e,taller) return 0;if(taller)switch(T->bf) case 1:Leftbalance(T);taller=false;break;case 0:T->bf=+1;taller=true;break;case -1:T->bf=0;taller=false;break;else if(!InsertAVL(T->rchild,e,taller) return 0;if(taller)switch(T->bf) case 1:T->bf=0;taller=false;break;case 0:T->bf=-1;taller=true;break;case -1:Rbalance(T);taller=false;break;return 1;bool SearchBST(BSTree T,ElemType key,BSTree f,BSTree &p) if(!T) P=f;cout<<"結(jié)點不存在。"<<endl;return false;else if( EQ(key.key,T->data.key) P=T;cout<<&