二进制排序树的建立和遍历的实现

武汉理工大学“数据结构”课程设计指导书课程设计任务书书名: 建立二元排序树和实现遍历的初始条件: 理论: 学习了“数据结构”课程，掌握了基本数据结构和通用算法；做法: 计算机技术实验室提供计算机和软件开发环境. 要完成的主要任务: （包括课程设计的工作量和技术要求，以及编写手册的具体要求）1.系统应具有的功能: （1）建立一个二进制排序树； （2）中阶遍历二叉树并输出排序结果； 2.数据结构设计； 3.主要算法设计； 4.编程和计算机实现； 5.编写课程设计报告，包括: （1）设计主题； （2）摘要和关键词； （3）正文，包括引言，需求分析，数据结构设计，算法设计，程序实现与测试，设计经验等； （四）结论； （5）参考资料. 时间表: 2007年7月2日至7日（第18周）7月2日检查信息7月3日系统设计，数据结构设计，算法设计7月4日至5日编程和调试7月报告写在6日，验收程序写在7月7日，并且设计报告已提交. 指导老师签名: 2007年7月2日部门负责人（或负责老师）签名: 2007年7月2日分类二叉树的建立及其遍历的实现武汉理工大学“数据结构”课程设计规范摘要: 我设计的项目为了建立排序的二叉树及其遍历实现，其主要功能是将输入数据组合到排序的二叉树中，并按顺序，一阶，中间顺序和后顺序进行遍历.

设计本主题采用C语言编程，简洁而方便. 它主要使用构建函数，调用函数二叉排序树的建立，构建递归函数等功能进行设计. 关键字: 排序二叉树，一阶遍历，中阶遍历，后序遍历0. 简介我设计的主题是排序二叉树的建立及其遍历的实现. 排序二叉树是空树或具有以下属性的二叉树: （1）如果其左子树不为空，则子树上所有节点的值小于其根节点的值; （2）如果其右子树不为空，则右子树上所有节点的值大于其根节点的值; （3）它的左和右子树也是二进制排序树. 要构建排序的二叉树二叉排序树的建立，您需要了解其定义并插入一个节点以构建排序的二叉树，遍历及其输出. 该设计基于输入数据构建排序的二叉树. 遍历排序的二叉树的关键是使用递归调用，这将极大地促进算法设计. 1.需求分析建立了一个排序的二叉树，主要需要建立节点来存储输入数据，以及一个创建排序的二叉树的功能. 在该函数内，需要进行数据比较以确定数据是放置在左侧还是右侧子树中. 在遍历二叉树时，需要建立一个递归函数进行遍历. 本主题包含两个方面，一个是建立排序的二叉树. 另一种是排序的二叉树的遍历，包括前序遍历，中阶遍历和后序遍历. 排序后的二叉树的构造主要通过使用循环语句和递归语句来执行，而遍历算法则通过使用递归语句来执行.

2. 数据结构设计本主题主要使用节点的建立，指针变量的构造，节点函数的插入以及用于排序的二叉树函数的建立，深度函数的搜索以及预遍历函数，中阶遍历函数，和后遍历功能. 常见的输入和输出语句. 明确已建立功能的功能. 首先，阐明该函数的内部程序和算法. 将其应用于整个程序时，在构建排序的二叉树时，主要用于建立节点函数，树函数，深度函数，以及遍历树为，使用一阶遍历函数，中阶遍历函数和二阶遍历函数. 武汉理工大学《数据结构》课程设计规范节点结构定义: typedef struct tnode / *创建节点* / {int数据； struct tnode * lchild，* rchild;} TNODE; 3.算法设计在设计算法时，应将主题分为两部分: 建立二叉树的遍历和遍历二叉树的遍历. 3.1定义节点typedef struct tnode / *创建节点* /（int数据; struct tnode * lchild，* rchild;）TNODE;结点* q; / *构造函数指针变量* / TNODE * bt; 3.2插入节点函数insert（）无效插入（TNODE ** b，TNODE * s）/ *将节点插入已排序的二叉树* /（if（（* b）== NULL）（* b）= s;否则（s->数据==（* b）->数据）返回;否则，如果（s->数据<（* b）->数据）插入（（&&（* b）-> lchild），s）;否则if（s-> data>（* b）-> data）insert（（&&（* b）-> rchild），s）;} 3.3创建树函数creat（）void creat（TNODE * b）/ *构建排序二叉树* /武汉理工大学结构》课程设计规范{int x; TNODE * s; b = NULL; / *初始二进制数* / scanf（“％d”，＆x）; s =（TNODE *）malloc （sizeof（TNODE））; q = s; / *将根节点指针的地址分配给q * / while（x！= -1）/ *重复读取该节点直到-1 * /（s- >数据= x; s-> lchild = NULL; s-> rchild = NULL; insert（＆bt，s）; scanf（“％d”，＆x）; / *节点插入已排序的二叉树* / s =（TNODE *）malloc（sizeof（TNODE））; n = n + 1;}} 3.4找到排序后的二叉树的深度int deep（TNODE * t）/ * F ind排序后的二叉树的深度* / {int rd;国际如果（！t）返回0;否则{ld =深（t-> lchild）; rd = deep（t-> rchild）；}武汉理工大学“数据结构”课程设计规范，如果（ld> rd）返回ld +1；否则返回rd + 1;} 3.5创建一个预遍历函数void preorder（TNODE * p）{if（p）{printf（“％4d”，p-> data）;预购（p-> lchild）; preorder（p-> rchild）;}} 3.6有序遍历无效有序（TNODE * p）{if（p）{inorder（p-> lchild）; printf（“％4d”，p->数据）； inorder（p-> rchild）;}} 3.7后序遍历void postorder（TNODE * p）{if（p）/ *一阶遍历二叉树* / / *中阶遍历二叉树* / / *后序遍历二进制树* /武汉理工大学“数据结构”课程设计规范{postorder（p-> lchild）;后订单（p-> rchild）; printf（“％4d”，p->数据）；}}这三个函数都应用递归调用.

