《2022年二叉树实验报告.docx》由会员分享，可在线阅读，更多相关《2022年二叉树实验报告.docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 数据结构课程设计报告专业运算机科学与技术班级3 班姓名学号指导老师名师归纳总结 起止时间2022.122022.1 第 1 页,共 6 页- - - - - - -精选学习资料 - - - - - - - - - 课程设计 ：二叉树一、任务描述二叉树的中序、前序、后序的递归、非递归遍历算法,应包含建树的实现；任务 ：设计一个程序,实现二叉树的前序、中序、后序的递归遍历运算；要求 ：（1）创建二叉树；（2）二叉树的前序、中序、后序的递归遍历运算实现；二、问题分析1、功能分析 分析设计课题的要求,要求编程实现以下功能：（1）二叉树的建立即创建二叉树
2、；（2）二叉树的遍历二叉树的前序、中序、后序操作；2、数据对象分析 二叉树的遍历：包括前序、中序、后序 将二叉树补充到完全二叉树在输入,才能正确创建二叉树三、数据结构设计二叉树的建立和遍历的实现；有关的定义如下：typedef int Status; typedef char TElemType; / 定义二叉树结点值的类型为字符型struct BiTNode / 定义二叉树结点类型栈结点的类型 TElemType data; / 数据域 BiTNode *lchild,*rchild;/ 指针域;BiTNode *BiTree; 四、功能设计（一）主控菜单设计程序运行后,输入提示,如下：“
3、创建二叉树,请按前序序列输入各节点值：”正确输入二叉树后,提示“ 已胜利创建二叉树”（二）程序模块结构由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：创建二叉树的函数 void CreateBiTreeBiTree &T;二叉树的前序遍历函数 二叉树的中序遍历函数 二叉树的后序遍历函数Status PreOrderTraverseBiTree T,Status*VisitTElemType; Status InOrderTraverseBiTree T,Status*VisitTElemType; Status PostOrderTraverseBiTree T,Status
4、*VisitTElemType ；最简洁的 visit 函数 Status VisitTElemType e;（三）函数调用关系程序的主要结构（函数调用关系）如下图所示；名师归纳总结 CreateBiTree Main Visit第 2 页,共 6 页PreOrderTraverse InOrderTraverse PostOrderTraverse - - - - - - -精选学习资料 - - - - - - - - - 其中 main是主函数,它进行菜单驱动；BiTree T; int n=0; printf 创建二叉树,请按前序序列输入各节点值：n; CreateBiTreeT; pr
5、intfn; printf 已胜利创建二叉树 n; PreOrderTraverse T,Visit; printfn; InOrderTraverseT,Visit; printfn; PostOrderTraverseT,Visit; printfn; （四）文件结构1、tree.h：二叉树相关的定义与声明 2、tree.cpp：二叉树运算的实现 5、mn.cpp：主函数（五）各函数的算法设计1、CreateBiTree 算法原理：按先序次序输入二叉树中结点的值（一个字符）链表 流程图：输入一个字符申请内存是否胜利生成根结点 退出程序构造左子树构造右子树 代码描述： void Create
6、BiTreeBiTree &T char ch; ch=getchar; /读入一个字符 printf%c,ch; if ch= T=NULL; ,空格字符表示空树,构造二叉else if .T=BiTNode *mallocsizeofBiTNode exitOVERFLOW; /内存安排胜利 T-data = ch; /生成根结点 CreateBiTreeT-lchild; CreateBiTreeT-rchild; 名师归纳总结 - - - - - - -第 3 页,共 6 页精选学习资料 - - - - - - - - - 算法的时间复杂度分析：O1 2、PreOrderTravers
7、e 算法原理：如二叉树为空,就空操作；否就（1）拜访根结点； （2）先序遍历左子树（3）先序遍历右子树流程图：流程图 存在一个二叉树是否为空树拜访根结点 退出程序先序遍历左子树先序遍历右子树代码描述： Status PreOrderTraverse BiTree T,Status *visitTElemType e /* 功能 :先序遍历二叉树 ;参数 :T 为二叉树的根 ,visit 为对结点的处理方法 */ if T /如根结点不空ifvisitT-data / 拜访根结点if PreOrderTraverseT-lchild,visit /先序遍历根的左子树ifPreOrderTrave
8、rseT-rchild,visit / 先序遍历根的右子树return OK; 算法的时间复杂度分析：On 3、InOrderTraverse 算法原理：如二叉树为空,就空操作；否就（中序遍历右子树；流程图：存在一个二叉树是否为空树1）中序遍历左子树； （2）拜访根结点； （3）中序遍历左子树 退出程序拜访根节点中序遍历右子树名师归纳总结 - - - - - - -第 4 页,共 6 页精选学习资料 - - - - - - - - - 代码描述： Status InOrderTraverse BiTree T,Status *visitTElemType e /* 功能 :中序遍历二叉树 ;参
9、数 :T 为二叉树的根 ,visit 为对结点的处理方法 */ if T /如根结点不空if InOrderTraverseT-lchild,visit / ifvisitT-data / 拜访根结点中序遍历根结点的左子树ifInOrderTraverseT-rchild,visit / 中序遍历根结点的右子树return OK; 算法的时间复杂度分析：On 4、PostOrderTraverse 算法原理：如二叉树为空,就空操作；否就（3）拜访根结点 流程图：存在一个二叉树是否为空树1）后序遍历左子树； （2）后序遍历右子树；后序遍历左子树 退出程序后序遍历右子树拜访根节点代码描述： Sta
10、tus PostOrderTraverse BiTree T,Status *visitTElemType e /* 功能 :后序遍历二叉树 ;参数 :T 为二叉树的根 ,visit 为对结点的处理方法 */ if T /如根结点不空if PostOrderTraverseT-lchild,visit ifPostOrderTraverseT-rchild,visit / ifvisitT-data / 拜访根结点 return OK; 算法的时间复杂度分析：On 五、测试数据和结果1、测试数据 Abc de g f 2、测试结果/后序遍历根结点的左子树 后序遍历根结点的右子树本程序在 VC+ 环境下实现,下面是对以上测试数据的运行结果；1 主菜单显示如下：名师归纳总结 - - - - - - -第 5 页,共 6 页精选学习资料 - - - - - - - - - 2 建立二叉树及各种遍历：六、终止语本设计完成了课题要求的任务,较娴熟地建立了二叉树,实现了各种遍历算法设计了较便利的操作界面；名师归纳总结 - - - - - - -第 6 页,共 6 页