建立和删除二进制排序树

长沙科技大学“数据结构”课程设计报告XXX XX学生姓名XXX主管XXX课程完成日期2013 201150学生姓名XXX主管XX完成日期2013主管对学生在课程设计中的评估和评分项目创意结果在通过课程设计中学生对课程内容的掌握程度课程设计完成课程设计动手能力书面表达学习态度规范课程设计质量要求老师对课程设计评价的指导综合评分指导教师签署课程设计任务计算机与通信工程学院计算机科学与技术学院课程名称数据结构课程设计时间2012〜2013学年第2学期19〜20学生姓名XXX教师XXX建立和删除二进制排序树的主要内容: 二进制链接列表用来 存储两个fork排序树，该树用C语言实现相关程序，实现建立，搜索，插入和删除二进制排序树的根节点，叶节点和其他任意节点的功能，并可以在任何时候的结果. 要求: （1）通过对实际项目的分析，设计，编码和测试，掌握使用C语言开发和维护软件的方法. （2）根据需要编写课程设计报告，并能够正确编写技术文档，例如分析，设计，编码，测试和用户手册. 提交文件: （1）课程设计学年论文.

（2）课程设计附件（主要是源程序）. 二元排序树的建立和删除学生姓名: XXX主管: XXX数据结构是研究数据之间关系的科学. 我们称这种关系为数据的逻辑结构，称为数据结构. 确定数据的逻辑结构后，将数据存储在物理空间中的方式称为数据存储结构. 相同的逻辑结构可以具有不同的存储结构，因此可以具有不同的算法. 在本课程设计中，程序中的数据采用“二叉树结构”. 具体而言，它使用“二进制排序树”并使用“一维数组”作为其存储结构. 一维数组顺序表存储结构使用一组连续的地址存储单元从左到右，从上到下顺序存储二进制排序树的节点元素. 基本操作（例如插入，删除和有序遍历输出）完美地实现了二进制排序树的大多数功能. 关键字: 创建二进制排序树；有序遍历输出；插入节点；查找节点；删除节点目录... .................................... 11.1课程设计的目的..... ........................................ 1 1.2项目的内容要求... ..................................................................... 1 1.3课程设计的重要性.................................................. ................ ............ 1相关理论的基础知识......................................... ....... 22.1二进制排序树的定义.................................. ........ 2 2.2二进制排序树的搜索算法..................................... 2 2 2.3二叉排序树的插入算法... ................................................... 2 2.4二进制排序树删除算法.. . ...................................... 2程序设计和算法流程.............. ........................................................ .... .43.1编程的算法流程..................... ................................ 4 3.2程序操作流程图..... ............. .............................................. ..... 4 3.3功能设计和注释.................................. ....................... 5运行环境和结果.................................. ......... 104.1操作环境.................................. ....................... 10 4.2运算结果.................... ....................... 10总结....................................... .................................................. ......... 12参考资料... .................. 13附录.................................. ............. .............................................. .......... 14代码列表................................................. .................................................................. 14周国庆的“建立和删除二元分类树”本课程设计主要针对二进制排序树的问题实现了建立，搜索，插入和删除二进制排序树的操作，并且可以随时显示操作结果.

1.1课程设计的目的是分析和编程主题，以便更好地理解二进制排序树，二进制排序树的建立，搜索，插入和删除操作的算法思想，并实现这些算法思想通过C语言编程. 1.2课程设计的内容需要一组关键值，要求: （1）建立相应的二进制排序树； （2）删除根节点，叶节点和其他任意节点的功能； （3）随时显示操作结果. 1.3课程设计的意义数据结构的课程设计对我们具有重要意义，主要体现在以下几点: 1.增强对数据逻辑结构和存储表示形式特征的理解，并培养选择合适的数据结构的能力和特定应用中的存储结构. 2.熟悉软件开发的基本过程，并掌握软件开发过程的基本任务和技能，自己的算法设计和算法分析能力，并提高独立分析和解决问题的能力. 4. 从培训体系和软件开发总体规范的角度出发，培养软件工作者应具备的工作方法创建二叉排序树，作风和相互合作的精神. 5. 全面使用链接列表的搜索，插入和删除，并将理论与实践相结合，将其应用于文章编辑实验. 这些知识将得到进一步巩固，深化和扩展. 利用模块的思想，模块之间通过指针连接，减少了不必要的麻烦.

