二叉排序树与平衡二叉排序树基本操作的实现

1、编 号：B04900083学 号：201440410208HUBEI POLYTECHNIC UNIVERSITY课程设计教学院计算机学院课程名称数据结构与算法题专班姓二叉排序树与平衡二叉排序树基本操目 作的实现业计算机科学与技术级 二班名同组人员指导教师成俊2015年 12月 27 日vtfl /理工学茂课程设计（论文）课程设计任务书20152016 学年 第1学期学生姓名： 专业班级：计科二指导教师：成俊工作部门： 计算机学院一、课程设计题目：二叉排序树与平衡二叉排序树基本操作二、课程设计内容用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车('n')为输入结

2、束标志，输入数列L,生成二叉排序树T;对二叉排序树T作中序 遍历；计算二叉排序树T的平均，输出结果；输入元素x,查找二叉排序树T,若 存在含x的结点,则删除该结点,并作中序遍历；否则输出信息“无结点 x” ；判断二叉排序树T是否为平衡二叉树；再用数列L,生成平衡二叉排序树BT: 当插入新元素之后，发现当前的二叉排序树 BT不是平衡二叉排序树，则立即将 它转换成新的平衡二叉排序树 BT;计算平衡的二叉排序树BT的平均查找长度， 输出结果。三、进度安排1 .分析问题，给出数学模型，选择数据结构2 .设计算法，给出算法描述3 .给出源程序清单4 .编辑、编译、调试源程序5 .撰写课程设计报告四、基本

3、要求编写AVL树判别程序，并判别一个二叉排序树是否为 AVL树。二叉排序树 用其先序遍历结果表示，如：5, 2, 1, 3, 7, 8。实现AVL树的ADT包括其上的基本操作：结点的加入和删除；另外包括 将一般二叉排序树转变为AVL树的操作。实现提示主要考虑树的旋转操作。目录一、课程设计题目：二叉排序树与平衡二叉排序树基本操作1二、课程设计内容 1三、进度安排 1四、基本要求 1一、概述 31 .课程设计的目的 32 .课程设计的要求 3二、总体方案设计 4三、详细设计 61 .课程设计总体思想 62 .模块划分 73 .流程图 8四、程序的调试与运行结果说明 9五、课程设计总结 14参考文献

4、 14、概述1.课程设计的目的1 .充分理解和掌握二叉树、平衡二叉树的相关概念和知识。2 .掌握排序二叉树的生成、结点删除、插入等操作过程。3 .并实现从键盘上输入一系列数据（整型），建立一棵平衡二叉树。4 .任意插入或删除一个结点后判断是否为平衡二叉树。5 .将非平衡二叉树转换成平衡二叉树。6 .按中序遍历输出这棵平衡二叉树。7 .课程设计的要求用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车（'n'）为输入结束标志，输入数列L,生成二叉排序树T;对二叉排序树T作中序遍 历;计算二叉排序树T的平均查找长度，输出结果；输入元素x,查找二叉排序树 T,若存在含x的

5、结点，则删除该结点，并作中序遍历；否则输出信息“无结点 x”;判断二叉排序树 T是否为平衡二叉树；再用数列 L,生成平衡二叉排序树 BT:当插入新元素之后，发现当前的二叉排序树 BT不是平衡二叉排序树，则立即 将它转换成新的平衡二叉排序树 BT ;计算平衡的二叉排序树BT的平均查找长 度，输出结果。编写AVL树判别程序，并判别一个二叉排序树是否为 AVL树。二叉排序树用 其先序遍历结果表示，如：5, 2, 1, 3, 7, 8。实现AVL树白ADT,包括其上的基本操作：结点的加入和删除；另外包括将一般二叉排序树转变为AVL树的操作。实现提示主要考虑树的旋转操作。、总体方案设计1）建立二叉排序树

6、，编写二叉排序树 T作中序遍历。2）查找删除二叉排序树函数。3）编写判断二叉排序树T是否为平衡二叉树函数，把非平衡二叉排序树转 换成平衡二叉排序树。4）编写计算二叉树BT的平均查找长度函数。我负责的是第一部分，二叉排序树或者是一棵空树，或者是具有下列性质的二 叉树：1 .若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2 .若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3 .它的左、右子树也分别为二叉排序树。以链表存储结构创建二叉排序树，以回车（'n'）为输入结束标志，输入数列L, 生成二叉排序树T;对二叉排序树T作中序遍历。中序遍历二叉树算法的框

7、架是：若二叉树为空，则空操作；否则（1）中序遍历左子树（L）;访问根结点（V）;（3）中序遍历右子树（R）。函数1:中序遍历二叉树中序遍历二叉树也采用递归函数的方式，先访问左子树2i,然后访问根结点i,最后访问右子树2i+1.先向左走到底再层层返回，直至所有的结点都被访问完 毕。（谢石林）函数2:平均查找长度计算二叉排序树的平均查询长度时，可采用类似中序遍历的递归方式，用 s记 录总查询长度，j记录每个结点的查询长度，s值初值为0,采用累加的方式最 总得到总查询长度s,平均查询长度等于s/i （i为树中结点个数）。（吴进）函数3:查找删除二叉排序树函数输入元素x,查找二叉排序树T,若存在含x的

