实验报告-平衡二叉树

1、实习报告一、需求分析1、问题描述 利用平衡二叉树实现一个动态查找表。（1）实现动态查找表的三种基本功能：查找、插入和删除。（2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中。每次插入或删除一个结点后，应更新平衡二叉树的显示。（3）每次操作的关键字都要从文件中读取，并且关键字的集合限定为短整型数字1，2，3，关键字出现的顺序没有限制，允许出现重复的关键字，并对其进行相应的提示。（4）平衡二叉树的显示采用图形界面画出图形。 2、系统功能 打开数据文件，用文件中的关键字来演示平衡二叉树操作

2、的过程。 3、程序中执行的命令包括： （1）(L)oad from data file /在平衡的二叉树中插入关键字； （2）(A)ppend new record /在平衡的二叉树中查找关键字； （3）(U)pate special record /显示调整过的平衡二叉树； （4）(D)elete special record /删除平衡二叉树中的关键字； （5）(Q)uit /结束。 4、测试数据： 平衡二叉树为：图 1 插入关键字10之前的平衡二叉树插入关键字：10； 调整后：图 2 插入关键字10之后的平衡二叉树 删除关键字：14； 调整后： 图 3 删除关键字14后的平衡二叉树 查找

3、关键字：11； 输出： The data is here!图 3 查找关键字11后的平衡二叉树二、概要设计 本次实验目的是为了实现动态查找表的三种基本功能：查找、插入和删除。动态查找表可有不同的表示方法，在此次实验中主要是以平衡二叉树的结构来表示实现的，所以需要两个抽象数据类型：动态查找表和二叉树。1、 动态查找表的抽象数据类型定义为：ADT DynamicSearchTable数据对象 D ：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系 R ：数据元素同属于一个集合。 基本操作 P ： InitDSTable(&ST); 操作结果：构造

4、一个空的动态查找表DT。 DestroyDSTable(&DT); 初始条件：动态查找表DT存在。 操作结果：销毁动态查找表DT。 SearchDSTable(DT,key); 初始条件：动态查找表DT存在，key为和关键字类型相同的给丁值。 操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。 InsertDSTable(&DT,e); 初始条件：动态查找表DT存在，e为待插入的数据元素。 操作结果：若DT中不存在其关键字等于e，key的数据元素，则插入e到DT； DeleteDSTable(&DT,key); 初始条件：动态查找表DT存在，

5、key为和关键字类型相同的给定值。 操作结果：若DT中存在其关键字等于key的数据元素，则删除之。ADT DynamicSearchTable2、 二叉树抽象数据类型的定义为：ADT BinaryTree数据对象 D ：D是具有相同特性的数据元素的集合。 数据关系 R ： 若D=，则R=，称BinaryTree为空的二叉树； 若D，则R=H，H是如下二元关系：（1） 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2） 若Droot，则存在Droot=D1，Dr，且D1Dr=;（3） 若D1，则D1中存在唯一的元素x1，H，且存在D1上的关系H1H；若Dr，则Dr中存在唯一的元

6、素xr，H，且存在Dr上的关系HrH；H=，H1，Hr；（4） （D1，H1）是一棵符合本定义的二叉树，称为根的左子树，（Dr，Hr）是符合本定义的二叉树，称为根的右子树。基本操作 P：InitBiTree(&T);操作结果：构造空的二叉树T；DestroyBiTree(&T);初始条件：二叉树T存在。操作结果：销毁二叉树T。CreateBiTree(&T,definition);初始条件：definition给出T的定义。操作结果：按definition构造二叉树T。BiTreeEmpty(T);初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE，否则FALSE。LeftChi

