《二叉树排序说明书》由会员分享，可在线阅读，更多相关《二叉树排序说明书（21页珍藏版）》请在金锄头文库上搜索。
1、摘要该程序和课本上的二叉排序树基本相同!但是在调试过程中遇到了一些问题。 我采用的是非递归思想进行遍历，所以存在的基本的语法错误，问题主要在于函 数和变量的定义。关键字和函数名的书写。时间，空间性能分析：二叉排序树的的查找与二分查找类似，是一个逐一缩 小查找范围的过程。具有n个节点的排序二叉树是一棵深度为n的单枝树，平均 查找长度与顺序查找相同，为（n+1）/2；即平均查找长度的数量级为O（n）。关键词：创建；查找节点；中序排序；删除节点；插入节点序言“数据结构”课程的教学目标是要求学生学会分析数据对象特征，掌握数据 组织方法和计算机的表示方法，以便为应用所涉及的数据选择适当的逻辑结构、 存储
2、结构以及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设 计技能。数据结构的学习过程是进行复杂程序设计的训练过程。技能培养的重要程度 不亚于知识传授，学生不仅要理解授课内容，还应培养应用知识解答复杂问题的 能力，形成良好的算法设计思想、方法技巧与风格，进行构造性思维，强化程序 抽象能力和数据抽象能力。因此，学习数据结构，仅从书本上学习是不够的，必 须经过大量的实践，在实践中体会构造性思维的方法，掌握数据组织与程序设计 的技术。在该课程的学习过程中，初学者会感到困惑，其主要原因：一是数据结构内 容抽象；二是动态存储结构难以理解；三是使用多种技术，如递归技术等掌握较 为困难；四是算法描述
3、、设计无从下手等。目录一、程序设计31.1数据结构设计31.2函数设计31.3函数调用关系31.4主要函数流程图4二、调试分析7三、测试及运行结果8四、课程设计总结15参考文献12致谢13附录14、程序设计1.1数据结构设计main():主函数模块Bsearch():查找相应的节点InsertBST ():插入一个新节点CreateBST ()：创建一棵二叉排序树Inorder ():对二叉排序树进行中序遍历 menu():主函数显示菜单模块DeleteBST ()：删除节点1.2函数设计函数列表，如图0所示:函数名称函数原型功能描述mainvoid main()主函数，程序入口InsertB
4、ST ()CreateBST创建插入节点DeleteBSTCreateBST输出删除、创建节点表1函数列表1.3函数调用关系函数调用关系，如图1所示:输入二叉排序树中的元调用menu函显示菜单调用子函数InsertBST()调用子函数Bsearch()调用子函数DeleteBST ()Inorder ()x=p-keyxkey（ 开始 ）YNNYp=p-lchildp=p-rchild图（2）二、调试分析调试中所遇问题及相应解决方法1、问题：输入节点中不存在的节点是，会报告找不到此节点。解决：在节点中逐个找一遍，如果没有则输出找不到节点。2、问题：如果输入节点中没有的数据时，中序有什么变化。解
5、决：中序和以前的中序结果一样。三、测试及运行结果测试及运行结果，如下图所示：将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若根节点 关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤； 若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则算法的时间及空间复杂度1. 输入节点信息：C:Documents and SettingAdministratorM面课程设计.exe府输入节点h.2345680，序遍历所得序列为：1234568| 1插入节点二2 查找节点3 删除节点4 退出后选择操作、2. 选择插入一个新节点:3. 查找一个已有节点:C:Docum
6、ents and SettingAdministratorM面Debu鞘课程设计.exb情输入节点信息，并以 智 结束；b.2345680印序遍历所得序列为：1234568| 1插入节点二2 查找节点3 删除节点4退出节遍 据I:1的序3:2数点寿中雷节作操个，2囊该操择一后择查塞选X-入1选人挨选列6是5:7丽点历4:64. 查找一个没有的节点:5. 删除一个节点:C:Documents and SettingAdministratorM面山酣喝课程设计.exe12345681插入节点查找节点删除节点4退出利6黑-5:7呢点历4:61点 所 :1节:5历 4节遍 据,言 :1的序3:2数点:
7、2数11:3数序 麝中雷节富为富中 操个- 择一后择查臂查塞管 选入入1选入找选入不选入除1选6.若操作完成，则退出程序:四、课程设计总结此程序目前的缺点：若二叉排序树为空，则查找失败。否则，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若 根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进 行此步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查 节点，则查找不成功。必须将当前操作结束等到下个主函数的循环开始，或者直接退出重新运 行此程序。优点则在于程序运行速度较快，不会出现输出结果有误的问题经 过这次集中上机的实验，从开始选题到自己上手还是编写程序的过
8、程中，我 学会了很多的东西，以前对C语言的知识和算法总是模棱两可的，经过这次 ，在某些方面上还是经过了加强的训练。此次，实验，从开始构建循环 链表然后实现约瑟夫环功能的过程中，中途也遇见一些问题，但都逐一克服， 相信在这次的实验中提升了较大的自身动手实践能力。学好数据结构！参考文献【1】徐孝凯1王昆仑，李红等编著.数据结构与算法.北京：中国铁道 出版社,2007.【2】李业丽，郑良斌编著。数据结构（0）实验教程。北京理工大学出版社 2005.数据结构课程实验M清华大学出版社.2006.【3】严蔚敏.吴伟民.数据结构题集（C语言版）M清华大学出版社.【4】苏仕华.贾伯琪.黄学俊.数据结构（解析习
9、题课程设计）M中国科学技术大学出版社.2009.9致谢首先我要感谢我们年轻有为的老师莅临我们学院指导，其次在编写程序 的过程中，我们得到了老师的精心指导以及孜孜不倦的教诲，在老师的指导 下，我们的能力得到了提高，同时养成了科学、严谨的作风和习惯，在此， 我们对老师的精心栽培表示衷心的感谢！感谢同学对我的帮助和指点，尤其感谢我的舍友在非常时期，在生活和 学习上帮我许多忙。在课设即将完成之际，我的心情无法平静，从开始进入 课题到课设的顺利完成，有多少可敬的师长、同学、朋友给了我无言的帮助， 在这里请接受我诚挚的谢意.源程序清单：#include stdio.h”#include malloc.h”
10、#define NULL 0typedef struct nodeint key;int other ;struct node *lchild,*rchild;Bstnode;Bstnode *Bsearch(Bstnode *t,int x)/查找Bstnode *p;int flag=0;p=t;while(p!=NULL) if(p-key=x) printf(已找到该节点！ )；flag=1;return(p);break;if (xkey)p=p-lchild;else p=p-rchild;if(flag=0)printf(找不到值为d 的节点！ ，x); return NULL;
11、 Bstnode *InsertBST(Bstnode *t,int x)/插入Bstnode *s，*p，*f;p=t;while (p!=NULL)f=p;/查找过程中，f指向*p的父节点if(x=p-key) return t;/二叉排序树中已有关键字为x的元素，无序插入if(xkey) p=p-lchild;else p=p-rchild;s=(Bstnode *)malloc(sizeof(Bstnode);s-key=x;s-lchild=NULL;s-rchild=NULL;if(t=NULL) return s;/原树为空，新节点成为二叉排序树的根if(xkey) f-lchi
12、ld=s;else f-rchild=s;return t;/新节点作为*f的左孩子/新节点作为*f的右孩子Bstnode *CreateBST()/创建一个新的二叉树Bstnode *t;int key; t=NULL;/设置二叉排序树的初态为空scanf(%d”,&key);/读入第一个节点的关键字while(key!=0)t=InsertBST(t,key);scanf(%d”,&key);return t; void Inorder(Bstnode *T)/中序遍历 /若二叉树不空中序遍历左子树访问根节点中序遍历右子树if( T)Inorder(T-lchild);printf(%4d
13、”,T-key);Inorder(T-rchild);Bstnode *DeleteBST(Bstnode *t,int k)/ 删除 Bstnode *p,*f,*s,*q;p=t;f=NULL;/查找关键字为k的待删节点*p/找到，则退出循环/节点*f为节点*p的父节点while(p)if(p-key=k) break;f=p;if(p-keyk) p=p-lchild;else p=p-rchild;/若找不到，则返回原二叉排序if (p=NULL) return t;树的根指针if (p-lchild=NULL)|(p-rchild=NULL) /若*p 无左孩子或右孩子 if(f=NULL)/若*p是原二叉排序树的根if(p-lchild=NULL) t=p-rchild;else t=p-lchild;else if (p-lchild=NULL)/若*p 无左孩子if(f-lchild=p) f-lchild=
