《二叉树求表达式的值》由会员分享，可在线阅读，更多相关《二叉树求表达式的值（6页珍藏版）》请在金锄头文库上搜索。
1、（一）实验目的本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。（二）实验内容 1、编写生成二叉树的函数， 二叉树的元素从键盘输入；2、编写在二叉树中输入表达方式的函数；3、编写在二叉树中实现表达方式的值的函数；4、编写遍历并输出二叉树的函数。(三）实验要求1、掌握树型结构的机器内表示；2、掌握树型结构之上的算法设计与实现；3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。(四 )实验设计思路实验采用递归创建二叉树的表达,并实现了后序遍历二叉数表达式,既逆波兰表达式的输出,编写函数计算表达式的值,并输出。对实验题目
2、进行细分,逐一实现函数预期的功能,如下图，先序输入创建二叉树表达式:+*-99#89#2#/66#3#输出结果：42 +*3/662 99 =89内蒙古工业大学信息工程学院第 1 页实验报告实验报告(一 )部分 算法 流程图1 先序创建二叉树表达式(五 )程序清单# #i in nc cl lu ud de e # #i in nc cl lu ud de e # #i in nc cl lu ud de e # #d de ef fi in ne e l le en n 2 20 0 # #d de ef fi in ne e N NU UL LL L 0 0s st tr ru uc ct
3、 t t tr re ee e c ch ha ar r d da at ta a l le en n ; ; t tr re ee e * *l lc ch hi il ld d, ,* *r rc ch hi il ld d; ; ; ;v vo oi id d c cr re ea at te et tr re ee e( (t tr re ee e * * ;s sc ca an nf f( (“ “% %s s“ “, ,c ch h) ); ; g ge et tc ch ha ar r( () ); ; i if f( (s st tr rc cm mp p( (c ch h,
4、,“ “# #“ “) )= = =0 0) )t tr re e= =N NU UL LL L; ; e el ls se e t tr re e= =( (t tr re ee e * *) )m ma al ll lo oc c( (s si iz ze eo of f( (t tr re ee e) ) ); ;s st tr rc cp py y( (t tr re e- - d da at ta a, ,c ch h) ); ;c cr re ea at te et tr re ee e( (t tr re e- - l lc ch hi il ld d) ); ;c cr re
5、ea at te et tr re ee e( (t tr re e- - r rc ch hi il ld d) ); ; v vo oi id d i in np pu ut tt tr re ee e( (t tr re ee e * *t tr re e) )/ / /输输出出二二叉叉树树 i if f( (t tr re e! != =N NU UL LL L) ) p pr ri in nt tf f( (“ “% %s s“ “, ,t tr re e- - d da at ta a) ); ; i if f( (t tr re e- - l lc ch hi il ld d!
6、!= =N NU UL LL L| | |t tr re e- - r rc ch hi il ld d! != =N NU UL LL L) ) 内蒙古工业大学信息工程学院第 2 页p pr ri in nt tf f( (“ “( (“ “) ); ; i in np pu ut tt tr re ee e( (t tr re e- - l lc ch hi il ld d) ); ; i if f( (t tr re e- - r rc ch hi il ld d! != =N NU UL LL L) )p pr ri in nt tf f( (“ “, ,“ “) ); ; i in
7、np pu ut tt tr re ee e( (t tr re e- - r rc ch hi il ld d) ); ; p pr ri in nt tf f( (“ “) )“ “) ); ; v vo oi id d t tr ra av ve er rs se et tr re ee e( (t tr re ee e * *t tr re e) )/ / /后后续续遍遍历历 i if f( (t tr re e! != =N NU UL LL L) ) t tr ra av ve er rs se et tr re ee e( (t tr re e- - l lc ch hi il
8、ld d) ); ;t tr ra av ve er rs se et tr re ee e( (t tr re e- - r rc ch hi il ld d) ); ;p pr ri in nt tf f( (“ “% %s s“ “, ,t tr re e- - d da at ta a) ); ; v vo oi id d i in no or rd de er rt tr ra av ve er rs s( (t tr re ee e * *t tr re e) )/ / /中中续续遍遍历历 i if f( (t tr re e! != =N NU UL LL L) ) t tr r
9、a av ve er rs se et tr re ee e( (t tr re e- - l lc ch hi il ld d) ); ;p pr ri in nt tf f( (“ “% %s s“ “, ,t tr re e- - d da at ta a) ); ;t tr ra av ve er rs se et tr re ee e( (t tr re e- - r rc ch hi il ld d) ); ; d do ou ub bl le e s so ol lu ut ti io on n( (t tr re ee e * *t tr re e) )/ / /二二叉叉树树表
10、表达达式式求求值值 i if f( (t tr re e- - l lc ch hi il ld d= = =N NU UL LL L ;e el ls se e s sw wi it tc ch h( (t tr re e- - d da at ta a 0 0 ) ) c ca as se e * * : :r re et tu ur rn n s so ol lu ut ti io on n( (t tr re e- - l lc ch hi il ld d) )* *s so ol lu ut ti io on n( (t tr re e- - r rc ch hi il ld d)
11、); ; c ca as se e - - : :r re et tu ur rn n s so ol lu ut ti io on n( (t tr re e- - l lc ch hi il ld d) )- -s so ol lu ut ti io on n( (t tr re e- - r rc ch hi il ld d) ); ; 内蒙古工业大学信息工程学院第 3 页c ca as se e + + : :r re et tu ur rn n s so ol lu ut ti io on n( (t tr re e- - l lc ch hi il ld d) )+ +s so o
12、l lu ut ti io on n( (t tr re e- - r rc ch hi il ld d) ); ; c ca as se e / / : :r re et tu ur rn n s so ol lu ut ti io on n( (t tr re e- - l lc ch hi il ld d) )/ /s so ol lu ut ti io on n( (t tr re e- - r rc ch hi il ld d) ); ; i in nt t m ma ai in n( () ) t tr re ee e * *t tr re e; ; d do ou ub bl l
13、e e s su um m; ;i in nt t c ch h; ; d do o p pr ri in nt tf f( (“ “选选择择下下面面功功能能 n n“ “) ); ; p pr ri in nt tf f( (“ “ 1 1. .先先序序创创建建二二叉叉数数表表达达式式 n n“ “) ); ; p pr ri in nt tf f( (“ “ 2 2. .后后序序遍遍利利二二叉叉数数表表达达式式 n n“ “) ); ; p pr ri in nt tf f( (“ “ 3 3. .求求二二叉叉数数表表达达式式的的数数值值 n n“ “) ); ; p pr ri in n
14、t tf f( (“ “ 4 4. .中中序序遍遍利利二二叉叉数数表表达达式式 n n“ “) ); ; p pr ri in nt tf f( (“ “ 5 5. .退退出出二二叉叉数数 n n“ “) ); ;p pr ri in nt tf f( (“ “ n n“ “) ); ;s sc ca an nf f( (“ “% %d d“ “, , ; s sw wi it tc ch h( (c ch h) ) c ca as se e 1 1: :p pr ri in nt tf f( (“ “输输入入创创建建的的二二叉叉树树： n n“ “) ); ;g ge et tc ch ha ar r( () ); ;c cr re ea at te et tr re ee e( (t tr re e) ); ;i in np pu ut tt tr re ee e( (t tr re e) ); ;p pr ri in nt tf f( (“ “ n n“ “) ); ;b br re ea ak k; ;c ca as se e 2 2: : p pr ri in nt tf f( (“ “后后序序遍遍历历的的二二叉叉树树：
