2022年二叉排序树运算-数据结构与算法课程设计报告_l.pdf

《2022年二叉排序树运算-数据结构与算法课程设计报告_l.pdf》由会员分享，可在线阅读，更多相关《2022年二叉排序树运算-数据结构与算法课程设计报告_l.pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、合肥学院计算机科学与技术系课程设计报告2009 2010 学年第二 学期课程数 据 结 构 与算法课 程 设 计名称二叉排序树运算学 生 姓 名顾成方学号03专 业 班 级08 计科 (2)指 导 教 师王昆仑张贯虹2010 年 5 月精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 16 页 - - - - - - - - - - 题目： （二叉排序树运算问题）设计程序完成如下要求： 对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。基本任务：选择合适的储存结构构造二叉排序树；对二

2、叉排序树T 作中序遍历，输出结果；在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。尽量给出“顺序和链式”两种不同结构下的操作，并比较。一、问题分析和任务定义本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历， 然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。实现本程序需要解决以下几个问题：1、 如何构造二叉排序树。2、 如何通过中序遍历输出二叉排序树。3、 如何实现多种查找。4、 如何实现插入删除等操作。二叉排序树的定义：精品资料 - - - 欢迎下载 - - - - - - -

3、 - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 16 页 - - - - - - - - - - 其左子树非空，则左子树上所有结点的值均小于根结点的值。若其右子树非空，则右子树上所有结点的值大于根结点的值。其左右子树也分别为二叉排序树。本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新

4、的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 16 页 - - - - - - - - - - 的方法。删除操作要分几种情况讨论，在后面有介绍。二、概要设计和数据结构选择用二叉链表作为二叉排序树的存储结

5、构，其中 key 为结点关键值， *lchlid、*rchild分别为左右孩子指针。该程序的结构如下图所示：三、详细设计和编码首先定义二叉排序树的数据类型如下：typedef struct nodeMain()先建立一棵二叉排序树，并输出其中序排序后的序列二 叉 排 序二 叉 排 序二叉排序二叉排序非递归查找递归查找精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 16 页 - - - - - - - - - - int key;452453122890452453122890精品资料 - -

6、- 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 16 页 - - - - - - - - - - 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 16 页 - - - - - - - - - - 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 16 页 - - - - - - - - - - 452453122

7、8901345245312289013451353122890451353122890精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 16 页 - - - - - - - - - - 红. 数据结构与算法. 北京：中国铁道出版社，(2) 王昆仑 . 李红 . 数据结构与算法试验指导， 2009精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 16 页 - - - - - - - - - - (3

8、) 谭浩强 .c 程序设计 . 北京：清华大学出版社，(4) 严蔚敏 . 数据结构：语言版. 北京：清华大学出版社， 2002(5) 耿国华 . 等. 数据结构 : 用 c 语言描述 . 北京：高等教育出版社，2004精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 16 页 - - - - - - - - - - 八、附录#include #include #include #define endflag 0叉排序树 -查找n); printf(ttt 2. 二叉排序树 -插入 n); pr

9、intf(ttt 3. 二叉排序树-删除 n); printf(ttt 4. 二叉排序树-显示 n); printf(ttt 0. 退出该程序 n);printf(ttt n);printf(ttt n); printf(ttt*n); printf(nnn); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 16 页 - - - - - - - - - - doif(flag=0)printf(!您的输入有误 , 请重新输入n); printf(请选择您要进行的项目:); scanf(%d

10、,&choice); flag=0;while(choice4);return choice;法 1-递归查找 n); printf(ttt 2. 方法 2-非递归查找 n);printf(ttt n);printf(ttt n);printf(ttt*n); printf(nnn);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 16 页 - - - - - - - - - - doif(flag=0)printf(!您的输入有误 , 请重新输入n); printf(请选择查找方法 :);

11、 scanf(%d,&choice);flag=0;while(choice!=1&choice!=2);return choice;/ 主函数void main()int i,j,k;Bstnode *tree,*p; system(cls);printf( 请先建立一棵二叉排序树nn);printf(输入其结点信息 ( 输入一组正整数, 当输入 0 时结束 ):n);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 16 页 - - - - - - - - - - tree=CreateB

12、ST(); printf(中序遍历的二叉排序树:n);Inorder(tree); printf(二叉排序树的根为:%dn,tree-key); for(;)switch(i=mainmenu()case 0:exit(0);case 1:switch(j=searchmenu() case 1:search_Bitree(tree);break; case 2:printf(n请输入要查找的结点的值 :);scanf(%d,&k);p=searchBST(tree,k); printf(n); break; /default:printf(输入有误 !); break;精品资料 - - -

13、欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 16 页 - - - - - - - - - - case 2:tree=insert_Bitree(tree);break;case 3:tree=delete_Bitree(tree);break; case 4:printf(n); printf(二叉排序树的根为:%dn,tree-key); printf(中序遍历后的序列为:n); print_Bitree(tree); printf(中序遍历的二叉排序树:n); Inorder(tree); printf(n); break; /default:printf(输入有误 !);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 16 页 - - - - - - - - - - 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 16 页，共 16 页 - - - - - - - - - -