数据结构试验报告

1、数据结构实验报告班级姓名学号实验三一.实验内容：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码， 在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息 的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈 夫曼的编/译码系统。一个完整的系统应具有以下功能：(1) I :初始化(Initialization )。从终端读入字符集大小n,以及n个字符 和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。(2) E：编码(Encoding)。利用以建好的哈夫曼树(如不在

2、内存，则从文件 hfmTree中读入)，对文件ToBeTran中的正文进行编码，然后将结果存入 文件CodeFile中。(3) D:译码(Decoding)。利用已经建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件 TextFile中。(4) P：打印代码文件(Print )。将文件CodeFile以紧凑格式显示在终端上，每行50个代码，同时将此字符形式的编码写入文件CodePrint中。T:打印哈夫曼树(Tree printing )。将已经在内存中的哈夫曼树以直观的 方式(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。二.实验目

3、的(1)掌握二叉树的存储结构及其相关操作。(2)掌握构造哈夫曼树的基本思想，及其编码/译码过程。三.程序清单#include <stdio.h>#include <stdlib.h>#include <string.h>/定义赫夫曼树结点的结构体typedef structchar ch;/增加一个域，存放该节点的字符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最小的两个结点void Init();void Coding。； / 编码void Decoding。； / 译码void Print_code(); /打印译码好的代码void Print_tree(); /打印哈夫曼树译码时根据 01将内存中的122887'n");int Read_tree(Huffma

5、nTree &); 从文件中读入赫夫曼树void find(HuffmanTree &HT,char *code,char *text,int i,int m); /字符串寻找相应叶子节点的递归算法void Convert_tree(unsigned char T100100,int s,int *i,int j); /赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; /全局变量int n=0; /全局变量，存放赫夫曼树叶子结点的数目int main()printf(" 班级：中法121姓名：郝雨微学号:char select;while(1)tips

6、();scanf("%c",&select);switch(select) /选择操作，根据不同的序号选择不同的操作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");/初始化函数，输入 n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree 中void Init()FILE *fp;int i,n,w52; /数组存放字符的权值char character52; / 存放 n 个字符printf("n输入字符个数 n:");scanf("%d",&n);/输入字符集大小printf("输入d个字符及其又应的权值：n",n);for (i=0;i<n;i+)char b=getchar();scanf("%c",&am

9、p;characteri);scanf("%d”,&wi);/输入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最小的两个结点，用 x和y返回其序号 void select(HuffmanTree HT,int j,int *x,int *y) int i;/查找weight最小的结点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次小的结点 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中的正文进行编码，然后将结果存入文件codefile 中void Coding。FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;if(n=0)n=Read_tree(HT);/从文件hfmtree.txt中读入赫夫曼树，返回叶子结点数/求赫夫曼树中各叶子

14、节点的字符对应的的编码，并存于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)在赫夫曼树中查找字符所在的位置将字符对应的编码存入文件从文件读入下一个字符成功编码，并已存入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 中的代码进行译码，结

17、果存入文件 textfile 中void Decoding。 FILE *fp,*fw;int m,i;char *code,*text,*p;if(n=0)n=Read_tree(HT);/从文件hfmtree.txt中读入赫夫曼树，返回叶子结点数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数组中t

19、ext=(char *)malloc(100*sizeof(char);p=text;m=2*n-1;if(*code='0')find(HT,code,text,HTm.lchild,m); /从根节点的左子树去找elsefind(HT,code,text,HTm.rchild,m); /从根节点的右子树去找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);/将已在内存中的哈夫曼树显示在屏幕上，并将此字符形式的哈夫曼树写入文件treeprint中。void Print_tree()unsigned char T100100;int i,j,m=0;FILE *fp;if(n=0)n=Read_tree(HT); / 从文件hfmtree.txt中读入赫夫曼树，返回叶子结点数存于数组Convert_tree(T,0,&m,2*n-1); /将内存中的赫夫曼树转换成凹凸表形式

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中读入赫夫曼树，返回叶子节点数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); /读入一个节点信息fclose(fp);n=(i-1)/2;return n;/译码时根据01字符串寻找相应叶子节点的递归算法 void find(HuffmanTree &HT,char *code,char *text,int i,int m) if(*code!='0') /若译码未结束 c

