数据结构二叉排序树课程设计汇本报告

1、 17/17 课程设计报告数据结构题目：二叉排序树姓 名：学 号：专 业：班 级：指导老师： 年 月 日目 录TOC o 1-3 h u HYPERLINK l _Toc20752 一、课程设计简介 PAGEREF _Toc20752 3 HYPERLINK l _Toc11625 二、原理分析及流程32.1、原理分析3 2.2、流程图4 1、main()函数4 2、创建4 3、插入5 4、查找6 HYPERLINK l _Toc1940 5、中序遍历输出7 HYPERLINK l _Toc2910 三、算法描述8 HYPERLINK l _Toc26960 3.1、存储结构8 HYPERLI

2、NK l _Toc29432 3.2、插入算法8 HYPERLINK l _Toc3385 3.3、查找算法9 HYPERLINK l _Toc29623 3.4、删除算法10 HYPERLINK l _Toc20392 四、小结与体会12 HYPERLINK l _Toc16392 五、程序执行过程13 5.1、创建二叉排序树并中序输出13 5.2、插入并中序输出13 5.3、查找14 HYPERLINK l _Toc7103 六、程序清单14一、课程设计简介1.1、题目：二叉排序树相关操作1、创建二叉排序树；2、插入给定值；3、查找给定值；4、删除给定值的结点。1.2、报告要求：1、封面;

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

4、te(&t)输入结点值，以-1结束调用插入函数 2、创建：3、插入：Insert(&t,x)输入给定的结点值*t=nullxkeyinsert(&(*t)-lchild)x);insert(&(*t)-rchild)x)*t=s结束N YN Y 4、查找：返回search(p-rchild,x)输入给定的结点值x,p=tP!=nullxkey返回search(p-lchild,x)返回nullsearch(t,x)返回p-keyx=p-keyYNYN 5、中序遍历输出：display(t)t!=nulldisplay(t-lchild)访问并输出根节点display(t-rchild)三、算法

5、描述3.1、存储结构定义一个链表式的二叉排序树，用链表的方式构造结点，存储二叉排序树中的结点、结点类型和指针类型如下：#include #define null 0typedef int keytype;typedef struct nodekeytype key;struct node *lchild,*rchild;bstnode,*bstree;3.2、插入算法在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。若二叉排序树中不存在关键字等于x的节点，则插入。将一个关键字值为x的节点s插入到二叉排序树中，可以用下面的方法： （1）若二叉排序树为空，则关键字为x的节点

6、s成为二叉排序树的根 （2）若二叉排序树非空，则将x与二叉排序树根进行比较，如果x的值等于根节点关键值，则停止插入；如果x的根节点值小于根节点关键值，则将x插入左子树；如果x的值大于根节点关键字的值，则将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

7、d),x); else if(x(*t)-key) insert(&(*t)-rchild),x);3.3、查找算法 （1）若二叉排序树不为空，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则查找不成功。 （2）否则，查找失败，返回null。算法如下：bstree search(bstree t,keytype x) bstree p; p=t; if(p!=null) if (x=p-key) return p-key; else if(xk

8、ey) 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的左孩子。根据被删除节点p有无孩子，删除部分可做以下3中情况讨论：（1）若p为叶子节点，则可令其父节点r的左孩子指针域为空，直接将其删除。（2）若p节点只有右子树或左子树，则可以将p的左子树或右子树直接改为其双

9、亲节点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(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=nul

10、l)|(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-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-l

11、child; else p-key=s-key; free(s); return t; 四、小结与体会 经过一个多星期来夜以继日的努力，终于把课程设计二叉排序树的相关算法全部完成！在编写程序过程中，让我对二叉排序树的创建、插入、查找、删除算法有了较系统的认识，也发现了一些以前纸上谈兵时的思想误区。比如实现插入功能时，从根节点开始比较；当实现删除功能时，如果待删除结点p左、右子树齐全，首先找到p的中序前驱节点s（p的中序前驱），然后用节点s的值代替节点p的值，再将节点s删除，节点s的原左子树改为s的双亲节点q的右子树。实现中序遍历功能时，采用递归思想这是第一次关于编写程序的课程设计。虽然上机安排

12、只有两天时间，可却并不像平时上机实验一样，离开了机房就不用再对着电脑屏幕编写代码，更多的工作实在离开机房后完成的。一遍一遍地按F9调试程序，error从几十个减少到几个，再到只剩几个warring，当按下Ctrl+F9，那精心设计的“菜单”出现在屏幕上时，那一刻的心情无以言表！涌上心头的除了自豪感、成就感之外，还有对编程工作之辛苦的慨叹！因为自己专业将来的方向与这有关，不免让我考虑起毕业后的发展方向。如果朝这方面发展的话，我是否可以胜任这样的工作？如果不是，又该选择什么？程序执行过程 5.1、创建二叉排序树并中序输出 5.2插入并中序输出5.3、查找5.4、删除并中序输出六、程序清单#incl

13、ude #define null 0typedef int keytype;typedef struct node keytype key; struct node *lchild,*rchild;bstnode,*bstree;void insert(bstree *t,keytype x);bstree 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)

14、; 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)-lchild),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

15、; 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; 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);re

16、turn 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-lchild=p-lchild; else r-lchild=p-lchild; free(p); else q=p; s-lchild; while(s-rchild) q=s;s-rchil

17、d; 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; while(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