《数据结构二叉排序树课程设计报告.pdf》由会员分享，可在线阅读，更多相关《数据结构二叉排序树课程设计报告.pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 欢迎下载 课 程 设 计 报 告 数据结构 题目：二叉排序树 姓 名：学 号：专 业：班 级：指导老师：年 月 日 欢迎下载 目 录 一、课程设计简介.3 二、原理分析及流程.3 2.1、原理分析.3 2.2、流程图.4 1、main()函数.4 2、创建.4 3、插入.5 4、查找.6 5、中序遍历输出.7 三、算法描述.8 3.1、存储结构.8 3.2、插入算法.8 3.3、查找算法.9 3.4、删除算法.10 四、小结与体会.12 五、程序执行过程.13 5.1、创建二叉排序树并中序输出.13 5.2、插入并中序输出.13 5.3、查找.14 六、程序清单.14 欢迎下载 一、课程设计
2、简介 1.1、题目：二叉排序树相关操作 1、创建二叉排序树；2、插入给定值；3、查找给定值；4、删除给定值的结点。1.2、报告要求：1、封面;2、题目与流程图或模块图;3、程序清单和运行结果;4、小结(收获和体会);5、装订成册。1.3、目的：课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。二、原理分析及流程 2.1、原理分析：根据题目要求，要实现这些功能，就必须创建一个菜单。这个菜单设置在 main（）函数里面，然后使用while().switch()语句进行循环调用相关函数，以
3、达到实现相关功能的目的。欢迎下载 2.2、流程图：1、main（）函数：2、创建：3、插入：选择操作 main()开始 选择 1 创建 选择 2 插入 选择 3 查找 选择 4 删除 选择 5 退出 Create(&t)输入结点值，以-1 结束 调用插入函数 欢迎下载 N Y N Y 4、查找：Insert(&t,x)输入给定的结点值*t=null xkey insert(&(*t)-lchild)insert(&(*t)-rchild)*t=s 结束 欢迎下载 Y N Y N 5、中序遍历输出：返回search(p-rchild,x)输入给定的结点值 x,p=t P!=null xkey 返
4、回search(p-lchild,x)返回 null search(t,x)返回p-key x=p-key display(t)欢迎下载 三、算法描述 3.1、存储结构 定义一个链表式的二叉排序树，用链表的方式构造结点，存储二叉排序树中的结点、结点类型和指针类型如下：#include 欢迎下载#define null 0 typedef int keytype;typedef struct node keytype key;struct node*lchild,*rchild;bstnode,*bstree;3.2、插入算法 在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经
5、存在。若二叉排序树中不存在关键字等于 x 的节点，则插入。将一个关键字值为 x 的节点 s 插入到二叉排序树中，可以用下面的方法：（1）若二叉排序树为空，则关键字为 x 的节点 s 成为二叉排序树的根 （2）若二叉排序树非空，则将 x 与二叉排序树根进行比较，如果 x 的值等于根节点关键值，则停止插入；如果 x 的根节点值小于根节点关键值，则将 x 插入左子树；如果 x 的值大于根节点关键字的值，则将 x 插入右子树。在左右两个子树的插入方法与整个二叉排序树相同。算法如下：void insert(bstree*t,keytype x)bstree s;if(*t=null)s=(bstree)
6、malloc(sizeof(bstnode);s-key=x;s-lchild=null;欢迎下载 s-rchild=null;*t=s;else if(xkey)insert(&(*t)-lchild),x);else if(x(*t)-key)insert(&(*t)-rchild),x);3.3、查找算法 （1）若二叉排序树不为空，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则查找不成功。（2）否则，查找失败，返回 null。算法如下：
7、bstree search(bstree t,keytype x)bstree p;p=t;if(p!=null)if(x=p-key)return p-key;else if(xkey)return search(p-lchild,x);else return search(p-rchild,x);else printf(%d can not be foundn,x);return null;欢迎下载 3.4、删除算法 在二叉排序树中删除节点，首先要确定被删除的节点是否在二叉排序树中。若不在，则不做任何操作；否则，假设要删除的节点为 p，节点 p 的父节点为 r，并假设 p 是 r 的左孩子
8、。根据被删除节点 p有无孩子，删除部分可做以下 3 中情况讨论：（1）若 p 为叶子节点，则可令其父节点 r 的左孩子指针域为空，直接将其删除。（2）若 p 节点只有右子树或左子树，则可以将 p 的左子树或右子树直接改为其双亲节点 r 的左子树。（3）若 p 既有左子树又有右子树；将节点 s 为 p 的中序前驱。首先找到 p 的中序前驱节点 s，然后用节点 s 的值代替节点p 的值，再将节点 s 删除，节点 s 的原左子树改为 s 的双亲节点 q的右子树。算法如下：bstree delete(bstree t,keytype x)bstree p,q,r,s;p=t;r=null;while(
9、p)if(x=p-key)break;r=p;if(xkey)p=p-lchild;else p=p-rchild;if(p=null)printf(%d is not exist!n,x);return t;欢迎下载 if(p-lchild=null)|(p-rchild=null)if(r=null)if(p-lchild=null)t=p-rchild;else t=p-lchild;else if(p-lchild=null)if(r-lchild=p)r-lchild=p-rchild;else r-rchild=p-rchild;else if(r-lchild=p)r-lchil
10、d=p-lchild;else r-lchild=p-lchild;free(p);else q=p;s-lchild;while(s-rchild)q=s;s-rchild;if(q=p)q-lchild=s-lchild;else p-key=s-key;free(s);return t;四、小结与体会 经过一个多星期来夜以继日的努力，终于把课程设计二叉排序树的相关算法全部完成！在编写程序过程中，让我对二叉排序树的创建、插入、查找、删除算法有了较系统的认识，也发现了一些以前纸上谈兵时的思想误区。比如实现插入功能时，从根节点开始比较；当实现删除功能时，如果待删除结点 p 左、右 欢迎下载 子
11、树齐全，首先找到 p 的中序前驱节点 s（p 的中序前驱），然后用节点 s 的值代替节点 p 的值，再将节点 s 删除，节点 s 的原左子树改为 s 的双亲节点 q 的右子树。实现中序遍历功能时，采用递归思想.这是第一次关于编写程序的课程设计。虽然上机安排只有两天时间，可却并不像平时上机实验一样，离开了机房就不用再对着电脑屏幕编写代码，更多的工作实在离开机房后完成的。一遍一遍地按 F9 调试程序，error 从几十个减少到几个，再到只剩几个warring，当按下 Ctrl+F9，那精心设计的“菜单”出现在屏幕上时，那一刻的心情无以言表！涌上心头的除了自豪感、成就感之外，还有对编程工作之辛苦的慨
12、叹！因为自己专业将来的方向与这有关，不免让我考虑起毕业后的发展方向。如果朝这方面发展的话，我是否可以胜任这样的工作？如果不是，又该选择什么？欢迎下载 五、程序执行过程 5.1、创建二叉排序树并中序输出 5.2 插入并中序输出 欢迎下载 5.3、查找 5.4、删除并中序输出 六、程序清单#include#define null 0 typedef int keytype;typedef struct node keytype key;struct node*lchild,*rchild;bstnode,*bstree;欢迎下载 void insert(bstree*t,keytype x);bs
13、tree search(bstree t,keytype x);void display(bstree t);void create(bstree*t)keytype x;*t=null;scanf(%d,&x);while(x!=-1)insert(t,x);scanf(%d,&x);void insert(bstree*t,keytype x)bstree s;if(*t=null)s=(bstree)malloc(sizeof(bstnode);s-key=x;s-lchild=null;s-rchild=null;*t=s;else if(xkey)insert(&(*t)-lchil
14、d),x);else if(x(*t)-key)insert(&(*t)-rchild),x);bstree search(bstree t,keytype x)bstree p;p=t;if(p!=null)if(x=p-key)return p-key;else if(xkey)return search(p-lchild,x);else return search(p-rchild,x);else printf(%d can not be foundn,x);return null;欢迎下载 bstree delete(bstree t,keytype x)bstree p,q,r,s;
15、p=t;r=null;while(p)if(x=p-key)break;r=p;if(xkey)p=p-lchild;else p=p-rchild;if(p=null)printf(%d is not exist!n,x);return t;if(p-lchild=null)|(p-rchild=null)if(r=null)if(p-lchild=null)t=p-rchild;else t=p-lchild;else if(p-lchild=null)if(r-lchild=p)r-lchild=p-rchild;else r-rchild=p-rchild;else if(r-lchi
16、ld=p)r-lchild=p-lchild;else r-lchild=p-lchild;free(p);else q=p;s-lchild;while(s-rchild)q=s;s-rchild;if(q=p)q-lchild=s-lchild;else p-key=s-key;free(s);欢迎下载 return t;void display(bstree t)if(t!=null)display(t-lchild);printf(%5d,t-key);display(t-rchild);void main(void)bstree t,b;int i=1,j;keytype x;whi
17、le(i)printf(n*n);printf(n*MENU OF BSTREE *n);printf(n*1.create 2.insert *n);printf(n*3.search 4.delete *n);printf(n*5.exit *n);printf(n*n);printf(what do you want to do?:);scanf(%d,&j);switch(j)case 1:printf(input bstrees values,end with-1:n);create(&t);printf(bstrees root is%dn,t-key);display(t);break;case 2:printf(input the insert value:);scanf(%d,&x);insert(&t,x);display(t);break;case 3:printf(input the search value:);scanf(%d,&x);printf(result is:%d,search(t,x);break;case 4:printf(input the delete value:);scanf(%d,&x);delete(t,x);display(t);break;case 5:i=0;break;clrscr();