大数据结构二叉排序树课程设计报告材料

1、课程设计报告数据结构题目：二叉排序树姓名:学号:专业:班级:指导老师：年 月曰目录一、课程设计简介 3二、 原理分析及流程 32.1、原理分析32.2、流程图41、main()函数42、创建43、插入54、查找65、中序遍历输出7三、 算法描述83.1、存储结构83.2、插入算法 83.3、查找算法93.4、删除算法10四、小结与体会 12五、程序执行过程135.1、创建二叉排序树并中序输出 135.2、插入并中序输出 135.3、查找14六、程序清单 144、课程设计简介1.1、题目：二叉排序树相关操作1、创建二叉排序树;2、插入给定值;3、查找给定值;4、删除给定值的结点。1.2、报告要求

2、:1、封面;2、题目与流程图或模块图3、程序清单和运行结果；4、小结(收获和体会);5、装订成册。1.3、目的：课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。二、原理分析及流程2.1、原理分析：根据题目要求，要实现这些功能，就必须创建一个菜 单。这个菜单设置在 main ()函数里面，然后使用 while()switch(语句进行循环调用相关函数，以达到实现 相关功能的目的。22、流程图:1、main ()函数:main()开始选择操作r选择17选择2（创建丿2、创建:选择3（插

3、入丿I查找选择4选择5I删除丿reate(&t)调用插入函数输入结点值，以-1结束3、插入:4、查找:search(t,x)输入给定的结点值x,p=tJP!=nullNVx=p-key返回nullxkey返回p-key返回返回search(p-search(p-lchild,x)rchild,x)丿VYV N5、中序遍历输出:display(t)三、算法描述3.1、存储结构定义一个链表式的二叉排序树，用链表的方式构造结点，存储二叉排序树中的结点、结点类型和指针类型如下：#i nclude #defi ne null 0typedef int keytype;typedef struct nod

4、ekeytype key;struct node *lchild,*rchild;bst no de,*bstree;3.2、插入算法在二叉排序树中插入一个新节点，首先要查找该节点在二叉 排序树中是否已经存在。若二叉排序树中不存在关键字等于x的节点，贝y插入。将一个关键字值为x的节点s插入到二叉排序树中，可以用 下面的方法：(1) 若二叉排序树为空，则关键字为x的节点s成为二叉排 序树的根(2) 若二叉排序树非空，则将x与二叉排序树根进行比较， 如果x的值等于根节点关键值，则停止插入；如果x的根节点值 小于根节点关键值，则将x插入左子树；如果x的值大于根节点 关键字的值，则将x插入右子树。在左

5、右两个子树的插入方法与 整个二叉排序树相同。算法如下：void in sert(bstree *t,keytype x)bstree s;if(*t=null)s=(bstree)malloc(sizeof(bst no de);s_key=x;s-lchild=n ull;s-rchild=nu II;*t=s;else if(xkey)in sert(&(*t)-lchild),x);else if(x(*t)-key)in sert(&(*t)-rchild),x);3.3、查找算法(1)若二叉排序树不为空，将根结点的关键字与待查关键字 进行比较，若相等，则查找成功；若根节点关键字大于待

6、查值， 则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在 查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节 点，则查找不成功。(2)否则，查找失败，返回null。算法如下：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 prin tf(%d can not be foundn ,x);retur n n ull;3

7、.4、删除算法在二叉排序树中删除节点，首先要确定被删除的节点是否在 二叉排序树中。若不在，则不做任何操作；否则，假设要删除的节点为p，节点p的父节点为r，并假设p是r的左孩子。根据被删除节点p 有无孩子，删除部分可做以下 3中情况讨论：(1) 若p为叶子节点，则可令其父节点r的左孩子指针域 为空，直接将其删除。(2) 若p节点只有右子树或左子树，则可以将p的左子树 或右子树直接改为其双亲节点 r的左子树。(3) 若p既有左子树又有右子树；将节点 s为p的中序前 驱。首先找到p的中序前驱节点S,然后用节点s的值代替节点 p的值，再将节点s删除，节点s的原左子树改为s的双亲节点q 的右子树。算法如

8、下：bstree delete(bstree t,keytype x)bstree p,q,r,s;p=t；r=n ull;while(p)if(x=p-key) break;r=p;if(xkey) p=p-lchild;elsep=p-rchild;if(p=nu II)pri ntf(%d is not exist!n,x);retur n t;if(p-lchild=n ull)|(p-rchild=n ull) if(r=n ull)if(p-lchild=n ull) t=p-rchild;else t=p-lchild;else if(p-lchild=n ull) if(r-l

9、child=p) r-lchild=p-rchild;else r-rchild=p-rchild; else if(r-lchild=p) r-lchild=p-lchild;else r-lchild=p-lchild; free(p);elseq=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;四、小结与体会经过一个多星期来夜以继日的努力，终于把课程设计一一二叉排序树的相关算法全部完成！ 在编写程序过程中，让我对二叉 排序树的创建、插

