数据结构实验二叉树.pdf

_

实验六：二叉树及其应用

一、实验目的

树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构

的特性，以及如何应用树结构解决具体问题。

二、问题描述

首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算

术表达式的基础上，设计一个十进制的四则运算的计算器。

如算术表达式：a+b*(c-d)-e/f

三、实验要求

如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的

个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入

的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。

四、实验环境

PC微机

DOS操作系统或Windows操作系统

TurboC程序集成环境或VisualC++程序集成环境

五、实验步骤

1、根据二叉树的各种存储结构建立二叉树；

2、设计求叶子结点个数算法和树的深度算法；

3、根据表达式建立相应的二叉树，生成表达式树的模块；

4、根据表达式树，求出表达式值，生成求值模块；

5、程序运行效果，测试数据分析算法。

_

六、测试数据

1、输入数据：2.2*（3.1+1.20）-7.5/3

正确结果：6.96

2、输入数据：(1+2)*3+(5+6*7);

正确输出：56

七、表达式求值

由于表达式求值算法较为复杂，所以单独列出来加以分析：

1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作

符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀

表达式可以很容易地利用堆栈计算出表达式的值。

例如有如下的中缀表达式：

a+b-c

转换成后缀表达式为：

ab+c-

然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再

将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a和b放入栈

中，然后碰到操作符“+”，则从栈中弹出a和b进行a+b的运算，并将其结果d（假设

为d）放入栈中，然后再将c放入栈中，最后是操作符“-”，所以再弹出d和c进行d-c

运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运

算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级

以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。

2、求值过程

_

一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的

形式保存。

二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括

号处理掉。

三、计算后缀表达式的值。

3、中缀表达式分解

DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，

保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：

2.2*(3.1+1.20)-7.5/3

队首队尾

其算法思想是：从左往右按一个字节依次扫描原始中缀表达式m_string，碰到连续的数字

或小数点就加到strin