巩固加深指针的目的并了解模块的优点. 加深对链表的理解，充分理解链表操作的字符串的模式匹配操作. 周国庆的“建立和删除二进制排序树”相关的理论基础2.1二进制排序树的定义二进制排序树是空树或具有以下属性的二进制树: （1）如果其左子树不为空，则左子树中所有节点的值小于根节点的值; （2）如果其右子树不为空，则右子树中所有节点的值大于根节点的值; （3）它的左和右子树也是二进制排序树. （4）二进制排序树通常存储在二进制链接列表中. 2.2二进制排序树的搜索算法二进制排序树的搜索实际上是遍历二进制排序树并确定在该过程中是否存在要查找的数据元素. 二进制排序树上的搜索过程: 如果二进制排序树不为空，则现在比较给定的关键字和根节点关键字. 如果它们相等，则搜索成功；否则，搜索成功. 如果它小于根节点关键字，则左子级搜索在树上继续；如果它大于根节点关键字，则搜索将在右侧的子树上继续，直到搜索成功或失败. 二进制排序对树的搜索可以通过两种方式实现: 循环结构和递归结构. 2.3二进制排序树的插入算法对于二进制排序树的插入操作，必须首先确定数据元素是否存在，如果存在，则不执行插入操作；否则，将数据元素插入到搜索路径上访问的最后一个节点中. 左孩子还是右孩子.

二进制排序树的特征应在插入后保持. 二进制排序树中的插入过程: 如果二进制排序树不为空，则比较给定关键字和根节点关键字. 如果它们相等，则插入操作将停止并返回；否则，如果它小于根节点关键字，则在左子树中搜索合适的位置以插入元素；如果关键字大于根节点，请在右侧子树中搜索合适的位置以插入元素. 2.4二进制排序树删除算法二进制排序树删除操作等效于删除数据元素集中的元素. 您不能删除以该节点为基础的所有子树，它们都是周国庆的“构建和删除二进制排序树”. 只能删除该节点创建二叉排序树，并且删除该节点之后的其余数据元素仍需要一个二进制排序树. 二进制排序树的删除过程: 如果二进制排序树不为空，则在二进制排序树中搜索给定数据元素的存在，如果不存在，则返回；如果存在，请分别使用以下四种方法执行不同的操作. （1）如果要删除的节点是叶节点，则直接将其删除； （2）要删除的节点只有一个左子树，删除该节点，将删除的节点的父节点指向删除的节点的左子节点； （3）要删除的节点只是右子树. 删除节点，并使已删除节点的父节点指向已删除节点的右子节点. （4）要删除的节点同时具有左子树和右子树. 首先在要删除的节点的右子树中找到最左边的节点，然后用找到的最左边的节点替换要删除的数据元素，最后以最左边的节点作为参数调用delete函数.

