欢迎来到天天文库
浏览记录
ID:35555781
大小:528.38 KB
页数:32页
时间:2019-03-28
《实验四-平衡二叉树演示》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、实验四平衡二叉树演示1.问题定义及需求分析1.1课题目的和任务问题描述:利用平衡二叉树设计动态查找表。实验要求:设计平衡二叉树的动态演示的模拟程序。1)采用平衡二叉树存储结构。2)完成平衡二叉树的创建、查找、插入和删除的演示操作。3)可以考虑两棵平衡二叉树的合并。1.2数据形式输入数据形式:通过键盘输入数据输入值的范围:树中元素的值为float型,范围为1.2e-38至3.4e+38;树的名称为char类型数据,可以输入字母,数字和符号,但是长度必须在20位以内;对菜单进行操作时,输入数据长度必须在200以内,且有效的输入数据为0至7,其中0为退出程序,1至
2、7为对应菜单的操作选项。输出数据形式:输出到显示器。1.3程序功能创建平衡二叉树存储结构,通过平衡因子,使二叉排序树达到平衡,提供平衡二叉树的创建、查找和删除,树中元素的查找、插入和删除等基本功能,可以实现创建多棵平衡二叉树,并且能够进行两棵树的合并。通过平衡二叉树,能够使树时刻保持平衡,从而提高在树中遍历数据的速度,具有重要意义。1.4测试数据1//创建平衡二叉树2//输入创建树的个数t1//输入第一个树的名称5//输入第一个树中元素的个数52689//依次输入各个元素t2//输入第二个树的名称5//输入第二个树中元素的个数314107//依次输入各个元素
3、5//层次遍历输出第一个树的结构图t1//操作树名5//层次遍历输出第二个树的结构图t2//操作树名3//插入元素操作t1//操作树名1//插入元素个数7//依次插入元素5//层次遍历输出树的结构图t1//操作树名4//删除元素操作t2//操作树名1//删除元素个数7//依次删除元素5//层次遍历输出树的结构图t2//操作树名6//合并两个树操作t1t2//操作树名5//层次遍历输出树的结构图t1//操作树名2//查询元素操作t1//操作树名5//需要查询的元素(该元素树中存在)2//查询元素操作t1//操作树名11//需要查询的元素(该元素树中不存在)7/
4、/删除二叉平衡树操作t1//操作树名2//查询操作t1//操作树名(会提示该树不存在,说明删除树成功)0//退出程序1.概要设计2.1抽象数据类型需要定义一个树的结构类型,其中包含数据类型,它的左右孩子指针,以及平衡因子,平衡因子的取值为-1,0,1三种,分别对应树的右边高(RH),平衡(EH)和左边高(LH)三种情形,通过平衡因子的判别,来调整树的高度使其达到平衡;另外需要用到双向链表的数据结构,以及队列的数据结构。2.2主程序流程及各模块之间的调用关系1.详细设计3.1存储结构实现typedefstructType{//数据类型结构floatnum;}T
5、ype;/*平衡树结构声明*/typedefstructAVLTree{//二叉平衡树结构体声明intbf;//结点的平衡因子structTypedata;//结点数据structAVLTree*lchild,*rchild;//左右孩子}AVLTree,*AVL;/*队列结构声明*/typedefstructQNode{//队列AVLtree;structQNode*next;}QNode,*QP;typedefstruct{QPfron;QPrear;}LinkQ;/*双向链表结构声明*/typedefstructLNode{//链表AVLt;chart
6、ree_name[NAME_LENGTH];structLNode*prior,*next;}LNode,*Link;3.2负责模块的伪码算法(1)voidLeftBalance(AVL&t){//左部平衡化处理l=t->lchild;switch(l->bf){//检查T的左子树平衡度,并作相应的平衡处理caseLH://新节点插入在T的左孩子的左子树上,做单右旋处理调整平衡因子;R_Rotate(t);break;caseEH://deleteAVL需要,insertAVL用不着调整平衡因子;R_Rotate(t);break;caseRH://新插入节
7、点在T的左孩子的右子树上,做双旋处理lr=l->rchild;switch(lr->bf){caseLH:调整平衡因子;break;caseEH:调整平衡因子;break;caseRH:调整平衡因子;break;}调整平衡因子;L_Rotate(t->lchild);R_Rotate(t);}}(2)voidRightBalance(AVL&t){//右部平衡化处理r=t->rchild;switch(r->bf){caseRH://新节点插在T的右孩子的右子树上,要做单左旋处理调整平衡因子;L_Rotate(t);break;caseEH://delete
8、AVL需要,insertAVL用不着调整平衡因子;L
此文档下载收益归作者所有