8、结点，则删该结点，并作中序遍历 （执行函数1）;否则输出信息“无x”。（张常勋）函数4:判断二叉排序树T是否为平衡二叉树，若不是则用数列 L, 生成平衡排序二叉树BT;最后调用函数6 ,接着调用函数5.判断二叉排序树 是否为平衡二叉树的函数也是采用递归函数的方式，分别判定以树中每个节点为根节点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树，则该树 便不是平衡二叉树。函数5:在平衡二叉树BT上插入新元素，若发现当前的二叉排序树 BT不是平 衡二叉排序树，则立即将它转换成新的平衡二叉排序树BT。4两I "4N察他课程设计(论文)三、详细设计1.课程设计总体思想1 .生成二叉排序树：

9、建立二叉排序树采用的是边查找边插入的方式。查找函数采用递归的方式 进行查找。查找是按照二叉排序树的性质进行的，通过比较要插入元素的关键 字与当前结点关键字的大小来决定我们是遍历当前结点的哪个子树。如果小于 当前结点关键字，则遍历它的左子树；大于当前结点关键字，则遍历它的右子 树；等于当前关键字，则此元素不插入原树。我们按照这样的规律，一直向下 遍历，知道它的子树为空，则返回当前结点的上一个结点。然后利用插入函数 将该元素插入原树。2 .中序遍历：对二叉排序树进行中序遍历采用递归函数的方式。在根节点不为空的情况 下，先访问左子树，在访问根结点，最后访问右子树。3 .平均查找长度：计算二叉排序树的

10、平均查找长度，仍采用类似中序遍历的递归方式，用 s 记录总查找长度，j记录每个结点的查找长度，s置初值为0,采用累加的方式 最终得到总查找长度s,平均查找长度就等于s/j (i为树中结点的总个数)。4 .删除结点：删除结点函数，采用边查找变删除的方式。如果没有查找到，则不对树做 任何的修改：如果查找到结点，则分四种情况分别进行讨论：(1)该结点左右子树均为空；(2)该结点仅左子树为空；(3)该结点仅右子树为空；(4)该结点左右子树都不为空；5.用数列L,生成平衡的二叉排序树BT;当插入新元素之后，发现当前的二叉 排序树BT不是平衡二叉排序树，则立即将它转换成新的平衡的二叉排序树 BT。 我所负