简而言之，问题的实质是删除要删除的节点的右子树的最左节点. 周国庆“建立和删除二进制排序树”的程序设计和算法流程3.1程序设计的算法流程二进制排序树的设计主要分为四个大块，即建立，搜索，插入和删除任何节点. 当然，除了这些主要部分内. 如果不是，请重新输入操作编号. 如果在此间隔内，则根据其值0、1执行相应的操作，具体过程如图3.1所示. 图3.1程序操作流程图周国庆“创建和删除二进制排序树” 3.3功能设计和注意事项（1）二进制排序树通常存储在二进制链接列表中. 节点的结构定义如下: typedef struct bitnode intdata; //定义数据字段struct bitnode * lchild; //定义左子指针结构struct bitnode * rchild; //定义正确的子指针} bitnode，* bitree; （2）建立一个二进制排序树void createbst（bitree * root）//建立一个二进制排序树inti，data，cnt; * root = NULL; //设置输入数据scanf的数量（“％d”，＆cnt）; printf（“请输入数据: for（i = 0; idata == data）//数据等于当前节点的关键字，并且当前节点的关键字返回p-> data; if（p-> data> data）//数据小于当前节点的关键字，然后在左子树中搜索p = p-> lchild；否则p = p-> rchild; //数据大于当前节点的关键字节点，然后找到合适的子树returnINF；（4）二进制排序树的插入操作，首先确定数据元素是否存在，如果存在，则不执行插入操作；否则，将数据元素插入搜索路径在左子节点或右子节点上的节点之后访问.

二进制排序树的特征应在插入后保持. void insertbst（bitree * root，int data）//插入二进制排序树周国庆“二进制排序树的创建和删除” //定义树sif（* root == NULL）{//树为空Case s = （bitree）malloc（sizeof（bitnode））;分配内存空间s-> data = data; //给定的关键字等于根节点关键字s-> lchild = s-> rchild = NULL; //左右子树都是空的* root = s; elseif（datadata）//给定的关键字小于根节点关键字insertbst（＆（（* root）-> lchild），data）; //在左侧搜索子树上的合适位置以插入else if（data>（* root）-> data）//给定的关键字大于根节点关键字insertbst（＆（（（* root）-> rchild），数据）； //在右侧子树中搜索合适的位置以进行插入（5）二进制排序树的删除操作等效于删除数据元素集中的元素. 您无法删除以该节点为根的所有子树. 删除节点，删除节点后剩余的数据元素仍然需要二进制排序树.

bitnode * deletebst（bitree t，int f = NULL; while（p）{if（p-> data == k）break; if（p-> data> k）p = p-> lchild;否则p = p-> rchild; if（p == NULL）{printf（“关键字不存在！\ n”）;周国庆“ Building and Deleting Binary Sort Trees” if（p-> lchild == NULL）{if（ f == NULL）t = p-> rchild;否则if（f-> lchild == p）f-> lchild = p-> rchild;否则f-> rchild = p-> rchild; free（p）; s = p-> lchild;而（s-> rchild）{q-> lchild = s-> lchild;否则q-> rchild = s-> lchild; p-> data = s-> data; free（s）（ 6）主要功能模块根据主题要求，调用每个功能以实现对二进制排序树的建立，搜索，插入和删除，然后调用display函数显示操作结果. main（）intdata，菜单； bitree根；周国庆“创建和删除二进制排序树”表（）; //调用该表函数以显示操作列表printf（“请输入相应的操作: ”）； scanf（“ ％d“，和菜单）； while（！（menu> = 0 menudata == data）//数据等于当前节点的关键字，返回当前节点的关键字返回p-> data; if（p-> data> data）// data is小于当前Node键，然后寻找左子树p = p-> lchild;否则p = p-> rchild; //数据大于当前节点的关键字，然后寻找右子树Zhou Guoqing和删除二进制排序树”，第15个returnINF; voidinsertbst（bitree * root，int data）//插入二进制排序树//定义树sif（* root == NULL）{//如果是空树s =（bitree） malloc（sizeof（bitnode））;分配内存空间s-> data = data; //给定的关键字等于根节点关键字s-> lchild = s-> rchild = NULL; //左和右子树是empty * root = s; elseif（datadata）//给定的关键字小于根节点关键字insertbst（＆（（（* root）-> lchild），data）; //在左子树中搜索合适的位置以插入else if（data>（* root）-> data） //给定的关键字大于根节点关键字insertbst（＆（（（* root）-> rchild），data）; //在右边的子树中搜索合适的位置以插入voiddisplay（bitree root）if（root！= NULL）{display（root-> lchild）; printf（“％5d”，root->数据）；显示（root-> rchild）;

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-149388-1.html