7、ld(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回“空”。RightChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。InsertAVL(T,e,taller);初始条件：二叉树T存在，e为要插入的结点，taller反映T长高与否。操作结果：若在平衡二叉树中不存在和e相同关键字的结点，则插入一个数据元素为e的结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则旋转处理。RightProcess(T);初始条件：二叉树T存在。操作结果：对以T为根的二叉树做右旋转处理

8、，处理之后T指向新的树根结点。LeftProcess(T);初始条件：二叉树T存在。操作结果：对以T为根的二叉树做左旋转处理，处理之后T指向新的树根结点3、 本程序包括四个模块：（1）主程序模块： void main() for(;) switch()接受命令；处理命令； （2）二叉树单元模块： 实现二叉树的抽象数据类型。（3）动态查找表单元模块： 实现动态查找表的抽象数据类型。（4）结点结构模块： 实现平衡二叉树的查找、插入和删除操作。 各模块之间的关系：主程序模块二叉树单元模块：动态查找表单元模块结点结构模块图 4 各模块之间的关系三、详细设计1、元素类型、结点类型和指针类型； typed

9、ef int InfoTypetypedef struct node /*记录类型*/ InfoType data; /*其他数据域*/ Struct node lchild, rchild; /*左右孩子指针*/BSTNode,*BSTree;status MakeNode(BSTNode &p,ElemType e) /* 分配由p指向的数据元素为e、后继为空的结点,并返回 TRUE,扩若分配失败,则返回FALSE*/p=(BSTNode*)malloc(sizeof(BSTNode);if(!p) return FALSE;p-data=e;p-next =NULL;return TRU

10、E;void FreeNode(BSTNode &p)/* 释放 p 所指结点*/2、 根据动态查找表的基本操作特点：表结构本身是在查找过程中动态产生的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。在此次试验中主要是利用平衡二叉树来实现动态查找表。平衡二叉排序树定义为： typedef int InfoType typedef int KeyType; /*元素类型*/ typedef struct nodeKeyType key; /*关键字项*/ int bf; /*平衡因子*/ InfoType data; /*其他数据域*/

11、Struct node lchild, rchild; /*左右孩子指针*/ BSTNode,*BSTree; int taller; /*taller=0,平衡二叉数没有长高不需要调整；taller=1,二叉数长高,需要验证是否还是平衡二叉数,如果不是,则需要进行调整.*/ 平衡二叉树的基本操作定义如下： int InsertAVL(BSTNode *b,KeyType e,int *m); /如果在平衡二叉排序树b中不存在e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0.如果因插入而使二叉排序树失去平衡，则做平衡处理，指针m反应b长高与否。 void LeftPr

12、ocess(BSTree *p,int *m); /在插入结点时对以指针p所指结点为根的二叉树做左平衡旋转处理。 void RightProcess(BSTree *p,int *m); /在插入结点时对以指针p所指结点为根的二叉树做右平衡旋转处理。 int DeleteAVL(BSTree *p,KeyType x,int *m);/ /在以p为根的平衡二叉树中删除关键字为e的结点，如果因删除而使平衡二叉树失去平衡，则做平衡处理，指针m反应b树长高与否。 void LeftProcess1(BSTree *p,int *m); /由DeleteAVL()函数调用，在删除结点时进行左处理。 v

13、oid RightProcess1(BSTree *p,int *m); /由DeleteAVL()函数调用，在删除结点时进行右处理。 void Delete2(BSTree q,BSTree *r,int *m); /由DeleteAVL（）调用，用于处理被删除结点都不为空的情况。 void DrawTree(BSTree b); /对以b为根的平衡二叉树，以括号的形式显示出来。 void OutputTree(BSTree b,int fx,int fy,int prex,int prey); /用图形把平衡二叉树显示出来。3、 本程序实现的是演示平衡二叉树的操作过程，包括插入和删除操作，

14、以下是它们算法的设计。（1） 插入数据操作，如果数据存在，输出提示信息，如果不存在，则把此数据插入到入平衡二叉树中，并做相应的调整，使之还为平衡二叉树。以下是对插入操作的设计。 int InsertAVL(BSTree *b,KeyType e,int *m)/*若在平衡的二叉排序树中b中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回0。若因插入而使二叉排序树失去平衡，则做平衡旋转处理，taller的值反应长高与否。*/ if(*b=NULL) /*原为空树，插入新结点，树长高，置taller=*m=1*/ (*b)=(BSTNode*)malloc(sizeof(BST

15、Node); (*b)-key=e; (*b)-lchild=(*b)-rchild=NULL; (*b)-bf=0; *m=1; else if(e=(*b)-key) /*树中已存在和e有相同关键字的结点，则不再进行插入*/ *m=0; /*置taller=*m=0,树没有长高，不须进行调整*/ printf(n The data is here!n); /*输出提示信息*/ return 0; if(ekey) /*继续在*b的左子树中进行搜索*/ if(InsertAVL(&(*b)-lchild),e,&taller)=0) return 0; /*存在和e有相同关键字的元素，则不需

16、要插入*/ if(taller=1) /*已插入在*b的左子树中且左子树长高*/ LeftProcess(&(*b),&taller); else /*已插入在*b的右子树中且左子树长高*/ if(InsertAVL(&(*b)-rchild),e,&taller)=0) return 0; /*存在和e有相同关键字的元素则不需要插入*/ if(taller=1) /*已插入在*b的右子树中且右子树长高*/ RightProcess(&(*b),&taller); return 1; void LeftProcess(BSTree *p,int *m)/*对以指针p所指结点为根的二叉树做左平衡

17、旋转处理，算法结束后，指针 p指向新的根结点*/ BSTNode *p1,*p2; if(*p)-bf=0) /*原本左右子树等高，现因左子树增高而使树增高*/ (*p)-bf=1; *m=1； else if(*p)-bf=-1) /*原本右子树比左子树高，现左右子树等高*/ (*p)-bf=0; *m=0; /*树没有长高*/ else /*原本左子树比右子树高，需做左子树的平衡处理*/ p1=(*p)-lchild; /*p1指向*p的左子树根结点*/ if(p1-bf=1) /*新结点插入在*p的左孩子的右子树上，要做LL调整*/ (*p)-lchild=p1-rchild; /*p的

18、左孩子为p1的右孩子*/ p1-rchild=(*p); /*p1的右孩子为p*/ (*p)-bf=p1-bf=0; /*p和p1的平衡因子都变为0*/ *p=p1; /*p1取代以前p的位置*/ else if(p1-bf=-1) /*如果新结点插在*b的左子树根结点的右子树上，需做LR调整*/ p2=p1-rchild; /*p2指向p1的右子树根结点*/ p1-rchild=p2-lchild; /*p1的右孩子为p2的左孩子*/ p2-lchild=p1; /*p2的左孩子为p1*/ (*p)-lchild=p2-rchild; /*p的左孩子为p2的右孩子*/ p2-rchild=*

19、p; /*p2的右孩子为p*/ if(p2-bf=0) /*新结点插在p2处做叶子结点的情况*/ (*p)-bf=p1-bf=0; else if(p2-bf=1) /*新结点插在p2的左子树上的情况*/ p1-bf=0; (*p)-bf=-1; else /*新结点插在p2的右子树上的情况*/ p1-bf=1; (*p)-bf=0; *p=p2; (*p)-bf=0; /*仍将p指向新的根结点，并置其平衡因子为0*/ *m=0; /*返回值为*m=taller，在 InsertAVL（）递归调用时，依次判断每个结点的平衡因子是否在（-1，1）之间*/ void RightProcess(BS

20、Tree *p,int *m) /*对以指针p所指结点为根的二叉树做左平衡旋转处理，算法结束后，指针 p指向新的根结点*/ BSTNode *p1,*p2; if(*p)-bf=0) /*原本左右子树等高，现因右子树增高而使树增高*/ (*p)-bf=-1; *m=1; else if(*p)-bf=1) /*原本左子树比右子树高，现左右子树等高*/ (*p)-bf=0; *m=0; else /*原本右子树比左子树高，需做右子树的平衡处理*/ p1=(*p)-rchild; /*p1指向*p的右子树根结点*/ if(p1-bf=-1) /*如果新结点插在*b的左子树根结点的右子树上，需做RR

21、调整*/ (*p)-rchild=p1-lchild; p1-lchild=*p; (*p)-bf=p1-bf=0; *p=p1; else if(p1-bf=1) /*新结点插入在*p的右孩子的左子树上，要做RL调整*/ p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; (*p)-rchild=p2-lchild; p2-lchild=*p; if(p2-bf=0) /*新结点插在p2处做叶子结点的情况*/ (*p)-bf=p1-bf=0; else if(p2-bf=-1) /*新结点插在p2的右子树上的情况*/ p1-bf=0; (*p)-

22、bf=1; else /*新结点插在p2的左子树上的情况*/ p1-bf=-1; (*p)-bf=0; *p=p2; (*p)-bf=0; /*仍将p指向新的根结点，并置其平衡因子为0*/ *m=0; （2）以下是对删除算法的设计和实现。假设要删除关键字为x的结点，如果x 不在叶子结点上，则用它左子数中的最大值或最小值取代x；如此反复取代，直到删除动作传递到某个叶子接点。删除叶子结点时，若需要进行平衡变换，可采用插入的平衡变换的反变换（如：左子树变矮对应于右子树长高）； int DeleteAVL(BSTree *p,KeyType x,int *m)/*在AVL树中删除关键字为 x的结点。*

23、/ int k; BSTNode *q; if(*p)=NULL) return 0; else if(xkey) k=DeleteAVL(&(*p)-lchild),x,&taller); if(taller=1) LeftProcess1(&(*p),&taller); return k; else if(x(*p)-key) k=DeleteAVL(&(*p)-rchild),x,&taller); if(taller=1) RightProcess1(&(*p),&taller); return k; else /*找到了关键字为x的结点，由p指向它。*/ q=(*p); if(*p)

