数据结构课程设计AVL树实现及其分析实验报告

算法与数据结构课程设计报告题目: AVLree的实现及分析班级:12计算机1学号:1200303132姓名:熊成毅成绩:2013年12月31日一、AVLree的实现及分析AVL树是平衡的二元查找树。一株平衡的二元查找树就是指对其每一个节点，其左子树和右子树的高度只差不超过1.编写程序实现AVL树的判别；并实现AVL树的ADT，包括其上的基本操作；节点的加入和删除。BSt和AVL的差别就在平衡性上，所以AVL的操作关键要考虑如何在保持二元查找树定义条件下对二元树进行平衡化。编写AVL树的判别程序，并判别一个人元查找数是否为AVL树。二元查找树用其先序遍历结果表示，如：5,2,1,3,7,8.实现AVL树的ADT，包括其上的基本操作：节点的加入和删除，另外包括将一般二元查找树转变为AVL树的操作。二、设计思想（宋体，三号加粗）任意给定一组数据，设计一个算法，建立一棵平衡二叉树，对它进行查找、插入、删除等操作。平衡二叉树ADT结构如下：typedefstruct{ Statuskey;}ElemType;typedefstructBSTNode{ ElemTypedata; Statusbf; structBSTNode*lchild,*rchild;}BSTNode,*BSTree;给出一组数据，通过InsertAVL(BSTree&T,ElemTypee,Status&taller)插入算法，构建平衡二叉树，若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。在此算法中，利用到递归算法和LeftBalance(BSTree&T)左平衡处理，RightBalance(BSTree&T)右平衡处理。进而实现构建平衡二叉树，使其左子树和右子树的高度之差不超过1.LeftBalance(BSTree&T）对以指针T所指结点为根的二叉树作左平衡旋转处理。本算法结束时，指针T指向新的根结点。RightBalance(BSTree&T)//对以指针T所指结点为根的二叉树作右平衡旋转处理。本算法结束时，指针T指向新的根结点。R_Rotate(BSTree&p)对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点L_Rotate(BSTree&p)对以p↑为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转处理之前的右子树的根结点存在一个平衡二叉树，通过DeleteBST(BSTree&T,Statuskey)和Delete(BSTree&p)实现删除节点操作；Delete(BSTree&p)从二叉排序树中删除结点p，并重接它的左或右子树。DeleteBST(BSTree&T,Statuskey)若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点p，并返回TRUE；否则返回FALSE。存在一个平衡二叉树，通过SearchBST(BSTreeT,Statuskey,BSTreef,BSTree&p)实现查找节点操作；SearchBST(BSTreeT,Statuskey,BSTreef,BSTree&p)在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上访问的最后一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL。存在一个二元排序树或二元查找树通过Balance(BSTreeT)算法判断是否为AVL树，Balance(BSTreeT)递归判断是不是平衡二叉树。三、软件结构图及流程图（宋体，三号加粗）主函数流程图：开始开始选择功能选择功能删 除节 点构建AVL树删 除节 点构建AVL树1 2查 找节 点查 找节 点插 入节 点插 入节 点0结束结束构建AVL树和插入结点流程图：开始开始判断根结点是否存在判断根结点是否存在否是是否相同是否相同创建结点是 否创建结点插入失败插入失败插入插入平衡旋转处理平衡旋转处理结束结束查找函数流程图：开始开始判断判断输出查询数据输出查询数据查找失败查找失败结束结束删除函数流程图：开始开始查找查找删除数据删除失败删除数据删除失败结束结束四、测试（宋体，三号加粗）创建AVL树，输入一组数据：按先序遍历输出：删除节点7；先序遍历结果：插入数据6后的先序遍历结果：然后退出子目录操作。输入一组数据创建BST树，判断创建的BST是否为AVL树：创建的BST树不是AVL树，将BST转换为AVL树五、源程序（宋体，三号加粗）函数头代码#include"iostream.h"#include<stdio.h>#include<malloc.h>#defineMAXNODE100#defineTRUE1#defineFALSE0#defineOVERFLOW1#defineLH+1#defineEH0#defineRH-1typedefintStatus;typedefcharTElemType;typedefstruct{ Statuskey;}ElemType;typedefstructBSTNode{ ElemTypedata; Statusbf; structBSTNode*lchild,*rchild;}BSTNode,*BSTree;StatusSearchBST(BSTreeT,Statuskey,BSTreef,BSTree&p){//算法9.5(b)//在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，//若查找成功，则指针p指向该数据元素结点，并返回TRUE，//否则指针p指向查找路径上访问的最后一个结点并返回FALSE，//指针f指向T的双亲，其初始调用值为NULLif(!T){p=f;returnFALSE;}//查找不成功elseif(key==T->data.key){p=T;returnTRUE;}//查找成功elseif(key<T->data.key)returnSearchBST(T->lchild,key,T,p);//在左子树中继续查找elsereturnSearchBST(T->rchild,key,T,p);//在右子树中继续查找}//SearchBSTStatusInsertBST(BSTree&T,ElemTypee){//算法9.6//当二叉排序树T中不存在关键字等于e.key的数据元素时，//插入e并返回TRUE，否则返回FALSEBSTreep,s;if(!SearchBST(T,e.key,NULL,p)){//查找不成功s=(BSTree)malloc(sizeof(BSTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//插入s为新的根结点elseif(e.key<p->data.key)p->lchild=s;//插入s为左孩子elsep->rchild=s;//插入s为右孩子returnTRUE;}elsereturnFALSE;//树中已有关键字相同的结点，不再插入}//InsertBSTStatusCreateBST(BSTree&T)//将输入的一组数据，创建为二叉排序树{ Statusnum; ElemTypee; cout<<"请输入二叉排序树结点数:"<<endl; cin>>num; while(num!=0) { cout<<"请输入结点值:"<<endl; cin>>e.key; InsertBST(T,e);//按二叉排序树插入方法； num--; } return0;}Statusmax(Statuslchild,Statusrchild)//取较大的值返回{ if(lchild>rchild) returnlchild; else returnrchild;}StatusDepth_bt(BSTreeT)//求二叉树深度{if(T==NULL)return0;return1+max(Depth_bt(T->lchild),Depth_bt(T->rchild));}StatusBalance(BSTreeT)//递归判断是不是平衡二叉树{Statusbl,br;if(T==NULL)return1;//空树输出是平衡二叉树bl=Depth_bt(T->lchild);//将左子树的深度赋值给blbr=Depth_bt(T->rchild);//将右子树的深度赋值给brif(bl-br>1||br-bl>1)return0;//如果不满足平衡二叉树的定义返回错误信息returnBalance(T->lchild)&&Balance(T->rchild);//递归调用}Statusn=0;voidN_PreOrderAVL(BSTreeT)//先序遍历（根，左，右）{ if(T) { cout<<""<<T->data.key; n++; N_PreOrderAVL(T->lchild); N_PreOrderAVL(T->rchild); }}Statusk_ey[40],k=0;voidKey_PreOrderAVL(BSTreeT)//先序遍历（根，左，右）{ if(T) { if(k<n) { k_ey[k]=T->data.key; k++; } Key_PreOrderAVL(T->lchild); Key_PreOrderAVL(T->rchild); }}intPreorderAVL(BSTreeT){if(T){cout<<T->data.key<<"";PreorderAVL(T->lchild);PreorderAVL(T->rchild);} return1;}voidR_Rotate(BSTree&p){//算法9.9//对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，//即旋转处理之前的左子树的根结点BSTreelc;lc=p->lchild;//lc指向*p的左子树根结点p->lchild=lc->rchild;//lc的右子树挂接为*p的左子树lc->rchild=p;p=lc;//p指向新的根结点}//R_RotatevoidL_Rotate(BSTree&p){//算法9.10//对以p↑为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，//即旋转处理之前的右子树的根结点BSTreerc;rc=p->rchild;//rc指向*p的右子树根结点p->rchild=rc->lchild;//rc的左子树挂接为*p的右子树rc->lchild=p;p=rc;//p指向新的根结点}//L_RotatevoidLeftBalance(BSTree&T){//算法9.12//对以指针T所指结点为根的二叉树作左平衡旋转处理。//本算法结束时，指针T指向新的根结点BSTreelc,rd;lc=T->lchild;//lc指向*T的左子树根结点switch(lc->bf){//检查*T的左子树的平衡度，并作相应平衡处理caseLH://新结点插入在*T的左孩子的左子树上，要作单右旋处理T->bf=lc->bf=EH;R_Rotate(T);break;caseRH://新结点插入在*T的左孩子的右子树上，要作双旋处理rd=lc->rchild;//rd指向*T的左孩子的右子树根switch(rd->bf){//修改*T及其左孩子的平衡因子caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}//switch(rd->bf)rd->bf=EH;L_Rotate(T->lchild);//对*T的左子树作左旋平衡处理R_Rotate(T);//对*T作右旋平衡处理}//switch(lc->bf)}//LeftBalancevoidRightBalance(BSTree&T){//算法9.12//对以指针T所指结点为根的二叉树作右平衡旋转处理。//本算法结束时，指针T指向新的根结点BSTreerc,ld;rc=T->rchild;//rc指向*T的右子树根结点switch(rc->bf){//检查*T的右子树的平衡度，并作相应平衡处理caseRH://新结点插入在*T的右孩子的右子树上，要作单右旋处理T->bf=rc->bf=EH;L_Rotate(T);break;caseLH://新结点插入在*T的右孩子的左子树上，要作双旋处理ld=rc->lchild;//ld指向*T的右孩子的左子树根switch(ld->bf){//修改*T及其右孩子的平衡因子caseLH:T->bf=EH;rc->bf=RH;break;caseEH:T->bf=rc->bf=EH;break;caseRH:T->bf=LH;rc->bf=EH;break;}//switch(rd->bf)ld->bf=EH;R_Rotate(T->rchild);//对*T的右子树作右旋平衡处理L_Rotate(T);//对*T作左旋平衡处理}//switch(lc->bf)}//LeftBalanceStatusInsertAVL(BSTree&T,ElemTypee,Status&taller){//算法9.11//若在平衡的二叉排序树T中不存在和e有相同关键字的结点，//则插入一个数据元素为e的新结点，并返回1，否则返回0。//若因插入而使二叉排序树失去平衡，则作平衡旋转处理，//布尔变量taller反映T长高与否if(!T){//插入新结点，树"长高"，置taller为TRUET=(BSTree)malloc(sizeof(BSTNode));T->data=e;T->lchild=T->rchild=NULL;T->bf=EH;taller=TRUE;}else{if(e.key==T->data.key)//树中已存在和e有相同关键字的结点{taller=FALSE;return0;}//则不再插入if((e.key<T->data.key)){//应继续在*T的左子树中进行搜索if(InsertAVL(T->lchild,e,taller)==0)return0;//未插入if(taller)//已插入到*T的左子树中且左子树"长高"switch(T->bf){//检查*T的平衡度caseLH://原本左子树比右子树高，需要作左平衡处理LeftBalance(T);taller=FALSE;break;caseEH://原本左、右子树等高，现因左子树增高而使树增高T->bf=LH;taller=TRUE;break;caseRH://原本右子树比左子树高，现左、右子树等高T->bf=EH;taller=FALSE;break;}//switch(T->bf)}//ifelse{//应继续在T↑的右子树中进行搜索if(InsertAVL(T->rchild,e,taller)==0)return0;if(taller)//已插入到*T的右子树且右子树长高switch(T->bf){//检查*T的平衡度caseLH://原本左子树比右子树高，现左、右子树等高T->bf=EH;taller=FALSE;break;caseEH://原本左、右子树等高，现因右子树增高而使树增高T->bf=RH;taller=TRUE;break;caseRH://原本右子树比左子树高，需要作右平衡处理RightBalance(T);taller=FALSE;break;}//switch(T->bf)}//else}//elsereturn1;}//InsertAVLStatusDelete(BSTree&p){//算法9.8//从二叉排序树中删除结点p，并重接它的左或右子树BSTreeq,s;if(!p->rchild){//右子树空则只需重接它的左子树q=p;p=p->lchild;free(q);}elseif(!p->lchild){//只需重接它的右子树q=p;p=p->rchild;free(q);}else{//左右子树均不空q=p;s=p->lchild;while(s->rchild)//转左，然后向右到尽头{q=s;s=s->rchild;}p->data=s->data;//s指向被删结点的“后继”if(q!=p)q->rchild=s->lchild;//重接*q的右子树elseq->lchild=s->lchild;//重接*q的左子树free(s);}returnTRUE;}//DeleteStatusDeleteBST(BSTree&T,Statuskey){//算法9.7//若二叉排序树T中存在关键字等于key的数据元素时，//则删除该数据元素结点p，并返回TRUE；否则返回FALSEif(!T)returnFALSE;//不存在关键字等于key的数据元素else{if(key==T->data.key)//找到关键字等于key的数据元素returnDelete(T);elseif(key<T->data.key)returnDeleteBST(T->lchild,key);elsereturnDeleteBST(T->rchild,key);}}//DeleteBST主函数代码#include"AVL.h"intmain(){Statusi,j,t,r=0,e,num; ElemTypeavl;//TElemType;Statustaller=0;BSTreeA=NULL,B=NULL,AVL=NULL;cout<<"AVL树的实现\n";cout<<"*******************************\n";cout<<"*1、输入数据，建立AVL树*\n"; cout<<"*2、输入数据，建立BST树*\n";//cout<<"*3、判断二元树是否为AVL树*\n";cout<<"*0、退出系统*\n";cout<<"*******************************\n"; cout<<"请输入选择:";cin>>i;while(i!=0){if(i==1){cout<<"AVL树的简单操作\n";cout<<"******************************\n";cout<<"*1、建立AVL树,先序遍历*\n";cout<<"*2、删除结点*\n";cout<<"*3、插入结点*\n";cout<<"*4、查找结点*\n";cout<<"*0、退出本操作*\n";cout<<"******************************\n"; cout<<"请输入选择:";cin>>j;while(j!=0){if(j==1){ cout<<"请你输入AVL树的节点数目：\n"; cin>>num;cout<<"请输入数据：";while(num!=0){ cin>>avl.key;InsertAVL(A,avl,taller);num--;}cout<<"先序遍历结果";PreorderAVL(A); cout<<"\n\n";}elseif(j==2){cout<<"输入想要删除的数据：";cin>>t;DeleteBST(A,t); N_PreOrderAVL(A); Key_PreOrderAVL(A); num=0; A=NULL; while(num<n){ avl.key=k_ey[num];InsertAVL(A,avl,taller);num++;}//PreorderAVL(A); cout<<"\n\n";}elseif(j==3){cout<<"输入想要插入的数据：";cin>>avl.key;InsertAVL(A,avl,taller);PreorderAVL(A); cout<<"\n\n";}elseif(j==4){cout<<"输入想要查找的数据：";cin>>avl.key;if(SearchBST(A,avl.key,NULL,AVL)) cout<<"查找成功，资料数据为"<<AVL->data.key<<endl;else cout<<"此树中没有"<<avl.key<<"元素"<<endl; cout<<"\n\n";}else{cout<<"操作失败！\n";} cout<<"AVL树的简单操作\n"; cout<<"******************************\n"; cout<<"*1、建立AVL树,先序遍历*\n"; cout<<"*2、删除结点*\n"; cout<<"*3、插入结点*\n"; cout<<"*4、查找结点*\n"; cout<<"*0、退出本操作*\n"; cout<<"******************************\n";cout<<"请继续在子目录中选择：";cin>>j;}A=NULL;}elseif(i==2){ cout<<"BST树的简单操作\n";cout<<"******************************\n";cout<<"*1、建立BST树,先序遍历*\n"; cout<<"*2、判断BST树是否为AVL树*\n"; cout<<"*3、将BST树转换为AVL树*\n";cout<<"*0、退出本操作*\n";cout<<"******************************\n"; cout<<"请继续在目录中选择："; cin>>e; while(e!=0) { if(e==1) { cout<<"请你输入BST树的节点数目：\n"; cin>>num;cout<<"请输入数据：";while(num!=0){ cin>>avl.k