没有合适的资源?快使用搜索试试~ 我知道了~
数据结构实验二叉树.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 77 浏览量
2022-06-18
00:38:00
上传
评论
收藏 1.24MB PDF 举报
温馨提示
试读
34页
。。。
资源推荐
资源详情
资源评论
_
实验六:二叉树及其应用
一、实验目的
树是数据结构中应用极为广泛的非线性结构,本单元的实验达到熟悉二叉树的存储结构
的特性,以及如何应用树结构解决具体问题。
二、问题描述
首先,掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次,以二叉树表示算
术表达式的基础上,设计一个十进制的四则运算的计算器。
如算术表达式:a+b*(c-d)-e/f
三、实验要求
如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树,分别计算统计叶子结点的
个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入
的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。
四、实验环境
PC 微机
DOS 操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境
五、实验步骤
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,碰到连续的数字
或小数点就加到 string 变量 str 中;如果碰到括号或操作符就将原先的 str 推入队列,然
后将括号或操作符赋予 str,再将 str 推入队列,并将 str 赋予空值,依次循环进行直
到扫描 m_string 完成。
4、转化为后缀表达式
ChangeToSuffix()函数。将保存在队列中的中缀表达式转换为后缀表达式,并保存在
栈中。这个函数也是整个表达式算法的关键,这里需要两个栈 stack_A 和 stack_B,分别
在转换过程中临时存放后缀表达式的操作数与操作符。依次从中缀表达式队列que 中出列
一个元素,并保存在一个 string 变量 str 中,然后按以下几方面进行处理:
①如果 str 是“(”,则将 str 推入栈 stack_B。
②如果 str 是“)”,则要考虑 stack_B 的栈顶是不是“(”,是的话就将“(”出栈 stack_B;
如果不是,则将 stack_B 出栈一个元素(操作符),然后将其推入栈 stack_A。
_
③如果 str 是“+”或“-”,则要考虑有括号和优先级的情况,如果栈 stack_B 为空或者
栈顶为“(”,则将 str 推入栈 stack_B;因为操作符“+”和“-”优先级相同(谁先出现
就先处理谁进栈 stack_A),并且低于“*”和“/”,所以当栈stack_B 不为空并且栈顶不
为“(”,则依次循环取出stack_B 的栈顶元素并依次推入栈 stack_A,循环结束后再将str
推入栈 stack_B。
④如果 str 是“*”或“/”,因为它们的优先级相同并且高于“+”和“-”,所以如果栈
stack_B 为空或者栈顶为“+”、“-”或“(”就直接将 str 推入栈 stack_B;否则就将 stack_B
弹出一个元素并将其推入栈 stack_A 中,然后再将 str 推入栈 stack_B 中。
⑤除了上述情况外就只剩下操作数了,操作数就可以直接推入栈 stack_A 中。注意整个过
程中栈 stack_B 中的元素只能是如下几种:“(”、“+”、“-”、“*”、“/”,而最终
栈 stack_A 保存的是后缀表达式。
只有操作数和操作符,如下图所示:
-
/
3
栈顶
-
*
+
3.1
1.20
7.5
*
2.2
+
/
2.2 7.5 3
1.2
3.1
栈示意图
栈底
表达式二叉树
_
注意到最后返回的是 stack_B 而不是 stack_A,因为考虑到为了后面的计算方便,所以将
其倒序保存在 stack_B 中(最后一个 while 循环)。
5、后缀表达式求值
Calculate()函数。剩下的计算后缀表达式就显得非常简单了,依次将倒序的后缀表达
式 stack_B 弹出一个元素推入保存结果的 double 类型的栈 stack 中,如果遇到操作符就
从栈 stack 中弹出两元素进行该操作符的运算并将其结果推入到栈 stack 中,依次循环进
行直到栈 stack_B 为空,最后栈 stack 只有一个元素即为表达式的结果。
八、实验报告要求
实验报告应包括以下几个部分:
1、设计算术表达式树的存储结构;
实验中采用的是二叉树的的链接存储。结点格式如下:
left data right
其严格类的定义如下:
template <typename T>
class Binarynode //二叉树的结点类
{
public:
Binarynode():left(NULL),right(NULL){} //默认构造函数
Binarynode(const T& item,Binarynode<T> *lptr=NULL,
Binarynode<T> *rptr=NULL):data(item),left(lptr),right(rptr){} //初始化
T data; //结点数据
Binarynode<T> *&Left() {return left;} //取 left
剩余33页未读,继续阅读
资源评论
xxpr_ybgg
- 粉丝: 6559
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功