《数据结构课程设计二叉排序树的实现.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计二叉排序树的实现.doc（21页珍藏版）》请在三一办公上搜索。
1、课 程 设 计 说 明 书课程名称： 数据结构 设计题目： 二叉排序树的实现 院 系： 学生姓名： 学 号： 专业班级： 指导教师： 2010年5月29日课 程 设 计 任 务 书设计题目二叉排序树的实现 姓名罗浩 院系计算机科学与信息工程系专业、年级、 班08软件工程1班设计要求：a) 以回车(n)为输入结束标志,输入数列L，生成一棵二叉排 序树T；b) 对二叉排序树T作中序遍历，输出结果；c) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；学生应完成的工作：1、按设计要求完成各项任务。2、测试数据及测试结果在上交的资料中写明
2、，必须上机调试通过。l3、按数据结构课程设计大纲中的要求完成课程设计报告格式。4、设计结束后，上交如下材料：1）课程设计报告打印稿一份 2）课程设计的源代码电子文档一份参考文献阅读：1 李春葆 尹为民 李蓉蓉 蒋晶鈺 喻丹丹.数据结构教程上机实验指导.2 谭浩强.C程序设计教程3唐宁九 游洪跃 朱宏.数据结构与算法（C+版） 工作计划：共计一周时间，进度安排如下：1 选题，在上机实验之前看透设计要求，翻阅资料完成程序设计大致提纲 。2 选好题，上级编写程序（需求分析、概要设计） 。3 填写算法，实现设计要求的各项功能（详细设计） 。4. 调试和分析，最终完成较合理的程序设计 。5. 按数据结构
3、课程设计大纲中的要求完成课程设计报告格式。任务下达日期： 2010 年 5 月 27 日 任务完成日期： 2010 年 6 月 3 日指导教师（签名）： 学生（签名）：罗浩（设计题目）摘 要：设计一个程序，根据任一数列生成一棵二叉排序树；实现基本的遍历方法；查询结点并删除结点且保证仍为二叉排序树。具体要求：用顺序和二叉链表作存储结构,输入数列L，以回车(n)为输入结束标志生成一棵二叉排序树T；对二叉排序树T作中序遍历，输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,否则输出信息“无x”。 根据二叉排序树的概念，查找当前插入的元素的位置；删除结点如果不是叶子结点，要注意考
4、虑如何使树仍为二叉排序树。关键词：二叉排序树，二叉链表，遍历，查询，删除目 录1. 设计背景41.1 问题的提出41.2 任务与分析42.设计方案42.1整体设计方案43. 方案实施53.1主程序模块设计方案53.2初始化模块设计方案51）.实现二叉树的初始化52）. 创建一棵二叉树：63.3中序遍历模块设计方案：73.4 查找并删除元素模块设计方案81) 查找元素x：82) 删除元素x：83.5 主函数设计方案104. 结果与结论114.1结果演示114.2结果演示125. 收获与致谢125.1总结：125.2致谢：136. 参考文献137. 附件137.1源程序：131. 设计背景1.1
5、问题的提出根据自己的知识功底和能力水平，选择二叉排序树的实现问题。而随着计算机发展并逐渐成为各行业不可缺少的东西，数据结构与算法包含计算机科学与技术的许多重要方面，对训练学生编出质量高、风格好的程序，又语言的发展，C+已成为用处最为广泛的语言。该设计运用数据结构知识，利用C+编写，来锻炼和提高我自己的编程及独立解决问题的能力，故选较为基础，但知识点广泛的题目。1.2 任务与分析 任务是一个二叉排序树的实现问题，根据任一数列生成一棵二叉排序树；实现基本的遍历方法；查询结点并删除结点且保证仍为二叉排序树。根据二叉排序树的概念，查找当前插入的元素的位置；删除结点如果不是叶子结点，要注意考虑如何使树仍
6、为二叉排序树。2.设计方案2.1整体设计方案此课题研究二叉排序树的实现，建立二叉排序树；中序遍历并显示遍历结果；输入元素x,查找x；若存在删除之，否则输出“无x”；然后再进行中序遍历输出遍历结果。为方便起见，画出流程图如图1：初始化模块CreateBST()中序遍历二叉排序树inorder()中序遍历二叉排序树inorder()查找元素xBSTSearch()主程序模块图1该程图描述了主要程序及函数。3. 方案实施3.1主程序模块设计方案#include typedef int KeyType;typedef char ElemType10;typedef struct tnodeKeyTyp
7、e key;ElemType data;struct tnode *lchild,*rchild;BSTNode;定义全局变量、分配储存空间。3.2初始化模块设计方案1）.实现二叉树的初始化BSTNode *CreatBST(KeyType A,int n)/由数组中的关键字建立一棵二叉排序树BSTNode *bt=NULL; /初始时bt为空树int i=0;while(ikey=k)return(0);f=p;/*f指向*p结点的双亲结点*/if (p-keyk)p=p-lchild;/*在左子树中查找*/elsep=p-rchild;/*在右子树中查找*/p=new BSTNode;/*
8、建立新结点*/p-key=k;p-lchild=p-rchild=NULL;if (bt=NULL)/*原树为空时,*p作为根结点插入*/bt=p;else if (kkey)f-lchild=p;/*插入*p作为*f的左孩子*/elsef-rchild=p;/*插入*p作为*f的右孩子*/return(1);void CreateBST(BSTNode *&bt,KeyType str,int n)bt=NULL; /*初始时bt为空树*/int i=0;while (ilchild);coutkeyrchild);3.4 查找并删除元素模块设计方案1) 查找元素x：BSTNode *BST
9、Search(BSTNode *bt,KeyType k)BSTNode *p=bt;while (p!=NULL & p-key!=k)if (kkey) p=p-lchild; /*沿左子树查找*/else p=p-rchild; /*沿右子树查找*/return(p);2) 删除元素x：int BSTDelete(BSTNode *&bt,KeyType k)BSTNode *p=bt,*f,*r,*f1;f=NULL;/*p指向待比较的结点,f指向*p的双亲结点*/while (p!=NULL & p-key!=k)/*查找值域为x的结点*/f=p;if (p-keyk) p=p-lc
10、hild;/*在左子树中查找*/elsep=p-rchild;/*在右子树中查找*/if (p=NULL)/*未找到key域为k的结点*/return(0);else if (p-lchild=NULL) /*p为被删结点,若它无左子树*/if (f=NULL)/*p是根结点,则用右孩子替换它*/bt=p-rchild;else if (f-lchild=p)/*p是双亲结点的左孩子,则用其右子替换它*/f-lchild=p-rchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其右孩子替换它*/f-rchild=p-rchild;delete p
11、;else if (p-rchild=NULL)/*p为被删结点,若它无右子树*/if (f=NULL)/*p是根结点,则用左孩子替换它*/bt=p-lchild;if (f-lchild=p)/*p是双亲结点的左孩子,则用其左孩子替换它*/f-lchild=p-lchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其左孩子替换它*/f-rchild=p-lchild;delete p;else/*p为被删结点,若它有左子树和右子树*/f1=p;r=p-lchild;/*查找*p的左子树中的最右下结点*r*/while (r-rchild!=NUL
12、L)/*r一定是无右子树的结点,*f1作为r的双亲*/f1=r;r=r-rchild;if (f1-lchild=r)/*r是*f1的左孩子,删除*r*/f1-lchild=r-rchild;else if (f1-rchild=r)/*r是*f1的右孩子,删除*r*/f1-rchild=r-lchild;r-lchild=p-lchild;/*以下语句是用*r替代*p*/r-rchild=p-rchild; if (f=NULL)/*f为根结点*/bt=r;/*被删结点是根结点*/else if (f-lchild=p)/*p是*f的左孩子*/f-lchild=r;else/*p是*f的右孩
13、子*/f-rchild=r;delete p;return(1);3.5 主函数设计方案void main()int n;BSTNode *bt=NULL,*p;KeyType a200,k;cout n;cout 请输入数据:; for(int i=0;iai;CreateBST(bt,a,n);coutBST:; BSTdisp(bt);coutendl;cout中序遍历二叉排序树:endl;inorder(bt);coutn;/cout先序遍历二叉排序树:;/preorder(bt);/coutn;coutk;p=BSTSearch(bt,k);if(p!=NULL)BSTDelete(
14、bt,k);cout 已经删除值为k的结点endl;cout中序遍历二叉排序树:; inorder(bt);elsecout无kn;4. 结果与结论4.1结果演示（删除元素在二叉排序树中）运行结果如图2：4.2结果演示（删除元素不在二叉排序树中）运行结果如图3：5. 收获与致谢5.1总结：这几天的工作，终于完成了程序设计。可也遇到了不少问题，其中较为麻烦的是程序的调试。经过这几天的的上机实践和查阅资料 ，我变改变思路用C+编写，最终实现了所有要求。了虽然问题出现了不少，但收获也是颇丰：认识到自己的不足，要努力。解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；、 初步掌握软件开发
15、过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 通过课程设计，提高了自己的编程能力。掌握了以往不太熟悉的知识，比如：C中的标准函数库、函数的调用及嵌套调用。通过实践的学习，我认识到学好计算机要重视实践操作，不仅仅是数据结构，还有其它的计算机方面的知识都要重在实践，以后在学习过程中，我会更加注重实践操作能力的培养，无论学习什么，亲自动手去做了才能有最深刻的体会。5.2致谢：首先需要感谢的是指导老师兼数据结构老师冯慧玲老师，在她的督促下我们按时完成这个课程设计，并且对于提出的各种问题很热情耐心的解答。没有她的教导自然就不可能有基础来完成课程设计了。还有整个完成的过程中我们小组齐心合力，
16、经过翻阅资料、编程，调试最终完成了此次课程设计，大家都得到了应有的收获。6. 参考文献1 李春葆 尹为民 李蓉蓉 蒋晶鈺 喻丹丹.数据结构教程上机实验指导.2 谭浩强.C程序设计教程3唐宁九 游洪跃 朱宏.数据结构与算法（C+版）7. 附件7.1源程序：#include typedef int KeyType;typedef char ElemType10;typedef struct tnodeKeyType key;ElemType data;struct tnode *lchild,*rchild;BSTNode;void BSTdisp(BSTNode *b);BSTNode *BST
17、Search(BSTNode *bt,KeyType k)BSTNode *p=bt;while (p!=NULL & p-key!=k)if (kkey) p=p-lchild; /*沿左子树查找*/else p=p-rchild; /*沿右子树查找*/return(p);int BSTInsert(BSTNode *&bt,KeyType k)BSTNode *f,*p=bt;while (p!=NULL)if (p-key=k)return(0);f=p;/*f指向*p结点的双亲结点*/if (p-keyk)p=p-lchild;/*在左子树中查找*/elsep=p-rchild;/*在
18、右子树中查找*/p=new BSTNode;/*建立新结点*/p-key=k;p-lchild=p-rchild=NULL;if (bt=NULL)/*原树为空时,*p作为根结点插入*/bt=p;else if (kkey)f-lchild=p;/*插入*p作为*f的左孩子*/elsef-rchild=p;/*插入*p作为*f的右孩子*/return(1);/*BSTNode *CreatBST(KeyType A,int n)/由数组中的关键字建立一棵二叉排序树BSTNode *bt=NULL; /初始时bt为空树int i=0;while(in)if(BSTInsert(bt,Ai) /将
19、Ai插入二叉排序树T中count 第i+1步，插入:Ai;DispBST(bt); printf(n);i+;return bt; /返回建立的二叉排序树的根指针*/void CreateBST(BSTNode *&bt,KeyType str,int n)bt=NULL; /*初始时bt为空树*/int i=0;while (ikey!=k)/*查找值域为x的结点*/f=p;if (p-keyk) p=p-lchild;/*在左子树中查找*/elsep=p-rchild;/*在右子树中查找*/if (p=NULL)/*未找到key域为k的结点*/return(0);else if (p-lc
20、hild=NULL) /*p为被删结点,若它无左子树*/if (f=NULL)/*p是根结点,则用右孩子替换它*/bt=p-rchild;else if (f-lchild=p)/*p是双亲结点的左孩子,则用其右子替换它*/f-lchild=p-rchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其右孩子替换它*/f-rchild=p-rchild;delete p;else if (p-rchild=NULL)/*p为被删结点,若它无右子树*/if (f=NULL)/*p是根结点,则用左孩子替换它*/bt=p-lchild;if (f-lchi
21、ld=p)/*p是双亲结点的左孩子,则用其左孩子替换它*/f-lchild=p-lchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其左孩子替换它*/f-rchild=p-lchild;delete p;else/*p为被删结点,若它有左子树和右子树*/f1=p;r=p-lchild;/*查找*p的左子树中的最右下结点*r*/while (r-rchild!=NULL)/*r一定是无右子树的结点,*f1作为r的双亲*/f1=r;r=r-rchild;if (f1-lchild=r)/*r是*f1的左孩子,删除*r*/f1-lchild=r-rch
22、ild;else if (f1-rchild=r)/*r是*f1的右孩子,删除*r*/f1-rchild=r-lchild;r-lchild=p-lchild;/*以下语句是用*r替代*p*/r-rchild=p-rchild; if (f=NULL)/*f为根结点*/bt=r;/*被删结点是根结点*/else if (f-lchild=p)/*p是*f的左孩子*/f-lchild=r;else/*p是*f的右孩子*/f-rchild=r;delete p;return(1);/先序遍历/*void preorder(BSTNode *t) if(t!=0) coutkeylchild);pr
23、eorder(t-rchild);*/中序遍历void inorder(BSTNode *t) if(t!=0) inorder(t-lchild);coutkeyrchild);void BSTdisp(BSTNode *bt)if(bt!=NULL)coutkey;if(bt-lchild !=NULL|bt-rchild !=NULL)coutlchild );if(bt-rchild !=NULL)coutrchild );cout);void main()int n;BSTNode *bt=NULL,*p;KeyType a200,k;cout n;cout 请输入数据:; for(
24、int i=0;iai;CreateBST(bt,a,n);coutBST:; BSTdisp(bt);coutendl;cout中序遍历二叉排序树:endl;inorder(bt);coutn;/cout先序遍历二叉排序树:;/preorder(bt);/coutn;coutk;p=BSTSearch(bt,k);if(p!=NULL)BSTDelete(bt,k);cout 已经删除值为k的结点endl;cout删除X后的BST:; BSTdisp(bt);coutendl;cout中序遍历二叉排序树:; inorder(bt); coutendl;elsecout无kn;指导教师评语：1
25、、课程设计报告：a、内容： 不完整 完整 详细 b、方案设计： 较差 合理 非常合理c、实现： 未实现 部分实现 全部实现 d、文档格式： 不规范 基本规范 规范 2、出勤： 全勤 缺勤 次3、答辩： a、未能完全理解题目，答辩情况较差 b、部分理解题目，部分问题回答正确 c、理解题目较清楚，问题回答基本正确 d、理解题目透彻，问题回答流利 课程设计报告成绩： ，占总成绩比例： 50% 课程设计其它环节成绩：环节名称： 出勤 ，成绩： ，占总成绩比例： 20% 环节名称： 答辩 ，成绩： ，占总成绩比例： 30% 总 成 绩： 指导教师签字：年 月 日本次课程设计负责人意见：负责人签字：年 月 日
