2022年二叉树实验报告 .pdf

《2022年二叉树实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年二叉树实验报告 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计报告专业计算机科学与技术班级3 班姓名学号指导教师起止时间2012.122013.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 CreateBiTree(BiTree &T);二叉树的前序遍历函数Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType); 二叉树的中序遍历函数Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType);二叉树的后序遍历函数Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType) ；最简单

4、的visit 函数 Status Visit(TElemType e);（三）函数调用关系程序的主要结构（函数调用关系）如下图所示。Main() Visit()CreateBiTree() PreOrderTraverse() InOrderTraverse() PostOrderTraverse() 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 6 页其中 main()是主函数，它进行菜单驱动。BiTree T; int n=0; printf( 创建二叉树，请按前序序列输入各节点值：n); CreateBiTree(T); pri

5、ntf(n); printf( 已成功创建二叉树n); PreOrderTraverse( T,Visit); printf(n); InOrderTraverse(T,Visit); printf(n); PostOrderTraverse(T,Visit); printf(n); （四）文件结构1、tree.h：二叉树相关的定义与声明2、tree.cpp：二叉树运算的实现5、mn.cpp：主函数（五）各函数的算法设计1、CreateBiTree() 算法原理：按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表流程图：输入一个字符申请内存是否成功生成根结点退出程序构造

6、左子树构造右子树代码描述： void CreateBiTree(BiTree &T) char ch; ch=getchar(); /读入一个字符printf(%c,ch); if (ch= ) T=NULL; else if (!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); /内存分配成功T-data = ch; /生成根结点CreateBiTree(T-lchild); CreateBiTree(T-rchild); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 6 页

7、算法的时间复杂度分析：O(1) 2、PreOrderTraverse ()算法原理：若二叉树为空，则空操作；否则（1）访问根结点； （2）先序遍历左子树（3）先序遍历右子树流程图：流程图存在一个二叉树是否为空树访问根结点退出程序先序遍历左子树先序遍历右子树代码描述： Status PreOrderTraverse (BiTree T,Status (*visit)(TElemType e) /* 功能 :先序遍历二叉树;参数 :T 为二叉树的根,visit 为对结点的处理方法*/ if (T) /若根结点不空if(visit(T-data) / 访问根结点if (PreOrderTravers

8、e(T-lchild,visit) /先序遍历根的左子树if(PreOrderTraverse(T-rchild,visit) /先序遍历根的右子树return OK; 算法的时间复杂度分析：O(n) 3、InOrderTraverse ()算法原理：若二叉树为空，则空操作；否则（1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树；流程图：存在一个二叉树是否为空树中序遍历左子树退出程序访问根节点中序遍历右子树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 6 页代码描述： Status InOrderTraverse (Bi

9、Tree T,Status (*visit)(TElemType e) /*功能 :中序遍历二叉树 ;参数 :T 为二叉树的根 ,visit 为对结点的处理方法*/ if (T) /若根结点不空if (InOrderTraverse(T-lchild,visit) /中序遍历根结点的左子树if(visit(T-data) / 访问根结点if(InOrderTraverse(T-rchild,visit) /中序遍历根结点的右子树return OK; 算法的时间复杂度分析：O(n) 4、PostOrderTraverse() 算法原理：若二叉树为空，则空操作；否则（1）后序遍历左子树； （2）后

10、序遍历右子树；（3）访问根结点流程图：存在一个二叉树是否为空树后序遍历左子树退出程序后序遍历右子树访问根节点代码描述： Status PostOrderTraverse (BiTree T,Status (*visit)(TElemType e) /* 功能 :后序遍历二叉树;参数 :T 为二叉树的根,visit 为对结点的处理方法*/ if (T) /若根结点不空if (PostOrderTraverse(T-lchild,visit) /后序遍历根结点的左子树if(PostOrderTraverse(T-rchild,visit) /后序遍历根结点的右子树if(visit(T-data) / 访问根结点return OK; 算法的时间复杂度分析：O(n) 五、测试数据和结果1、测试数据 Abc de g f 2、测试结果本程序在VC+ 环境下实现，下面是对以上测试数据的运行结果。(1) 主菜单显示如下：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页(2) 建立二叉树及各种遍历：六、结束语本设计完成了课题要求的任务，较熟练地建立了二叉树，实现了各种遍历算法设计了较便捷的操作界面。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页