（一）实验目的
本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。
（二）实验内容
1、编写生成二叉树的函数， 二叉树的元素从键盘输入；
2、编写在二叉树中输入表达方式的函数；
3、编写在二叉树中实现表达方式的值的函数；
4、编写遍历并输出二叉树的函数。
(三）实验要求
1、掌握树型结构的机器内表示；
2、掌握树型结构之上的算法设计与实现；
3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。
(四) 实验设计思路
实验采用递归创建二叉树的表达, 并实现了后序遍历二叉数表达式, 既逆波兰表达式的输出, 编写函数计算表达式的值, 并输出。对实验题目进行细分, 逐一实现函数预期的功能, 如下图，先序输入创建二叉树表达式:+*-99##89##2##/66##3##
实验报告
(一) 部分算法流程图
1先序创建二叉树表达式
(五) 程序清单
#i n c l u d e
#i n c l u d e
#i n c l u d e
#d e f i n e l e n 20
#d e f i n e N U L L 0
s t r u c t t r e e
{
c h a r d a t a [l e n ];
t r e e *l c h i l d , *r c h i l d ;
};
v o i d c r e a t e t r e e (t r e e *&t r e ) //创建二叉树
{
c h a r c h [l e n ];
s c a n f (" %s " , c h ) ;
g e t c h a r () ;
i f (s t r c m p (c h , " #" ) ==0) t r e =N U L L ;
e l s e
{
t r e =(t r e e *) m a l l o c (s i z e o f (t r e e ) ) ;
s t r c p y (t r e ->d a t a , c h ) ;
c r e a t e t r e e (t r e ->l c h i l d ) ;
c r e a t e t r e e (t r e ->r c h i l d ) ;
}
}
v o i d i n p u t t r e e (t r e e *t r e ) //输出二叉树
{
i f (t r e ! =N U L L )
{
p r i n t f (" %s " , t r e ->d a t a ) ;
i f (t r e ->l c h i l d ! =N U L L ||t r e ->r c h i l d ! =N U L L )
{
p r i n t f (" (" ) ;
i n p u t t r e e (t r e ->l c h i l d ) ;
i f (t r e ->r c h i l d ! =N U L L ) p r i n t f (" , " ) ;
i n p u t t r e e (t r e ->r c h i l d ) ;
p r i n t f (" ) " ) ;
}
}
}
v o i d t r a v e r s e t r e e (t r e e *t r e ) //后续遍历
{
i f (t r e ! =N U L L )
{
t r a v e r s e t r e e (t r e ->l c h i l d ) ;
t r a v e r s e t r e e (t r e ->r c h i l d ) ;
p r i n t f (" %s " , t r e ->d a t a ) ;
}
}
v o i d i n o r d e r t r a v e r s (t r e e *t r e ) //中续遍历
{
i f (t r e ! =N U L L )
{
t r a v e r s e t r e e (t r e ->l c h i l d ) ;
p r i n t f (" %s " , t r e ->d a t a ) ;
t r a v e r s e t r e e (t r e ->r c h i l d ) ;
}
}
d o u b l e s o l u t i o n (t r e e *t r e ) //二叉树表达式求值
{
i f (t r e ->l c h i l d ==N U L L &&t r e ->r c h i l d ==N U L L &&
t r e ->d a t a [0]>=' 0' &&t r e ->d a t a [0]
r e t u r n a t o f (t r e ->d a t a ) ;
e l s e
{
s w i t c h (t r e ->d a t a [0])
{
c a s e ' *' :r e t u r n
s o l u t i o n (t r e ->l c h i l d ) *s o l u t i o n (t r e ->r c h i l d ) ;
c a s e ' -' :r e t u r n
s o l u t i o n (t r e ->l c h i l d ) -s o l u t i o n (t r e ->r c h i l d ) ;
c a s e ' +' :r e t u r n
s o l u t i o n (t r e ->l c h i l d ) +s o l u t i o n (t r e ->r c h i l d ) ;
c a s e ' /' :r e t u r n
s o l u t i o n (t r e ->l c h i l d ) /s o l u t i o n (t r e ->r c h i l d ) ;
}
}
}
i n t m a i n ()
{
t r e e *t r e ;
d o u b l e s u m ;
i n t c h ;
d o
{
p r i n t f (" ………………选择下面功能……………………\n " ) ; p r i n t f (" 1. 先序创建二叉数表达式 \n " ) ; p r i n t f (" 2. 后序遍利二叉数表达式 \n " ) ; p r i n t f (" 3. 求二叉数表达式的数值 \n " ) ; p r i n t f (" 4. 中序遍利二叉数表达式 \n " ) ; p r i n t f (" 5. 退出二叉数 \n " ) ; p r i n t f (" ……………………………………………………\n " ) ; s c a n f (" %d " , &c h ) ;
s w i t c h (c h )
{
c a s e 1:
p r i n t f (" 输入创建的二叉树：\n " ) ; g e t c h a r () ; c r e a t e t r e e (t r e ) ; i n p u t t r e e (t r e ) ;
p r i n t f (" \n " ) ; b r e a k ;
c a s e 2:
p r i n t f (" 后序遍历的二叉树：\n " ) ;
t r a v e r s e t r e e (t r e ) ; p r i n t f (" \n " ) ; b r e a k ;
c a s e 3:
s u m =s o l u t i o n (t r e ) ; p r i n t f (" 二叉树表达式
的值为=%l f \n " , s u m ) ; b r e a k ;
c a s e 4:
p r i n t f (" 中序遍历的二叉树：\n " ) ;
i n o r d e r t r a v e r s (t r e ) ; p r i n t f (" \n " ) ; b r e a k ;
c a s e 5: b r e a k ;
}
}w h i l e (c h ! =5) ;
r e t u r n 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
请按任意键继续. . .
（七）实验遇到的问题
二叉树的递归创建只能先序创建吗？若采用中序或后序创建，必须先输入左子树，我们所定义二叉树往电脑输入时，必须有终止条件，比如if(strcmp(ch,"#")==0)tre=NULL;所以，一颗二叉树中序或后序建立时，必先输入左子树，而左子树是终止条件，所以，无法建立一颗二叉树。
（一）实验目的
本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。
（二）实验内容
1、编写生成二叉树的函数， 二叉树的元素从键盘输入；
2、编写在二叉树中输入表达方式的函数；
3、编写在二叉树中实现表达方式的值的函数；
4、编写遍历并输出二叉树的函数。
(三）实验要求
1、掌握树型结构的机器内表示；
2、掌握树型结构之上的算法设计与实现；
3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。
(四) 实验设计思路
实验采用递归创建二叉树的表达, 并实现了后序遍历二叉数表达式, 既逆波兰表达式的输出, 编写函数计算表达式的值, 并输出。对实验题目进行细分, 逐一实现函数预期的功能, 如下图，先序输入创建二叉树表达式:+*-99##89##2##/66##3##
实验报告
(一) 部分算法流程图
1先序创建二叉树表达式
(五) 程序清单
#i n c l u d e
#i n c l u d e
#i n c l u d e
#d e f i n e l e n 20
#d e f i n e N U L L 0
s t r u c t t r e e
{
c h a r d a t a [l e n ];
t r e e *l c h i l d , *r c h i l d ;
};
v o i d c r e a t e t r e e (t r e e *&t r e ) //创建二叉树
{
c h a r c h [l e n ];
s c a n f (" %s " , c h ) ;
g e t c h a r () ;
i f (s t r c m p (c h , " #" ) ==0) t r e =N U L L ;
e l s e
{
t r e =(t r e e *) m a l l o c (s i z e o f (t r e e ) ) ;
s t r c p y (t r e ->d a t a , c h ) ;
c r e a t e t r e e (t r e ->l c h i l d ) ;
c r e a t e t r e e (t r e ->r c h i l d ) ;
}
}
v o i d i n p u t t r e e (t r e e *t r e ) //输出二叉树
{
i f (t r e ! =N U L L )
{
p r i n t f (" %s " , t r e ->d a t a ) ;
i f (t r e ->l c h i l d ! =N U L L ||t r e ->r c h i l d ! =N U L L )
{
p r i n t f (" (" ) ;
i n p u t t r e e (t r e ->l c h i l d ) ;
i f (t r e ->r c h i l d ! =N U L L ) p r i n t f (" , " ) ;
i n p u t t r e e (t r e ->r c h i l d ) ;
p r i n t f (" ) " ) ;
}
}
}
v o i d t r a v e r s e t r e e (t r e e *t r e ) //后续遍历
{
i f (t r e ! =N U L L )
{
t r a v e r s e t r e e (t r e ->l c h i l d ) ;
t r a v e r s e t r e e (t r e ->r c h i l d ) ;
p r i n t f (" %s " , t r e ->d a t a ) ;
}
}
v o i d i n o r d e r t r a v e r s (t r e e *t r e ) //中续遍历
{
i f (t r e ! =N U L L )
{
t r a v e r s e t r e e (t r e ->l c h i l d ) ;
p r i n t f (" %s " , t r e ->d a t a ) ;
t r a v e r s e t r e e (t r e ->r c h i l d ) ;
}
}
d o u b l e s o l u t i o n (t r e e *t r e ) //二叉树表达式求值
{
i f (t r e ->l c h i l d ==N U L L &&t r e ->r c h i l d ==N U L L &&
t r e ->d a t a [0]>=' 0' &&t r e ->d a t a [0]
r e t u r n a t o f (t r e ->d a t a ) ;
e l s e
{
s w i t c h (t r e ->d a t a [0])
{
c a s e ' *' :r e t u r n
s o l u t i o n (t r e ->l c h i l d ) *s o l u t i o n (t r e ->r c h i l d ) ;
c a s e ' -' :r e t u r n
s o l u t i o n (t r e ->l c h i l d ) -s o l u t i o n (t r e ->r c h i l d ) ;
c a s e ' +' :r e t u r n
s o l u t i o n (t r e ->l c h i l d ) +s o l u t i o n (t r e ->r c h i l d ) ;
c a s e ' /' :r e t u r n
s o l u t i o n (t r e ->l c h i l d ) /s o l u t i o n (t r e ->r c h i l d ) ;
}
}
}
i n t m a i n ()
{
t r e e *t r e ;
d o u b l e s u m ;
i n t c h ;
d o
{
p r i n t f (" ………………选择下面功能……………………\n " ) ; p r i n t f (" 1. 先序创建二叉数表达式 \n " ) ; p r i n t f (" 2. 后序遍利二叉数表达式 \n " ) ; p r i n t f (" 3. 求二叉数表达式的数值 \n " ) ; p r i n t f (" 4. 中序遍利二叉数表达式 \n " ) ; p r i n t f (" 5. 退出二叉数 \n " ) ; p r i n t f (" ……………………………………………………\n " ) ; s c a n f (" %d " , &c h ) ;
s w i t c h (c h )
{
c a s e 1:
p r i n t f (" 输入创建的二叉树：\n " ) ; g e t c h a r () ; c r e a t e t r e e (t r e ) ; i n p u t t r e e (t r e ) ;
p r i n t f (" \n " ) ; b r e a k ;
c a s e 2:
p r i n t f (" 后序遍历的二叉树：\n " ) ;
t r a v e r s e t r e e (t r e ) ; p r i n t f (" \n " ) ; b r e a k ;
c a s e 3:
s u m =s o l u t i o n (t r e ) ; p r i n t f (" 二叉树表达式
的值为=%l f \n " , s u m ) ; b r e a k ;
c a s e 4:
p r i n t f (" 中序遍历的二叉树：\n " ) ;
i n o r d e r t r a v e r s (t r e ) ; p r i n t f (" \n " ) ; b r e a k ;
c a s e 5: b r e a k ;
}
}w h i l e (c h ! =5) ;
r e t u r n 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
请按任意键继续. . .
（七）实验遇到的问题
二叉树的递归创建只能先序创建吗？若采用中序或后序创建，必须先输入左子树，我们所定义二叉树往电脑输入时，必须有终止条件，比如if(strcmp(ch,"#")==0)tre=NULL;所以，一颗二叉树中序或后序建立时，必先输入左子树，而左子树是终止条件，所以，无法建立一颗二叉树。