11、责的模块函数定义如下void TraverseOrderDSTable(BSTree DT, void(*Visit)(ElemType) 按中序 遍历详细的程序代码如下：typedef struct BSTNode /二叉排序树类型 ElemType data;struct BSTNode *lchild, *rchild;BSTNode, *BSTree;Status InitDSTable(BSTree &DT)构造一个空的动态 BST查找表DTDT = NULL;return 1;void TraverseOrderDSTable(BSTree DT, void(*Visit)

12、(ElemType)按中序遍历对DT的每个结点调用函数 Visit() 一次且至多一次if(DT) TraverseOrderDSTable (DT->lchild, Visit);Visit(DT->data);TraverseOrderDSTable (DT->rchild, Visit);2 .模块划分Main:主函数模块，在主函数中调用其他函数：(1) Status InsertBST(BSTree &T, ElemType e) /创建二叉排序树(2) void TraverseOrderDSTable(BSTree DT, void(*Visit)(Ele

13、mType) void TraverseOrderDSTable(AVLTree DT, void(*Visit)(ElemType) /中序遍历二叉排序树和平衡二叉排序树(3) void asl() /计算平均长度(4) BSTree SearchBST(BSTree T, KeyType key)void SearchBST(BSTree &T, KeyType key, BSTree f, BSTree &p, Status &flag)void Delete(BSTree &p)Status DeleteBST(BSTree &T, KeyTyp

14、e key)/查找并删除结点(5) Status InsertAVL(AVLTree &T, ElemType e, Status &taller) /创建平衡二叉排序树void RightBalance(AVLTree &T)/对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点void LeftBalance(AVLTree &T) /对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转处理之前的右子树的根结点6vtfl /理工学茂课程设计（论文）衡二叉排序树中进行查AVLTree SearchAV

15、L(AVLTree T, KeyType key)/找。3 .流程图四、程序的调试与运行结果说明主函数代码：void main()int num, i, select, t, *depth, max, flag;KeyType j; Status k;ElemType *r, *tempr, tempbst, tempavl;BSTree bst, p;AVLTree avl, q; do printf("请输入要输入的数据的总数，总数要大于0:");scanf("%d”,&num); if(num <=0)printf("n输入的总数要大

16、于0,请重新输入：”)；while(num <=0);gl_count = num;r = (ElemType*)malloc(gl_count*(sizeof(ElemType);printf("请输入生成二叉树的整型数据，前后数据用空格隔开：n");for(i=0; i<gl_count; i+)scanf("%d”, &ri.key) ;ri.order = i+1;printf("n用户输入的数据及序号如下：n");for(i=0; i< gl_count; i+)print(ri);if(i+1)%6 = 0

17、) printf("n");select = 0; flag = 0; InitDSTable(bst);for(i=0; i<gl_count; i+) InsertBST(bst, ri);printf("n按中序遍历该二叉排序树的结果如下：n");TraverseOrderDSTable(bst, print);cout<<endl<<endl<<”以下是对二叉排序树的基本操作："<<endl<<"1.查找一个节点"<<endl<<

18、;"2.插入一个节点"<<endl<<"3.删除一个节点"<<endl<<"4.判别二元查找树是否为平衡二叉树"<<endl<<"5.二叉树转换为平衡二叉树"<<endl<<"6.退出系统"<<endl;doif(flag = 6);printf("n请输入二叉排序树基本操作的选项：”)；scanf("%d”, &select);switch(select)ca

19、se 1:printf("请输入待查找的数据：")；scanf("%d", &j);p = SearchBST(bst, j);if(p)printf("n二叉排序树中存在此值：");print(p->data);else printf("n二叉排序树中不存在此值。");break;case 2:printf("请输入需插入的数据：")；scanf("%d", &j);p = SearchBST(bst, j);if(p)printf("n二叉

20、排序树中存在此值：");print(p->data);elsetempr(ElemType*)(malloc(gl_count*sizeof(ElemType);for(i=0; i < gl_count; i+)tempri.key = ri.key; tempri.order = ri.order;tempbst.key = j; tempbst.order = +gl_count;r = (ElemType*)(malloc(gl_count*sizeof(ElemType);for(i=0; i < gl_count-1; i+)ri.key = tempr

21、i.key; ri.order = tempri.order;ri.key = tempbst.key; ri.order = tempbst.order;InsertBST(bst, tempbst); printf("数据已经插入二叉排序树中。)printf("n按中序遍历该二叉排序树的结果如下：n");TraverseOrderDSTable(bst, print); break;case 3: printf("请输入需删除的数据：");scanf("%d", &j);p = SearchBST(bst, j)

22、;if(p)tempr (ElemType*)(malloc(gl_count*sizeof(ElemType);for(i=0; i < gl_count; i+) tempri.key = ri.key; tempri.order = ri.order; DeleteBST(bst, j); gl_count-;r = (ElemType*)(malloc(gl_count*sizeof(ElemType);for(i=0, t=0; i < gl_count; i+)if(tempri.key != j) rt.key = tempri.key;rt.order = temp

23、ri.order; t+;printf("二叉排序树中该数据已经删除。");TraverseOrderDSTable(bst, print);else printf("需删除的数据不存在于二叉树中。")；break;case 4: depth = (int*)malloc(gl_count*(sizeof(int);10vtfl /理工学茂课程设计(论文)BST_DepthDiff(bst, depth); max = depth0;for(i=1 ; i<gl_count; i+)if(max < depthi) max = depthi;

24、if(max < 2) printf("n该二叉排序树是平衡二叉树。");else printf("n该二叉排序树不是平衡二叉树。");if(max > 4)printf("n该二叉排序树有结点的左右子树之差大于4,系统建议您将该二叉排序树转换成平衡二叉树。");break;case 5: InitDSTable(avl);for(i =0; i < gl_count; i+)InsertAVL(avl, ri, k);printf("该二叉排序树转换成了平衡二叉树");TraverseOrder

25、DSTable(avl, print);flag = 6; break;case 6: break;default : printf("您输入的选项是错误的，请重新输入！)break;while(select != 6);初始提示输入节点数;输入数据用空格符隔开;请丽人生质二义阴的要型数据.期后叙据用三格府升1 14 S & 12 15 21 23 3& 9 10随后系统会自动对数据进行中序遍历；用户稀人的数据及序号如不：<14.IX5.2><G,3><12.4(15.GX21,6><2"7><%,Q*9

26、><10)按中序遍历该二叉排序树的结果如下；<£*2><6*9*»><1瓦10><12t4X14.IX15.SX 21,(><23*7>< 沟 8>功能菜单;12dj松序平树 为叉 否二 日南 树平排点点点我为 叉节节-睿换 二-元襄 对二一二WH 日拆人除别叉出 下查ijggS二退 JA - - - - - - c j 2 3 4 5 6vtfl 山穴N孝茂课程设计（论文）执行节点的查找功能;眄磊翻勰I本鼾的选项” L叉排序期中存在此值匕（一”一c14树基历该二叉排 2><6执行插入功能;人入已序< 捋花由请执行删除功能;判断是