实验四平衡二叉树演示

《实验四平衡二叉树演示》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验四平衡二叉树演示班级:计算机1405组别：4姓名：刘诚阳学号:201437121・问题定义及需求分析1・1课题目的和任务问题描述：利用平衡二叉树设计动态查找表。实验要求：设计平衡二叉树的动态演示的模拟程序。1）采用平衡二叉树存储结构。2）完成平衡二叉树的创建、杳找、插入和删除的演示操作。3）可以考虑两棵平衡二叉树的合并。1・2数据形式输入数据形式：通过键盘输入数据输入值的范围:树中元素的值为float型，范围为1.2e-38至3.4e+38；树的名称为char类型数据，可以输入字母，数字和符号，但是长度必须在20位以内；对菜

2、单进行操作时，输入数据长度必须在200以内，且右效的输入数据为0至7,其中0为退出程序，1至7为对应菜单的操作选项。输出数据形式:输出到显示器。1.3程序功能创建平衡二叉树存储结构,通过平衡因子，使二叉排序树达到平衡，提供平衡二叉树的创建、查找和删除，树屮元素的查找、插入和删除等基本功能，可以实现创建多棵平衡二叉树，并且能够进行两棵树的合并。通过平衡二叉树，能够使树时刻保持平衡，从而提高在树中遍历数据的速度，具冇重要意义。1.4测试数据12tl552689t253141075〃创建平衡二叉树〃输入创建树的个数//输入第一个树的名

3、称//输入第一个树屮元素的个数〃依次输入各个元素//输入第二个树的名称//输入第二个树中元索的个数〃依次输入各个元素//层次遍丿力输出第一个树的结构图tl5t23tl175tl4t2175t26tlt25tl2tl52tl117tl2tl0//操作树名〃层次遍历输出笫二个树的结构图〃操作树名//插入元索操作〃操作树名//插入元素个数//依次插入元素//层次遍历输出树的结构图〃操作树名//删除元素操作//操作树名//删除元素个数//依次删除元素//层次遍历输出树的结构图〃操作树名〃合并两个树操作//操作树名//层次遍历输出树的结构

4、图//操作树名//查询元索操作〃操作树名〃需要查询的元素(该元素树屮存在)//查询元素操作//操作树名〃需要查询的元索(该元索树中不存在)//删除二叉平衡树操作//操作树名//查询操作〃操作树名(会提示该树不存在，说明删除树成功)〃退出程序2・概要设计2.1抽象数据类型需要定义一个树的结构类型，其中包含数据类型，它的左右孩子指针,以及平衡因子，平衡因子的取值为-1,0,1三利分别对应树的右边高(RH),平衡(EH)和左边高(LH)三种情形，通过平衡因子的判别，来调整树的高度使其达到平衡；另外需要用到双向链表的数据结构，以及队列的

5、数据结构。2.2主程序流程及各模块之间的调用关系73.详细设计2.1存储结构实现typedefstructType{//数据类型结构floatnum;JType;/*平衡树结构声明*/typedefstructAVLTree{//二叉平衡树结构体声明intbf;〃结点的平衡因子structTypedata;//结点数据structAVLTree*Ichild,*rchild;//左右孩子}AVLTree,*AVL;厂队列结构声明=7typedefstructQNode{〃队歹！JAVLtree;structQNode*next;

6、}QNode,*QP;typedefstruct{QPfron;QPrear;}LinkQ;/*双向链表结构声明=7typedefstructLNode{〃链表AVLt;chartree_name[NAME_LENGTH];structLNode*prior;*next;}LNode,*Link;2.2负责模块的伪码算法(1)voidLeftBalancc(AVL&t){//左部平衡化处理l=t->lchild;switch(l~>bf){//检查T的左子树平衡度，并作相应的平衡处理caseLI1://新节点插入在T的左孩子的左

7、子树上，做单右旋处理调整平衡因子;R.Rotate(t);break;caseEH://deleteAVL需要，insertAVL用不着调整平衡因了；R_Rotate(t);break;caseRH://新插入节点在T的左孩子的右子树上，做双旋处理lr=l->rchild;switch(lr->bf){caseLH:调整平衡因子;break;caseEH:调整平衡因子;break;caseRH:调整平衡因子;break;}调整平衡因了；L_Rotate(t->lchild);RRotate(t);}}(1)voidRightBa

8、lance(AVL&t){//右部平衡化处理r=t->rchild;switch(r->bf){caseRH://新节点插在T的右孩子的右子树上，要做单左旋处理调整平衡因了;L_Rotatc(t);break;caseEH://deleteAVL需要，inser