二叉树求表达式的值.doc

《二叉树求表达式的值.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内蒙古工业大学信息工程学院（一）实验目的本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。（二）实验内容1、编写生成二叉树的函数，二叉树的元素从键盘输入；2、编写在二叉树中输入表达方式的函数；3、编写在二叉树中实现表达方式的值的函数；4、编写遍历并输出二叉树的函数。(三）实验要求1、掌握树型结构的机器内表示；2、掌握树型结构之上的算法设计与实现；3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。(四)实验设计思路实验采用递归创建二叉树的表达,并实现了后序遍历二叉数表达式,既逆波兰表达式的输出,编

2、写函数计算表达式的值,并输出。对实验题目进行细分,逐一实现函数预期的功能,如下图，先序输入创建二叉树表达式:+*-99##89##2##/66##3##输出结果：4+2/*66——2399=89第5页内蒙古工业大学信息工程学院实验报告(一)部分算法流程图1先序创建二叉树表达式(五)程序清单#include#include#include#definelen20#defineNULL0structtree{chardata[len];tree*lchild,*rchild;};voidcreatetree(tree*&

3、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

4、

5、tre->rchild!=

6、NULL){第5页内蒙古工业大学信息工程学院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(

7、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)*solut

8、ion(tre->rchild);case'-':returnsolution(tre->lchild)-solution(tre->rchild);第5页内蒙古工业大学信息工程学院case'+':returnsolution(tre->lchild)+solution(tre->rchild);case'/':returnsolution(tre->lchild)/solution(tre->rchild);}}}intmain(){tree*tre;doublesum;intch;do{printf("………………选择下面功能……………………");printf("　

9、　　　1.先序创建二叉数表达式　　");printf("　　　　2.后序遍利二叉数表达式　　");printf("　　　　3.求二叉数表达式的数值　　");printf("　　　　4.中序遍利二叉数表达式　　");printf("　　5.退出二叉数　　");printf("……………………………………………………");scanf("%d",&ch);switch(ch){case1:printf("输入创建的二叉树：");getchar();createtree(tre);inputtr