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

二叉树求表达式的值


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

(二)实验内容
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




相关文章:
二叉树表达式求值
二​叉​树​表​达​式​求​值二叉树表达式求值 本文由邓志光 8 贡献 //二叉树上的表达式求值算法 #include <stdio.h> #include <stdlib.h> #...
二叉树表达式求值
二叉树表达式求值_电脑基础知识_IT/计算机_专业资料。数据结构,二叉树表达式求值,代码今日推荐 157份文档 2015国家公务员考试备战攻略 ...
表达式二叉树代码
表达式二叉树代码_计算机软件及应用_IT/计算机_专业资料。#include<stdio.h> #...='/') {printf("\n 表达式中仍存在变量没有赋值!没法求出表达式的值!");...
波兰算法求二叉树表达式的值
波​兰​算​法​求​ ​ ​逆​波​兰​算​法​ ​二​​树​表​达​式​的​值​ ​是​经​典​的​...
表达式用二叉树表示
表达式二叉树表示 - 对于任意给出的前缀表达式(不带括号)、中缀表达式(可以带括号)或后缀表达式(不带括号),能够在计算机内部构造出一棵表达式二叉树,并且图示出来...
四则运算表达式求值(栈+二叉树,c++版)
运算表达式求值(栈+二叉树,c++版)_计算机软件及应用_IT/计算机_专业资料。数据结构——实验报告 HUNAN UNIVERSITY 课程实习报告 题 目: 四运算表达式求值 ...
树和二叉树——数据结构实验报告
实习报告题目:编写一个实现基于二叉树表示的算术表达式 Expression 操作程序 班级:...(BiTree E); /*检查表达式是否还存在没有赋值的变量,以便求算数表达式的值*...
二叉树的应用-代数表达式实现实验报告
的每个结点包括一个运算 符或操作数,代数表达式中只包含+、-、*、/和整数且没有错误,要求按照四则 运算法则构造二叉树,然后由对应的二叉树计算对应的表达式的值...
15算术表达式与二叉树
15算术表达式二叉树_数学_自然科学_专业资料。《数据结构与算法》课程设计任务书题目: 算术表达式二叉树 学生姓名: 班级: 题目类型:软件工程(R) 指导教师: ...
算术表达式与二叉树
算术表达式二叉树 - 目录 一、系统开发的背景 ......
更多相关标签: