资源描述：
《数据结构程序报告(平衡二叉树的操作).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机科学学院数据结构课程设计报告平衡二叉树操作学生姓名：学号：班级：指导老师：报告日期：1.需求分析1．建立平衡二叉树并进行创建、查找、插入、删除等功能。2．设计一个实现平衡二叉树的程序，可进行创建、查找、插入、删除等操作，实现动态的输入数据，实时的输出该树结构。3．测试数据：自选数据2.概要设计1.抽象数据类型定义：typedefstructBSTNode{intdata;intbf;//节点的平衡因子structBSTNode*lchild,*rchild;//左右孩子指针}BSTNode,*BSTree;voidCreat
2、BST(BSTree&T);//创建平衡二叉树voidR_Rotate(BSTree&p);//对以*p为根的二叉排序树作左旋处理voidL_Rotate(BSTree&p);//对以*p为根的二叉排序树作左旋处理voidLeftBalance(BSTree&T);//对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理voidRightBalance(BSTree&T);//对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理boolInsertAVL(BSTree&T,inte,bool&taller);//插入结点eboolSearch
3、BST(BSTree&T,intkey);//查找元素key是否在树T中voidLeftBalance_div(BSTree&p,int&shorter);//删除结点时左平衡旋转处理voidRightBalance_div(BSTree&p,int&shorter);//删除结点时右平衡旋转处理voidDelete(BSTreeq,BSTree&r,int&shorter);//删除结点intDeleteAVL(BSTree&p,intx,int&shorter);//平衡二叉树的删除操作voidPrintBST(BSTreeT
4、,intm);//按树状打印输出二叉树的元素2.主程序的流程请输入操作的选项编号（1-5）1---创建平衡二叉树2---查找3---插入4---删除5---结束3.各模块之间的层次调用退出输出删除插入查找平衡化输入数据元素显示主菜单主模块1.详细设计1.以平衡二叉树的插入和平衡化为例：boolInsertAVL(BSTree&T,inte,bool&taller){//若存在平衡的二叉排序树T中不存在和e有相同关键字的节点，则插入一个数据元素为e//的新结点，并返回1，否者返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转理，/
5、/布尔变量taller反映T长高与否。if(!T)//插入新结点，树“长高”，置taller为true{T=(BSTree)malloc(sizeof(BSTNode));T->data=e;T->lchild=T->rchild=NULL;T->bf=EH;taller=true;}else{if(EQ(e,T->data))//树中已存在和有相同关键字的结点{taller=false;printf("已存在相同关键字的结点");return0;}//则不再插入if(LT(e,T->data))//应继续在*T的左子树中进行
6、搜索{if(!InsertAVL(T->lchild,e,taller))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;talle
7、r=false;break;}//switch(T->bf)}//ifelse//应继续在*T的右子树中进行搜索{if(!InsertAVL(T->rchild,e,taller))return0;//未插入if(taller)//已插入到*T的右子树中且右子树“长高”switch(T->bf)//检查*T的平衡度{caseLH://原本左子树比右子树高，现左、右子树等高T->bf=EH;taller=false;break;caseEH://原本左子树、右子等高，现因右子树增高而使树增高T->bf=RH;taller=true;
8、break;caseRH://原本右子树比左子树高，需要作右平衡处理RightBalance(T);taller=false;break;}//switch(T->bf)}//else}//elsereturn1;}//InsertAVL2.说明：
