当前位置:首页 >> 工学 >>

二叉树求表达式的值


(一)实验目的
本实验以二叉树的创建与访问算法设计作为实验内容,掌握树型结构的实现方法,培 养解决负责问题的能力。

(二)实验内容
1、编写生成二叉树的函数, 二叉树的元素从键盘输入; 2、编写在二叉树中输入表达方式的函数; 3、编写在二叉树中实现表达方式的值的函数; 4、编写遍历并输出二叉树的函数。

(三 ) 实 验 要 求
1、掌握树型结构的机器内表示; 2、掌握树型结构之上的算法设计与实现; 3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度,阐明产生差异 的原因。

(四 )实 验 设 计 思 路
实验采用递归创建二叉树的表达,并实现了后序遍历二叉数表达式,既逆波兰表达式的 输出,编写函数计算表达式的值,并输出。对实验题目进行细分,逐一实现函数预期的功能,如 下图,先序输入创建二叉树表达式:+*-99##89##2##/66##3## 输出结果:42 +

*

/

3

— —

2

66

99 =

89

内蒙古工业大学信息工程学院

实验报告
(一 )部 分 算 法 流 程 图
1 先序创建二叉树表达式

(五 )程 序 清 单
#include<stdio.h> #include<stdlib.h> #include<string.h> #define len 20 #define NULL 0 struct tree { char data[len]; tree *lchild,*rchild; };

void createtree(tree *&tre)//创 建 二 叉 树 { char ch[len]; 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) {
第 1 页

内蒙古工业大学信息工程学院

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->data[0]>='0'&&tre->data[0]<='9') return atof(tre->data); else { switch(tre->data[0]) { case'*':return solution(tre->lchild)*solution(tre->rchild); case'-':return solution(tre->lchild)-solution(tre->rchild);
第 2 页

内蒙古工业大学信息工程学院

case'+':return solution(tre->lchild)+solution(tre->rchild); case'/':return solution(tre->lchild)/solution(tre->rchild); } } }

