二叉树求表达式的值

（一）实验目的本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。（二）实验内容1、编写生成二叉树的函数，二叉树的元素从键盘输入；2、编写在二叉树中输入表达方式的函数；3、编写在二叉树中实现表达方式的值的函数；4、编写遍历并输出二叉树的函数。(三）实验要求1、掌握树型结构的机器内表示；2、掌握树型结构之上的算法设计与实现；3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。(四)实验设计思路实验采用递归创建二叉树的表达,并实现了后序遍历二叉数表达式,既逆波兰表达式的输出,编写函数计算表达式的值,并输出。对实验题目进行细分,逐一实现函数预期的功能,如下图，先序输入创建二叉树表达式:+*-99##89##2##/66##3##输出结果：42+*3/662——99=89内蒙古工业大学信息工程学院第1页实验报告(一)部分算法流程图1先序创建二叉树表达式(五)程序清单#includestdio.h#includestdlib.h#includestring.h#definelen20#defineNULL0structtree{chardata[len];tree*lchild,*rchild;};voidcreatetree(tree*&tre)//创建二叉树{charch[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);}}voidinputtree(tree*tre)//输出二叉树{if(tre!=NULL){printf(%s,tre-data);if(tre-lchild!=NULL||tre-rchild!=NULL){内蒙古工业大学信息工程学院第2页printf(();inputtree(tre-lchild);if(tre-rchild!=NULL)printf(,);inputtree(tre-rchild);printf());}}}voidtraversetree(tree*tre)//后续遍历{if(tre!=NULL){traversetree(tre-lchild);traversetree(tre-rchild);printf(%s,tre-data);}}voidinordertravers(tree*tre)//中续遍历{if(tre!=NULL){traversetree(tre-lchild);printf(%s,tre-data);traversetree(tre-rchild);}}doublesolution(tree*tre)//二叉树表达式求值{if(tre-lchild==NULL&&tre-rchild==NULL&&tre-data[0]='0'&&tre-data[0]='9')returnatof(tre-data);else{switch(tre-data[0]){case'*':returnsolution(tre-lchild)*solution(tre-rchild);case'-':returnsolution(tre-lchild)-solution(tre-rchild);内蒙古工业大学信息工程学院第3页case'+':returnsolution(tre-lchild)+solution(tre-rchild);case'/':returnsolution(tre-lchild)/solution(tre-rchild);}}}intmain(){tree*tre;doublesum;intch;do{printf(………………选择下面功能……………………\n);printf(1.先序创建二叉数表达式\n);printf(2.后序遍利二叉数表达式\n);printf(3.求二叉数表达式的数值\n);printf(4.中序遍利二叉数表达式\n);printf(5.退出二叉数\n);printf(……………………………………………………\n);scanf(%d,&ch);switch(ch){case1:printf(输入创建的二叉树：\n);getchar();createtree(tre);inputtree(tre);printf(\n);break;case2:printf(后序遍历的二叉树：\n);traversetree(tre);printf(\n);break;case3:sum=solution(tre);printf(二叉树表达式的值为=%lf\n,sum);break;case4:printf(中序遍历的二叉树：\n);inordertravers(tre);printf(\n);break;case5:break;}}while(ch!=5);return0;}内蒙古工业大学信息工程学院第4页（六）实验结果………………选择下面功能……………………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.先序创建二叉数表达式内蒙古工业大学信息工程学院第5页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;所以，一颗二叉树中序或后序建立时，必先输入左子树，而左子树是终止条件，所以，无法建立一颗二叉树。