下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1、 实验目的(1)掌握二叉树的数组存储方法。(2)掌握二叉树的非线性特点、递归特点和动态特性。(3)复习二叉树遍历算法和标识符树的概念。(4)利用标识符树的后序计算表达式的值(运算只涉及+、-、*、/)。2、 实验内容(1)定义二叉树的结构如下:struct tree / 定义结构体 int data; / 定义一个整型数据域 struct tree *left; / 定义左子树指针 struct tree *right; / 定义右子树指针;typedef struct tree btnode; / 树的结构类型+*/2363 标识符树typedef btnode *bt; / 定义树结点
2、的指针类型(2)把算术表达式2*3+6/3的标识符树(见图7-35)存入一维数组。(3)求标识符树的前序遍历、中序遍历和后序遍历的序列。(4)以后序计算标识符树的值。3、 实验要求(1) 用C(C+)语言完成算法设计和程序设计。(2) 上机调试通过实验程序。(3) 输入数据,检验程序运行结果。(4) 给出具体的算法分析,包括时间复杂度和空间复杂度等。(5) 撰写实验报告(把输入实验数据及运行结果用抓图的形式粘贴到实验报告上)。4、 实验步骤与源程序 实验步骤先从具体的问题中抽象出适当的数学模型,然后设计出相应的算法,其中,需要设计一个主函数来实现菜单的输出,设计另外五个函数来求分别实现新建,先
3、序遍历输出,中序遍历输出,后序遍历输出,表达式求值,最后,串接函数,并调试程序,多次调试后,发现没有问题,得出实验结果,并截图。 源代码#include#includestruct tree / 树的结构声明char data; / 结点数据 struct tree *left; / 指向左子树的指针 struct tree *right; / 指向右子树的指针;typedef struct tree treenode; / 树的结构新类型typedef treenode *btree; / 声明树结点指针类型int n; / n计算字符串长度btree createbtree(int *da
4、ta,int pos) / 创建表达式二叉树 btree newnode; / 新结点指针 if (datapos=0|posn) / 终止条件 return NULL; else newnode=new treenode; / 创建新结点内存 newnode-data=datapos; / 创建结点内容 newnode-left=createbtree(data,2*pos); / 创建左子树递归调用 newnode-right=createbtree(data,2*pos+1); / 创建右子树递归调用return newnode;void preorder(btree ptr) / 表达
5、式二叉树前序输出 if(ptr!=NULL) / 终止条件 printf( %c,ptr-data); / 输出结点内容 preorder(ptr-left); / 左子树 preorder(ptr-right); / 右子树 void inorder(btree ptr) / 表达式二叉树中序输出 if (ptr!=NULL) / 终止条件 inorder(ptr-left); / 左子树 printf( %c,ptr-data); / 输出结点内容 inorder(ptr-right); / 右子树 void postorder(btree ptr) / 表达式二叉树后序输出 if(ptr
6、!=NULL) / 右子树 postorder(ptr-left); / 左子树 postorder(ptr-right); / 右子树 printf( %c,ptr-data); / 输出结点内容 int cal(btree ptr) / 表达式二叉树后序计值 int operand1=0; / 定义操作数变量1 int operand2=0; / 定义操作数变量2 int getvalue(int op,int operand1,int operand2); / 对getvalue函数作声明 if (ptr-left=NULL & ptr-right=NULL) / 终止条件 return
7、 ptr-data-48; operand1=cal(ptr-left); / 左子树 operand2=cal(ptr-right); / 右子树 return getvalue(ptr-data,operand1,operand2); int getvalue(int op,int operand1,int operand2) / 计算二叉树表达式值 switch(char)op) case*:return(operand1*operand2); case/:return(operand1/operand2); case+:return(operand1+operand2); case-:
8、return(operand1-operand2); void main() / 主程序 btree root=NULL; / 表达式二叉树指针 int result,k=1; / 定义输出结果变量 int data100= ; char ch; printf(按层次输入标识符树的结点数据,以回车键表示结束n); while(ch=getchar()!=n) datak+=ch; datak=0; n=k-1; root=createbtree(data,1); / 创建表达式二叉树 printf(tn 前序表达式:); preorder(root); / 前序输出二叉树 printf(tnn 中序表达式:); inorder(root); / 中序输出二叉树 printf(tnn 后序表达式:); postorder(root); / 后序输出二叉树 result=cal(root); / 计算 printf(tnn 表达式结果是:%dnn,result); / 输出计算结果5、 测试数据与实验结果(可以抓图粘贴)6、 结果分析与实验体会本次实验是书中
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2030年中国白朗姆市场竞争状况与营销趋势预测报告
- 2024年农村建房合同样本
- 天津市劳动合同试用期
- 2024-2030年中国电话单机项目风险评估报告
- 2023年上半年儿科护理学(二)全国自考考题含解析
- 2024年铜基、镍基钎料项目合作计划书
- 2024-2030年中国电流表行业市场发展趋势与前景展望战略分析报告
- 2024-2030年中国电子计算机设备制造行业前景趋势展望及投资潜力评估报告
- 2024-2030年中国电子玻璃行业需求趋势及项目可行性分析报告
- 2024-2030年中国电子微电机制造行业市场深度调研及发展趋势与投资前景研究报告
- 个人在廉洁自律方面存在的问题及整改措施
- 预防事故和职业病的措施及应注意的安全事项
- 2024年建筑继续教育-二级建造师继续教育历年考试高频考点试题附带答案
- 不倒翁说课稿课件
- 脐带间充质干细胞制备及质量控制规范(征求意见稿)
- 楼顶发光字采购安装投标方案
- 如何制定适合自己的专升本学习计划
- 乙肝病毒感染知识教学设计
- 创业法学仙乐牌加盟创业团队成员合作框架协议
- 人教新起点小学四年级英语下册同步练习试题(全册)
- 技术论文培训课件
评论
0/150
提交评论