最后，已建立的函数在主函数中被单独调用. 3.8技术讨论在设计程序时，我发现使用递归函数编写程序要简单得多，这可以大大减少程序代码并查找排序二叉树. 深度，一阶遍历和排序二叉树，中阶遍历和排序二叉树以及总和；后序遍历和排序二叉树均使用递归函数，从而大大简化了源代码. 输入数据时，使用while函数可以连续输入数据，从而解决了无法从外部输入数据的问题. 这是非常聪明的. 4. 程序实现4.1加载到文件#include #include #include 4.2 Main function main（）void main（）/ * Main function * / {printf（“请插入数字（当您完成数字插入后，请在末尾插入-1）: \ n“）；创造（bt）; / *构造排序二叉树* / printf（“节点数为: ％4d”，n）; // *输出的节点数排序后的二叉树* /武汉理工大学“数据结构”课程设计规范printf（“ \ n树的深度: ”）; printf（“％4d”，深（q））； / *查找二叉树深度* / printf（“ \ npreorder，结果是: ”）；预购（q）; / *一阶遍历排序二叉树* / printf（“ \ ninorder，结果为: ”）；顺序（q）; / *按顺序遍历排序二叉树* / printf（“ \ npostorder，结果是: ”）;后订单（q）; / *后遍历排序二叉树* / getchar（）;}，然后输出结果.

在设计中，最困难的部分是找到插入节点的功能. 在该功能中，执行比较. 较小的数字分配给左子树，较大的数字分配给右子树. 在其他算法设计中，只要思路明确就不太困难. 4.3运行结果显示程序: 输入数据: 武汉理工大学“数据结构”课程设计规范输出结果: 5.设计经验我感到最深的一点是我曾经使用C语言进行编程，但我只是专注于如何编写函数要完成所需的功能，似乎对如何设计以及在什么阶段尚无明确的想法. 设计完成后，我学习了如何设计程序以及如何控制整个程序. 它教会了我如何设计程序，设计算法和设计主题. 通过本周的课程设计，我仍然能收获很多. 我的c语言水平已经提高了很多. 其中，c语言比以前对指针和链接列表操作有更深入的了解. 此外，数据结构得到了改进，存储结构以及各种搜索和排序也得到了改进. 尽管我编写的程序中仍然存在编写问题，而且还不够深入，但是独立完成较大程序的经验也很有价值. 通过本课程设计，我认为我们学习“数据结构”的方法存在某些缺点. 武汉理工大学“数据结构”课程设计规范的影响直接影响我们对其他课程的学习和未来业务的增长. 我认为我们对“数据结构”的研究不仅包括理论部分，而且还要求我们勤于实践.

整个实验过程应根据教学进度和我们的实际情况，制定实验内容. 实验分为两部分. 一种是确认性的，主要是结合课堂理论教学的内容. 学生可以验证在课堂上学习的基本算法. 另一种是设计实验并坚持“为实际目的学习”的原则. 学生会充分利用所学的理论知识来进行相对复杂的应用程序设计，以进一步提高他们的综合能力和创新实践能力. 通过这种设计，我产生了很多情感. 确实，从主题选择到定稿，从理论到实践，在一周的一天中，可以说它比甜蜜更苦，但是您可以同时学到很多东西. 您不仅可以巩固以前学到的东西，而且还学到了很多书本上没有学到的东西. 通过本课程设计，我了解到将理论与实践相结合非常重要. 仅理论知识是远远不够的. 只有将学到的理论知识与实践相结合，并从理论中得出结论，才能真正为社会服务，从而提高人的实践能力和独立思考能力. 设计过程中遇到的问题可以说是困难的. 毕竟，当我第一次这样做时，我不可避免地会遇到各种问题. 同时，我发现了设计过程中的缺点. 我对以前的知识不太了解，也对它的掌握不够. 通过课程设计后，我必须复习以前的知识. 6.结束语本文主要讨论排序的二叉树的建立及其遍历的实现. 它的主要功能是: 在输入数据上形成排序的二叉树，并找到排序的二叉树的节点和深度. 遍历和后序遍历，输出结果. 参考文献[1]严为民，吴为明. 《数据结构》，清华大学出版社，2001年1月[2]谭浩强. “ C程序设计”，清华大学出版社，2002年1月[3]赵忠萌，张蓓. 典型数据结构问题分析“西北工业大学出版社2002年8月[4]钱能. ” C ++编程教程“清华大学出版社，2005年2月

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