二叉树求表达式的值.doc

内蒙古工业大学信息工程学院（一）实验目的 本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。（二）实验内容 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请按任意键继续. . .（七）实验遇到的问题 二叉树的递归创建只能先序