- 1、本文档共18页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
表达式用叉树表示
数据结构程序报告(3)
2011.3.29
2. 需求分析:
(1)功能:表达式可以用二叉树表示,对于简单的四则运算,请实现以下功能
【1】对于任意给出的前缀表达式(不带括号)、中缀表达式(可以带括号)或后缀表达式(不带括号),能够在计算机内部构造出一棵表达式二叉树,并且图示出来(图形的形式)。
【2】对于构造好的内部表达式二叉树,按照用户的要求输出相应的前缀表达式(不带括号)、中缀表达式(可以带括号,但不允许冗余括)或后缀表达式(不带括号)。
提示:所谓中缀表达式中的冗余括号,就是去掉括号后不影响表达式的计算顺序。例如:“(c+b)+a”中的括号是冗余的,可以表示成不冗余的“c+b+a”。
(2)输入输出要求:请输入字符串表达式:
树形二叉树(图形显示)
中缀表达式为:
前缀表达式为:
后缀表达式为:
概要设计:(算法)
分成两部分完成:
【1】前缀、中缀、后缀表达式-二叉树表达式
前缀表达式-二叉树表达式:(a)碰到操作数则把其值赋给相应的新申请的二叉树结点,地址压栈;(b)碰到操作符则把其值赋给相应的新申请的二叉树,并从栈中弹出两个地址,分别作为其右指针和左指针,然后再把其地址压栈,最后一个地址即为二叉树的根结点地址。
中缀表达式-二叉树表达式:把中缀表达式转换成后缀表达式,然后再建立二叉树。
后缀表达式-二叉树表达式:(a)碰到操作数则把其值赋给相应的新申请的二叉树结点,若栈为空则地址压栈,若非空则取栈顶元素,若栈顶元素的左孩子为空则当前结点设为其左孩子,左孩子为满则设为其右孩子再压栈;(b)碰到操作数则把其值赋给相应的新申请的二叉树结点,取栈顶元素,若栈顶元素的左孩子为空则设为其左孩子,左孩子为满则设为其右孩子开始那个元素地址为根结点地址,开始时用变量root保存。
【1】二叉树表达式-前缀、中缀、后缀表达式
二叉树表达式-前缀表达式:对二叉树表达式进行前序遍历。
二叉树表达式-中缀表达式:对二叉树表达式进行中序遍历,若结点操作符的优先级高于其左或右子树,在打印相应的子树之前先打印开括号,在打印相应的子树最后在打印一个闭括号。
二叉树表达式-后缀表达式:对二叉树表达式进行后序遍历。
建立表达式树就是建立树中的每一个结点,将每一个结点链接起来就是整棵树。而在建立深度低的结点时要将其左右指针指向之前建立的深度比它高一级的结点(如’*’要指向’2’和’3’,而’+’又要指向’*’)。这样我们可以用栈来存放每次建立的结点,按照优先级(表达式为中缀型)或顺序扫描表达式(表达式为波兰式与逆波兰式)建立每一个结点。建立结点的顺序即为表达式求值的顺序。如果扫描到操作数则直接新建一个左右指针为空的结点,并压入结点栈中(存放结点指针)。遇到运算符时首先新建一个结点,然后从栈中依次弹出两个结点,并让新建立的结点的左右指针域指向它们。当所有结点建立完毕时,如果表达式没有错误(这里假设输入表达式正确),这时栈中应该只剩下一个结点,它就是所建立的表达式的根结点。
4. 详细设计:(具体方法)
首先创建一个节点类TNode:包含操作符oper、左孩子left、右孩子right,isOper()判断是否为操作符,getOperOrder()返回运算符op所对应的优先级,freeTree()程序结束销毁二叉树,postOrder()先序遍历,preOrder()后序遍历,inOrder()中序遍历,ExpTree1()后缀表达式生成二叉树,ExpTree3()前缀表达式生成二叉树,ExpTree2()中后缀表达式生成二叉树,count()求值函数,paint()输出函数
附程序:
#include iostream
#include stack
#include queue
#include string
#includemath.h
using namespace std;
class TNode//节点类
{ public:
char oper;
TNode *left;
TNode *right;
int s; int t;
TNode()
{ left=right=NULL;
oper=0;
}
TNode(char op)
{ left=right=NULL;
oper=op;}};
bool isOper(char op)//判断是否为运算符
{
char oper[]={
文档评论(0)