24、-rchild=NULL) /*被删结点右子树为空。*/ (*p)=(*p)-lchild; free(q); *m=1; else if(*p)-lchild=NULL) /*被删结点左子树为空。*/ *p=(*p)-rchild; free(q); *m=1; else /*被删结点左右子树都不为空。*/ Delete2(q,&(q-lchild),&taller); if(taller=1) LeftProcess1(&q,&taller); (*p)=q; return 1; void LeftProcess1(BSTree *p,int *m)/*在删除结点时进行左处理。*/BSTN

25、ode *p1,*p2; if(*p)-bf=1) (*p)-bf=0; /*需做RR调整。*/ *m=1; else if(*p)-bf=0) (*p)-bf=-1; *m=0; else p1=(*p)-rchild; if(p1-bf=0) (*p)-rchild=p1-lchild; p1-lchild=*p; p1-bf=1;(*p)-bf=-1; *p=p1; *m=0; else if(p1-bf=-1) /*需做RR调整。*/ (*p)-rchild=p1-lchild; p1-lchild=*p; (*p)-bf=p1-bf=0; *p=p1; *m=1; else /*需做

26、RL调整。*/ 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; else (*p)-bf=0; p1-bf=-1; p2-bf=0; *p=p2; *m=1; void RightProcess1(BSTree *p,int *m)/*在删除结点时进行右处理。*/BSTNode *p1,*p2; if(*p)-bf=-1) (*p)-

27、bf=0; *m=-1; else if(*p)-bf=0) (*p)-bf=1; *m=0; else p1=(*p)-lchild; if(p1-bf=0) /*需做LL调整。*/ (*p)-lchild=p1-rchild; p1-rchild=*p; p1-bf=-1;(*p)-bf=1; *p=p1; *m=0; else if(p1-bf=1) /*需做LL调整。*/ (*p)-lchild=p1-rchild; p1-rchild=*p; (*p)-bf=p1-bf=0; (*p)=p1; *m=1; else p2=p1-rchild; p1-rchild=p2-lchild;

28、 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 /*需做LR调整。*/ (*p)-bf=0; p1-bf=1; p2-bf=0; *p=p2; *m=1; void Delete2(BSTree q,BSTree *r,int *m)/*由DeleteAVL( )调用，用于处理被删除结点左右子树均不为空的情况。*/if(*r)-rchild=NULL) q-key=(*r)-key; q=*

29、r; *r=(*r)-lchild; free(q); *m=1; else Delete2(q,&(*r)-rchild),&taller); if(taller=1) RightProcess1(&(*r),&taller); （3）以下是对二叉树输出的设计，包括以括号的形式输出和以图形的形式输出。void DispBSTree(BSTree b)/*以括号的形式输出*/ if(b!=NULL) printf(%d,b-key); if(b-lchild!=NULL|b-rchild!=NULL) printf(); DispBSTree(b-lchild); if(b-rchild!=N

30、ULL) printf(,); DispBSTree(b-rchild); printf(); void OutputTree(BSTree b,int fx,int fy,int prex,int prey)/*以图形的形式输出*/ char str30; if(b) b-x=fx; b-y=fy; sprintf(str,%d,b-key); setcolor(RED); outtextxy(fx-2,fy-2,str); setcolor(YELLOW); circle(fx,fy,15); line(prex,prey,fx,fy); OutputTree(b-lchild,fx-50

31、,fy+50,fx,fy); OutputTree(b-rchild,fx+50,fy+50,fx,fy); 4、 以下是对主函数部分的设计。void main() BSTree b=NULL; int i,k,j,n; FILE *fp; int m50; for(;) /*用for()循环语句控制每次选择*/ /*菜单*/ printf(n=Menu=n); printf(n 1: Load from the file;n); printf(n 2: Append new record;n); printf(n 3: Upate special record;n); printf(n 4:

32、 Delete special record;n); printf(n 5: Quit;n); printf(n=n); printf(n Please input your choose: j=(1-5)?nn j=); scanf(%d,&j); /*输入选择*/ switch(j) case 1: /*从文件中读出数据*/ if(fp=fopen(c:TC20nana.txt,rb)=NULL) printf(n Cannot open file,strike any key exit!n); getch(); exit(0); printf(n Please input the datas number: n= ); scanf(%d,&n); /*输入需要操作元素的范围（即个数）*/ for(i=1;i=n;i+) fscanf(fp,%d,(m+i); printf(n You can chose data from this range:n); printf(n); for(i=1;ilchild中找删除的合适位置，递归调用DeleteAVL( )函数后要写上LefeProcess1( )函数的操作。3、在设计用图形显示出平衡二叉树时，要在TC2.0的编译器中运行程序，因为只有TC2.0支持画图的功能。