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

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

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

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

4、除、插入等操作过程。3.并实现从键盘上输入一系列数据（整型），建立一棵平衡二叉树。4.任意插入或删除一个结点后判断是否为平衡二叉树。5将非平衡二叉树转换成平衡二叉树。6.按中序遍历输出这棵平衡二叉树。2.课程设计的要求用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车('n')为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历；计算二叉排序树T的平均查找长度,输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”；判断二叉排序树T是否为平衡二叉树；再用数列L,生成平衡二叉排序树BT:当插入

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

6、叉树BT的平均查找长度函数。我负责的是第一部分，二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3.它的左、右子树也分别为二叉排序树。以链表存储结构创建二叉排序树，以回车('n')为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历。中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则(1)中序遍历左子树（L）；(2)访问根结点（V）；(3)中序遍历右子树（R）。函数1：中序遍历二叉树中序遍历二叉树也采用递归函数的方式，

7、先访问左子树2i,然后访问根结点i,最后访问右子树2i+1.先向左走到底再层层返回，直至所有的结点都被访问完毕。（谢石林）函数2：平均查找长度计算二叉排序树的平均查询长度时，可采用类似中序遍历的递归方式，用s记录总查询长度，j记录每个结点的查询长度，s值初值为0，采用累加的方式最总得到总查询长度s，平均查询长度等于s/i（i为树中结点个数）。（吴进）函数3：查找删除二叉排序树函数输入元素x,查找二叉排序树T,若存在含x的结点,则删该结点,并作中序遍历(执行函数1)；否则输出信息“无x”。（张常勋）函数4：判断二叉排序树T是否为平衡二叉树，若不是则用数列L，生成平衡排序二叉树BT；最后调用函数6

8、 ，接着调用函数5.判断二叉排序树是否为平衡二叉树的函数也是采用递归函数的方式，分别判定以树中每个节点为根节点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树，则该树便不是平衡二叉树。函数5：在平衡二叉树BT上插入新元素，若发现当前的二叉排序树BT不是平衡二叉排序树，则立即将它转 换成新的平衡二叉排序树BT。三、详细设计1.课程设计总体思想1.生成二叉排序树：建立二叉排序树采用的是边查找边插入的方式。查找函数采用递归的方式进行查找。查找是按照二叉排序树的性质进行的，通过比较要插入元素的关键字与当前结点关键字的大小来决定我们是遍历当前结点的哪个子树。如果小于当前结点关键字

9、，则遍历它的左子树；大于当前结点关键字，则遍历它的右子树；等于当前关键字，则此元素不插入原树。我们按照这样的规律，一直向下遍历，知道它的子树为空，则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。2.中序遍历：对二叉排序树进行中序遍历采用递归函数的方式。在根节点不为空的情况下，先访问左子树，在访问根结点，最后访问右子树。3.平均查找长度：计算二叉排序树的平均查找长度，仍采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s，平均查找长度就等于s/j（i为树中结点的总个数）。4.删除结点：删除结点函数，采用边查找变删

10、除的方式。如果没有查找到，则不对树做任何的修改：如果查找到结点，则分四种情况分别进行讨论：（1）该结点左右子树均为空；（2）该结点仅左子树为空；（3）该结点仅右子树为空；（4）该结点左右子树都不为空；5用数列L，生成平衡的二叉排序树BT；当插入新元素之后，发现当前的二叉排序树BT不是平衡二叉排序树，则立即将它转换成新的平衡的二叉排序树BT。我所负责的模块函数定义如下 void TraverseOrderDSTable(BSTree DT, void(*Visit)(ElemType) /按中序遍历详细的程序代码如下：typedef struct BSTNode /二叉排序树类型 ElemTyp

11、e data; struct BSTNode *lchild, *rchild; BSTNode, *BSTree; Status InitDSTable(BSTree &DT) /构造一个空的动态BST查找表DT DT = NULL; return 1; void TraverseOrderDSTable(BSTree DT, void(*Visit)(ElemType) /按中序遍历对DT的每个结点调用函数Visit()一次且至多一次 if(DT) TraverseOrderDSTable (DT->lchild, Visit); Visit(DT->data); Tr

12、averseOrderDSTable (DT->rchild, Visit); 2.模块划分Main:主函数模块，在主函数中调用其他函数：（1）Status InsertBST(BSTree &T, ElemType e) /创建二叉排序树（2）void TraverseOrderDSTable(BSTree DT, void(*Visit)(ElemType) void TraverseOrderDSTable(AVLTree DT, void(*Visit)(ElemType) /中序遍历二叉排序树和平衡二叉排序树 （3）void asl() /计算平均长度 （4）BSTre

13、e 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, KeyType key)/查找并删除结点（5）Status InsertAVL(AVLTree &T, ElemType e, Status &taller) /创建平衡二叉排序树 void RightBalance(AVL

14、Tree &T)/对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 void LeftBalance(AVLTree &T) /对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转处理之前的右子树的根结点 AVLTree SearchAVL(AVLTree T, KeyType key)/衡二叉排序树中进行查找。3.流程图 四、程序的调试与运行结果说明主函数代码：void main() int num, i, select, t, *depth, max, flag; KeyType j; Status k; El

15、emType *r, *tempr, tempbst, tempavl; BSTree bst, p; AVLTree avl, q; do printf("请输入要输入的数据的总数，总数要大于0:"); scanf("%d",&num); if(num <=0) printf("n输入的总数要大于0，请重新输入："); while(num <=0); gl_count = num; r = (ElemType*)malloc(gl_count*(sizeof(ElemType); printf("请输入

16、生成二叉树的整型数据，前后数据用空格隔开：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) printf("n"); select = 0; flag = 0; InitDSTable(bst); for(i=0; i<gl_count; i+) InsertB

17、ST(bst, ri); printf("n按中序遍历该二叉排序树的结果如下：n"); TraverseOrderDSTable(bst, print); cout<<endl<<endl<<"以下是对二叉排序树的基本操作:"<<endl <<"1.查找一个节点"<<endl <<"2.插入一个节点"<<endl <<"3.删除一个节点"<<endl <<"

18、;4.判别二元查找树是否为平衡二叉树"<<endl <<"5.二叉树转换为平衡二叉树"<<endl <<"6.退出系统"<<endl; do if(flag = 6); printf("n请输入二叉排序树基本操作的选项："); scanf("%d", &select); switch(select) case 1:printf("请输入待查找的数据："); scanf("%d", &j);

19、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二叉排序树中存在此值："); print(p->data); elsetempr = (ElemTy

20、pe*)(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 = tempri.key; ri.order = tempri.order; ri.key = temp

21、bst.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); if(p)tempr = (ElemType*)(mall

22、oc(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 = tempri.order; t+; printf(&q

23、uot;二叉排序树中该数据已经删除。"); TraverseOrderDSTable(bst, print); else printf("需删除的数据不存在于二叉树中。"); break; case 4: depth = (int*)malloc(gl_count*(sizeof(int); BST_DepthDiff(bst, depth); max = depth0; for(i=1 ; i<gl_count; i+) if(max < depthi) max = depthi; if(max < 2) printf("n该二叉排序

24、树是平衡二叉树。"); 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("该二叉排序树转换成了平衡二叉树"); TraverseOrderDSTable(avl, print); flag = 6; break; case 6: break; default : printf("您输入的选项是错误的，请重新输入！"); break; while(select != 6); 初始提示输入节点数；输入数据用空格符隔开；随后系统会自动对数据