免费预览已结束,剩余1页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
内蒙古工业大学信息工程学院(一)实验目的 本实验以二叉树的创建与访问算法设计作为实验内容,掌握树型结构的实现方法,培养解决负责问题的能力。(二)实验内容 1、编写生成二叉树的函数, 二叉树的元素从键盘输入;2、编写在二叉树中输入表达方式的函数;3、编写在二叉树中实现表达方式的值的函数;4、编写遍历并输出二叉树的函数。(三)实验要求1、掌握树型结构的机器内表示;2、掌握树型结构之上的算法设计与实现;3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度,阐明产生差异的原因。(四)实验设计思路 实验采用递归创建二叉树的表达,并实现了后序遍历二叉数表达式,既逆波兰表达式的输出,编写函数计算表达式的值,并输出。对实验题目进行细分,逐一实现函数预期的功能,如下图,先序输入创建二叉树表达式:+*-99#89#2#/66#3#输出结果:4+2 /*662399=89 实验报告(一)部分算法流程图 1先序创建二叉树表达式(五)程序清单#include#include#include#define len 20#define NULL 0struct treechar datalen;tree *lchild,*rchild;void createtree(tree *&tre)/创建二叉树char chlen; scanf(%s,ch);getchar();if(strcmp(ch,#)=0)tre=NULL;else tre=(tree *)malloc(sizeof(tree); strcpy(tre-data,ch); createtree(tre-lchild); createtree(tre-rchild);void inputtree(tree *tre)/输出二叉树if(tre!=NULL)printf(%s,tre-data);if(tre-lchild!=NULL|tre-rchild!=NULL)printf();inputtree(tre-lchild);if(tre-rchild!=NULL)printf(,);inputtree(tre-rchild);printf();void traversetree(tree *tre)/后续遍历 if(tre!=NULL) traversetree(tre-lchild); traversetree(tre-rchild); printf(%s,tre-data); void inordertravers(tree *tre)/中续遍历 if(tre!=NULL) traversetree(tre-lchild); printf(%s,tre-data); traversetree(tre-rchild); double solution(tree *tre)/二叉树表达式求值if(tre-lchild=NULL&tre-rchild=NULL&tre-data0=0&tre-data0data); elseswitch(tre-data0) case*:return solution(tre-lchild)*solution(tre-rchild); case-:return solution(tre-lchild)-solution(tre-rchild); case+:return solution(tre-lchild)+solution(tre-rchild); case/:returnsolution(tre-lchild)/solution(tre-rchild); int main()tree *tre;double sum; int ch;doprintf(选择下面功能n);printf(1.先序创建二叉数表达式 n);printf(2.后序遍利二叉数表达式 n);printf(3.求二叉数表达式的数值 n);printf(4.中序遍利二叉数表达式 n);printf( 5.退出二叉数 n);printf(n);scanf(%d,&ch);switch(ch) case 1: printf(输入创建的二叉树:n);getchar(); createtree(tre);inputtree(tre); printf(n);break; case 2: printf(后序遍历的二叉树:n); traversetree(tre);printf(n);break; case 3: sum=solution(tre);printf(二叉树表达式的值为=%lfn,sum);break; case 4: printf(中序遍历的二叉树:n); inordertravers(tre);printf(n);break; case 5: break;while(ch!=5); return 0;(六)实验结果选择下面功能1.先序创建二叉数表达式2.后序遍利二叉数表达式3.求二叉数表达式的数值4.中序遍利二叉数表达式 5.退出二叉数1输入创建的二叉树:+*-99#89#2#/66#3#+(*(-(99,89),2),/(66,3)选择下面功能1.先序创建二叉数表达式2.后序遍利二叉数表达式3.求二叉数表达式的数值4.中序遍利二叉数表达式 5.退出二叉数2后序遍历的二叉树:9989-2*663/+选择下面功能1.先序创建二叉数表达式2.后序遍利二叉数表达式3.求二叉数表达式的数值4.中序遍利二叉数表达式 5.退出二叉数4中序遍历的二叉树:9989-2*+663/选择下面功能1.先序创建二叉数表达式2.后序遍利二叉数表达式3.求二叉数表达式的数值4.中序遍利二叉数表达式 5.退出二叉数3二叉树表达式的值为=42.000000选择下面功能1.先序创建二叉数表达式2.后序遍利二叉数表达式3.求二叉数表达式的数值4.中序遍利二叉数表达式 5.退出二叉数5请按任意键继续. . .(七)实验遇到的问题 二叉树的递归创建只能先序
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论