10、入、查找、删除算法有了较系统的认识，也发 现了一些以前纸上谈兵时的思想误区。比如实现插入功能时，从根节点开始比较；当实现删除功能时，如果待删除结点p左、右 子树齐全，首先找到p的中序前驱节点s （p的中序前驱），然后 用节点s的值代替节点p的值，再将节点s删除，节点s的原左 子树改为s的双亲节点q的右子树。实现中序遍历功能时，采用 递归思想这是第一次关于编写程序的课程设计。虽然上机安排只有两天 时间，可却并不像平时上机实验一样，离开了机房就不用再对着 电脑屏幕编写代码，更多的工作实在离开机房后完成的。一遍一遍地按F9调试程序，error从几十个减少到几个，再到只剩几个 warring，当按下C

11、trl+F9，那精心设计的“菜单”出现在屏幕上 时，那一刻的心情无以言表！涌上心头的除了自豪感、成就感之 外，还有对编程工作之辛苦的慨叹！因为自己专业将来的方向与这有关，不免让我考虑起毕业后的发展方向。如果朝这方面发展的话，我是否可以胜任这样的工作？如果不是，又该选择什么？五、程序执行过程5.1、创建二叉排序树并中序输出what do you want to do? :1input bstree s values,end with -1: 4625786212377029Hlbstree!s root is 4612252937466270785.2插入并中序输出* MENU OF BSTRE

12、E* 1.create2-insert* 3.search4.delete* 5exit*Mr 赞 賛* 赫轄 鸞 簧 黑 欝 鸞 欝黔 鸞 欝what do you want to do? :2 input the insert value:101012252937466270785.3、查找*MENU OF BSTREE*1.create2.insert-M*3.search4delete*5.exitwhat do you weint to do? : 3 input the search value:29 result is: 29MFM5.4、删除并中序输出* MENU OF BST

13、REE* 1.create2. insert* 3,search4,delete* 5.exit*what do you want to do? :4 input the delete value:121025293746627078六、程序清单#i nclude #defi ne null 0 typedef int keytype; typedef struct nodekeytype key;struct node *lchild,*rchild; bst no de,*bstree; void in sert(bstree *t,keytype x); bstree search(bs

14、tree t,keytype x); void display(bstree t);void create(bstree *t)keytype x;*t=null;sca nf(%d, &x);while(x!=-1)in sert(t,x);scan f(%d, &x);void in sert(bstree *t,keytype x)bstree s;if(*t=null)s=(bstree)malloc(sizeof(bst no de); s-key=x;s-lchild=n ull;s-rchild=nu II;*t=s;else if(xkey)in sert(&(*t)-lchi

15、ld),x);else if(x(*t)-key)in sert(&(*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 prin tf(%d can not be foundn ,x); return n ull;bstree delete(bstree t,keytype x)bstree p,q

16、,r,s;p=t；r=n ull;while(p)if(x=p-key) break;r=p；if(xkey) p=p-lchild;elsep=p-rchild;if(p=nu II)pri ntf(%d is not exist!n,x);retur n t;if(p-lchild=n ull)|(p-rchild=nu II)if(r=n ull)if(p-lchild=n ull)t=p-rchild;elset=p-lchild;else if(p-lchild=n ull)if(r-lchild=p)r-lchild=p-rchild;elser-rchild=p-rchild;e

17、lse if(r-lchild=p)r-lchild=p-lchild;elser-lchild=p-lchild;free(p);elseq=p;s-lchild;while(s-rchild)q=s;s-rchild;if(q=p)q-lchild=s-lchild;elsep-key=s-key;free(s);return t;void display(bstree t)if(t!=null)display(t-lchild);prin tf(%5d,t-key);display(t-rchild);void main (void)bstree t,b;int i=1,j;keytyp

18、e x;while(i)prin tf(n* * * * * * * * * * * * * * *n);prin tf(n*MENU OF BSTREE*n);prin tf(n*l.create2.i nsert*n);prin tf(n*3.search4.delete*n);prin tf(n*5.exit*n);prin tf(n* * * * * * * * * * * * * * *n);printf( what do you want to do? :);sca nf(%d,&j); switch(j)case 1: printf(input bstrees values,end with -1:n);create(&t); prin tf(bstrees root is %dn,t-key);display(t);break;case 2: pri