二叉排序树运算-大数据结构与算法课程设计报告材料_l.doc

二叉排序树运算-大数据结构与算法课程设计报告材料_l.doc

ID:56523405

大小:301.77 KB

页数:47页

时间:2020-06-27

二叉排序树运算-大数据结构与算法课程设计报告材料_l.doc_第1页
二叉排序树运算-大数据结构与算法课程设计报告材料_l.doc_第2页
二叉排序树运算-大数据结构与算法课程设计报告材料_l.doc_第3页
二叉排序树运算-大数据结构与算法课程设计报告材料_l.doc_第4页
二叉排序树运算-大数据结构与算法课程设计报告材料_l.doc_第5页
资源描述:

《二叉排序树运算-大数据结构与算法课程设计报告材料_l.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、学院计算机科学与技术系课程设计报告2009~2010学年第二学期课程数据结构与算法课程设计名称二叉排序树运算学生顾成方学号0704011033专业班级08计科(2)指导教师王昆仑贯虹2010年5月题目:(二叉排序树运算问题)设计程序完成如下要求:对一组数据构造二叉排序树,并在二叉排序树中实现多种方式的查找。基本任务:⑴选择合适的储存结构构造二叉排序树;⑵对二叉排序树T作中序遍历,输出结果;⑶在二叉排序树中实现多种方式的查找,并给出二叉排序树中插入和删除的操作。⑷尽量给出“顺序和链式”两种不同结构下的操作,并比较。一、问题分析和任务定义本次程序需要完成如下要求:首先输入任一组数

2、据,使之构造成二叉排序树,并对其作中序遍历,然后输出遍历后的数据序列;其次,该二叉排序树能实现对数据(即二叉排序树的结点)的查找、插入和删除等基本操作。实现本程序需要解决以下几个问题:1、如何构造二叉排序树。2、如何通过中序遍历输出二叉排序树。3、如何实现多种查找。4、如何实现插入删除等操作。二叉排序树的定义:⑴其左子树非空,则左子树上所有结点的值均小于根结点的值。⑴若其右子树非空,则右子树上所有结点的值大于根结点的值。⑵其左右子树也分别为二叉排序树。本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现:输入(插入)的第一个数据即为根

3、结点;继续插入,当插入的新结点的关键值小于根结点的值时就作为左孩子,当插入的新结点的关键值大于根结点的值时就作为右孩子;在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后,要插入新的数据时,要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此,插入算法还要包括对数据的查找判断过程。本问题的难点在于二叉排序树的删除算法的实现。删除前,首先要进行查找,判断给出的结点是否已存在于二叉排序树之中;在删除时,为了保证删除结点后的二叉树仍为二叉排序树,要考虑各种情况,选择正确的方法。删除操作要分几种情况讨论,在后面有介绍。一、概要设计和数据结构选择用二叉链表作为二叉排

4、序树的存储结构,其中key为结点关键值,*lchlid、*rchild分别为左右孩子指针。该程序的结构如下图所示:Main()先建立一棵二叉排序树,并输出其中序排序后的序列二叉排序树的查找二叉排序树的插入二叉排序树的删除二叉排序树的显示非递归查找递归查找二、详细设计和编码首先定义二叉排序树的数据类型如下:typedefstructnode{intkey;//关键字项structnode*lchild,*rchild;//左右孩子指针}Bstnode;然后按一定顺序来编写算法程序:1、递归查找算法具体思想如下:(1)若二叉树为空,则查找失败。(2)否则,将根结点的关键值与待查关

5、键字进行比较,若相等,则查找成功;若根结点关键值大于待查值,则进入左子树重复此步骤,否则,进入右子树重复此步骤;若在查找过程的中遇到二叉排序树的叶子结点时,还没有找到待查结点,则查找不成功。if(t==NULL)returnNULL;else{if(t->data==x)returnt;if(xdata)return(Bsearch(t->lchild,x));elsereturn(Bsearch(t->rchild,x));}二叉排序树递归查找算法流程图1、非递归查找算法查找过程是从根结点开始逐层向下进行的。并定义一个标记量记录是否找到结点。Bstnode*sear

6、chBST(Bstnode*t,intx){Bstnode*p;intflag=0;p=t;//定义*p结点用于逐层查找,丛根结点开始查找while(p!=NULL)//二叉排序树不为空{if(p->key==x)//查找成功{printf("该结点值存在!");flag=1;break;}//查找不成功,到下一层继续查找if(xkey)p=p->lchild;//查找左子树elsep=p->rchild;//查找右子树}if(flag==0){printf("找不到值为%d的结点!",x);p=NULL;}returnp;}1、插入算法从根结点开始,根据比较规则,逐

7、一与待插入结点的值比较,查找到插入结点在二叉排序树中的未来位置,然后插入该结点。将一个关键字的值为x的结点s插入到二叉排序树中,方法如下:(1)若二叉排序树为空,则关键字值为x的结点s成为二叉排序树的根。(2)若二叉排序树非空,则将x与二叉排序树的根进行比较,如果x的值等于根结点关键字的值,则停止插入;如果x的值小于根结点关键字的值,则将x插入左子树;如果x的值大于根结点关键字的值,则将x插入右子树。在左右子树中插入方法与整个二叉排序树相同。Bstnode*InsertBST(Bstnode*t,int

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。