二叉树求表达式的值
（一）实验目的
本实验以二叉树的创建与访问算法设计作为实验容，掌握树型结构的实现方法，培养
解决负责问题的能力。
（二）实验容
1、编写生成二叉树的函数，二叉树的元素从键盘输入；
2、编写在二叉树中输入表达方式的函数；
3、编写在二叉树中实现表达方式的值的函数；
4、编写遍历并输出二叉树的函数。
（三）实验要求
1、掌握树型结构的机器表示；
2、掌握树型结构之上的算法设计与实现；
3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异
的原因。
（四）实验设计思路
实验采用递归创建二叉树的表达，并实现了后序遍历二叉数表达式，既逆波兰表达式的输出，编写函数计算表达式的值，并输出。对实验题目进行细分，逐一实现函数预期的功能，如
下图，先序输入创建二叉树表达式：+*-99##89##2##/66##3##
输出结果：42
内蒙古工业大学信息工程学院
实验报告
（一）部分算法流程图
1先序创建二叉树表达式
（五）程序清单
# i n c l u d e< st d i o. h >
# i n c l u d e< st d l i b. h >
#in cludevstri ng. h >
# d ef i ne len 20
#d efi n e NULL 0 st ru ct tree
{
char d at a[ l e n ];
tree * l ch i l d ,* r ch i l d ;
};
void createtree(tree* & tre)/ / 创建二叉树
{
char ch [ l e n ];
scanf (” %s" , ch);
g et ch ar ();
if(strcmp(ch,"#") = = 0)t r e= NULL;
else
{
t r e= (tree *)malloc(sizeof(tree)); st rcpy (tre- >
d at a,ch );
cr eatet ree(t re- > l ch i l d );
createtree(tre - > r ch i l d);
}
} void in putt ree(tree *t re)// 输出二叉树{
if(tre!= NULL)
{
prin t f (" %s", t r e - > d at a);
i f (t r e- > lchild!=NULL||tre- > r ch i l d !N U LL)
{
pri ntf(" (");
in puttree(tre - > Ichild);
i f (t r e - > rch i Id ! = N ULL)pri n t f (",");
in p u tt ree(t re- > rchi Id);
pri ntf(")");
}
}
} void t r av e r se t r e e(t re e *t re)// 后续遍历{ if(tre!= N ULL)
{
t raver set ree(t re- > l ch i l d );
t raver set ree(t re- > r ch i l d );
p ri n tf (" %s" ,t re- > d at a);
}
} void in ordertravers(tree*tre)/ / 中续遍历
{
内蒙古工业大学信息工程学院
if(tre!= N ULL)
t raver set ree(t re- > Ichild); p ri n tf (" %s" ,t re- > d at a); t raver set ree(t re- > r ch i l d ); }
} double so l ut io n(tree * t r e)/ / 二叉树表达式求值 {
if(tre- > l ch ild = = N ULL && tre- >rchild = = NULL && tre->data[O]> = 'O' & & t re- > d at a
[ 0 ] < = ' 9')
r et u rn at o f(t re- > d at a);
e l se {
sw i tch (t re- > d at a[0]) {
case'*':retur n so l u t i on( tre - > l ch i l d )* so l u t i on( t r e - case' - ' :r et u r n so l u t i on( tre- > l ch i l d )- so l u t i on( t r e - case' + ' : re t u r n so l u t i on( tre - > l c h i l d) + sol u t i on( t re case'/': ret u rn soluti on( tre - >lchild)/soluti on( t re - > rchild);
> rch ild); > rc h ild); -> r c h i l d );
内蒙古工业大学信息工程学院
{
i n t m a i n () {
tree * t re ; double sum; i n t ch; d o
sca nf ("%d"，&ch); sw i tch(ch) case 1 :
p r i n t f (” 输入创建的二叉树： n " );g etchar();
createtree(tre) ;in puttree(tre);
p r i n t f (" n ") ;b r e a k ;
case 2 :
p r i n t f ("后序遍历的二叉树：n ");
t raver set ree(t re) ;p r in t f (" n ”)；break;
case 3 : ri ntf (" ............. ...... 选择下面功能 ................... …n ");
ri ntf (" 1.先序创建二叉数表达式
n " ri ntf(" 2.后序遍利二叉数表达式
n " ri ntf(" 3.求二叉数表达式的数值
n " ri ntf(" 4.中序遍利二叉数表达式
n " ri ntf("
5.退出二叉数
n" ri ntf(" .............
… n")
P ); P );
P ); P );
P ); P P