26、ode+;if(HTi.lchild=0&&HTi.rchild=0) /若找到叶子节点*text=HTi.ch; /将叶子节点的字符存入text中text+;if(*code='0')从根节点的左子树找从根节点的右子树找从该节点的左子树去找从该节点的右子树去找find(HT,code,text,HTm.lchild,m); / else find(HT,code,text,HTm.rchild,m); /else /如果不是叶子节点if(*code='0')find(HT,code,text,HTi.lchild,m); / else find

27、(HT,code,text,HTi.rchild,m); /else*text='0' /译码结束/将文件中的赫夫曼树转换成凹凸表形式的赫夫曼树打印出来 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'； 四.调试步骤1. 赫夫曼树节点的数据类型定义为：typedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild; HTNode,*HuffmanTree;2. void HuffmanCoding(HuffmanTree &,char *,int *,int);建立赫夫曼树的算法，此函数块调用了 Select ()函数。void select(HuffmanTree HT,int j,int *x,int *y);从已建好的赫夫曼树中选择 parent为0, weig

29、ht最小的两个结点。3. 利用已建好的哈夫曼树从文件hfmtree.txt中读入，对文件中的正文进行编码，然后将结果存入文件codefile.txt 中。4. coding编码功能：对输入字符进行编码5. Decoding译码功能：利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件texfile.txt 中。6. Print()打印功能函数：输出哈夫曼树以及对应的编码。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 -记事本文件/编辑格式查看业程助（生 THIS PROGRAMtreeprint -记事本文件的遍与任】格式（。）萱看M帮助（H）47301551codefile -记事本文件的编辐任】格式（。）萱看凹帮助（H）01111000001111101110101101001111011110101011100六.分析与思考我的课程设计题目是赫夫曼编译码器。最初做这个程序的时候，让我觉得 完成这次程序设计真的是太难了，

32、然后我查阅了课本，并去图书馆借了资料，在 写这个程序的时候也参考了网上的设计流程，写完刚运行时出现了很多问题。尤其是编码错误，导致内存无法read,通过同组人员的交流请教，逐渐明白过来， 然后经过不知道多少次修改才顺利运行。本次试验也让我明白了理论与实际相结 合的重要性，并提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能以及合作能力。通过对各个步骤各个流程的控制，逐渐让我产生了兴趣，在实际编写过程中，和同学们相互讨论让我学到的不仅仅是一些解 决问题的方法，更是解决问题的思想。数据结构实验报告实验五一.实验内容：查找表是数据处理的重要操作，试建立有100个结点的二叉排序树

33、进行查找，然后用原数据建立 AVL树，并比较两者的平均查找长度。【基本要求】(1)以链表作为存储结构，实现二叉排序树的建立、查找和删除。(2)根据给定的数据建立平衡二叉树。(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; /关键字域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<<" 结点"<<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<<"结点不存在。"<<endl;return false;else if( EQ(key.key,T->data.key) P=T;cout<<"查找成功，存在结点"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;结点的左子树高，删除结点后p的b

43、f减1,树变矮结点左、右子树等高，删除结点后p的bf减1,树高不变指向p的右子树结点左、右子树等高，删除结点后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<<"结点不存在。"<<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<<"输入要插入结点(数字):"；cin>>e.key;InsertAVL(T,e,tall);Print_BSTTree(T,0);cout<<"是否继续，是选 y,否选n:"cin

50、>>y;if(y='Y'|y='y') choice=true;else choice=false;BSTree f,p;choice=true;while(choice) cout<<" 输入要查找的结点："； cin>>e.key;SearchBST( T,e,f,p);cout<<"是否继续，是选 y,否选n:cin>>y;if(y='Y'|y='y') choice=true;else choice=false;int shorter

51、; choice=true;while(choice) cout<<" 输入要删除的结点：”； cin>>e.key;DeleteAVL(T,e,shorter);Print_BSTTree(T,0);cout<<"是否继续，是选 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; / 关键字域 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<<" 结点"<<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<<"结点不存在。"<<endl;return false;else if( EQ(key.key,T->data.key) P=T;cout<<&