int main() { tree *tre; double sum; int ch; do { printf("… … … … … … 选 择 下 面 printf(" 1.先 序 创 建 二 printf(" 2.后 序 遍 利 二 printf(" 3.求 二 叉 数 表 printf(" 4.中 序 遍 利 二 printf(" 5.退 出 二 叉 数

功 叉 叉 达 叉

能 数 数 式 数

… 表 表 的 表

… 达 达 数 达

… … … … … … \n"); 式 \n"); 式 \n"); 值 \n"); 式 \n"); \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("二 叉 树 表 达 式 的 值 为 =%lf\n",sum);break; case 4: printf("中 序 遍 历 的 二 叉 树 : \n"); inordertravers(tre);printf("\n");break; case 5: break; } }while(ch!=5); return 0; }
第 3 页

内蒙古工业大学信息工程学院

(六)实验结果
… … … … … … 选 择 下 面 功 能 … … … … … … … … 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.先 序 创 建 二 叉 数 表 达 式 第 4 页

内蒙古工业大学信息工程学院 2.后 序 遍 利 二 叉 数 表 达 式 3.求 二 叉 数 表 达 式 的 数 值 4.中 序 遍 利 二 叉 数 表 达 式 5.退 出 二 叉 数 … … … … … … … … … … … … … … … … … … … … 4 中 序 遍 历 的 二 叉 树 : 9989-2*+663/ … … … … … … 选 择 下 面 功 能 … … … … … … … … 1.先 序 创 建 二 叉 数 表 达 式 2.后 序 遍 利 二 叉 数 表 达 式 3.求 二 叉 数 表 达 式 的 数 值 4.中 序 遍 利 二 叉 数 表 达 式 5.退 出 二 叉 数 … … … … … … … … … … … … … … … … … … … … 3 二 叉 树 表 达 式 的 值 为 =42.000000 … … … … … … 选 择 下 面 功 能 … … … … … … … … 1.先 序 创 建 二 叉 数 表 达 式 2.后 序 遍 利 二 叉 数 表 达 式 3.求 二 叉 数 表 达 式 的 数 值 4.中 序 遍 利 二 叉 数 表 达 式 5.退 出 二 叉 数 … … … … … … … … … … … … … … … … … … … … 5 请 按 任 意 键 继 续 . . .

(七)实验遇到的问题
二叉树的递归创建只能先序创建吗?若采用中序或后序创建,必须先输入左子树,我 们所定义二叉树往电脑输入时, 必须有终止条件, 比如 if(strcmp(ch,"#")==0)tre=NULL;所以, 一颗二叉树中序或后序建立时,必先输入左子树,而左子树是终止条件,所以,无法建立 一颗二叉树。



5




相关文章:
二叉树求表达式的值.doc
标签: 二叉树| 表达式| 二叉树求表达式的值_工学_高等教育_教育专区。二叉树求表达式的值 采用波兰算法 遍历 并求二叉树表达式的值 ...
数据结构第6章 树习题+答案.doc
数据结构第6章 树习题+答案 - 第六章 树和二叉树 一、选择题 1.已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式为 ABC*+DE/-,其前 缀形式为( D ...
基于二叉树的算术表达式计算与实现.pdf
本文旨在研究表达式向二叉 树的转换,即扫描输入的算术表达式,生成 表达式的二叉树,再以先序遍历此二叉树求表达式的值。为由一种算术表达式得出后 缀、前缀两种...
算术表达式与二叉树.doc
算术表达式二叉树 - 目录 一、系统开发的背景 ......
二叉树表达式求值.doc
二叉树表达式求值 - 二叉树表达式求值 本文由邓志光 8 贡献 //二叉树上的表达式求值算法 #include <stdio.h> #include <stdlib.h> #include
表达式用二叉树表示(1).doc
表达式二叉树表示(1) - 数据结构程序报告(3) 2011.3.29 2. 需求分析: (1)功能:表达式可以用二叉树表示,对于简单的四则运算,请实现以下功能 【1】对于...
波兰算法求二叉树表达式的值.doc
波兰算法求 逆波兰算法 二树表达式的值 是经典的...
后序遍历二叉树实现表达式求值_论文.pdf
后序遍 历二叉 树 实现表达 式求值 . 比传 统 表达式求值方 法有着更高的时 间和空间效率 , 尤其适用于同一表达式对 于多种赋值组合求 值的情况 ,如 判...
树和二叉树数据结构实验报告.doc
实习报告题目:编写一个实现基于二叉树表示的算术表达式 Expression 操作程序 班级:...(BiTree E); /*检查表达式是否还存在没有赋值的变量,以便求算数表达式的值*...
表达式用二叉树表示.doc
表达式二叉树表示 - 对于任意给出的前缀表达式(不带括号)、中缀表达式(可以带括号)或后缀表达式(不带括号),能够在计算机内部构造出一棵表达式二叉树,并且图示出来...
c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课....doc
c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课设报告 - 沈阳理工大学课程设计专用纸 目 题目 录 一.二叉树操作(1)二.算术表达式求 ...
表达式二叉树.doc
{ public: char oper;//数据域,为简便起见,操作数用单个字符代替 Node *...(3)后缀表达式:从前往后扫描 ①碰到操作数把它赋给相应的新建立的二叉树结点...
数据结构实验二叉树.doc
求叶子结点个数算法和树的深度算法; 3、根据表达式建立相应的二叉树,生成表达式树的模块; 4、根据表达式树,求出表达式值,生成求值模块; 5、程序运行效果,测试数据...
第5章 树和二叉树(新)_图文.ppt
利用二叉树求解表达式的值二叉树表示表达式的递归定义如下: (1)若表达式为数或简单变量,则相应二叉 树中仅有一个根结点,其数据域存放该表达 式信息; (2)若...
四则运算表达式求值(栈+二叉树,c++版).doc
运算表达式求值(栈+二叉树,c++版)_计算机软件及应用_IT/计算机_专业资料。数据结构实验报告 HUNAN UNIVERSITY 课程实习报告 题 目: 四运算表达式求值 ...
表达式与二叉树的相互转换_图文.pdf
表达式二叉树的相互转换 - ISSN 10093044 E-mail:kfy
表达式二叉树上机报告.doc
(1)功能:表达式可以用二叉树表示,对于简单的四则运算,请实现以下功能 【1】...数据: (1)请输入表达式类型,前缀表达式输入-1,中缀表达式输入 0,后缀表达式输入...
《数据结构》复习题-第6章-树和二叉树.doc
数据结构》复习题-第6章-树和二叉树_教育学_高等教育_教育专区。第六章 树和二叉树 一、选择题 1.已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式为...
C语言二叉树运算.doc
=NULL) copytree(T->rchild,s->rchild); else s->rchild=NULL; s->data=T->data; } } int Calculate(BiTree T)//计算表达式二叉树的值 { //后序...
表达式类型的实现(二叉树).doc
二叉树实现前缀表达式转换为中缀表达式,并对其计算,求复合表达式与及对变量赋值等。数据结构实验。用二叉树实现前缀表达式转换为中缀表达式,并对其计算,求复合表达式与...
更多相关标签: