表达式用二叉树表示Word格式文档下载.docx
- 文档编号:6942284
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:18
- 大小:54.79KB
表达式用二叉树表示Word格式文档下载.docx
《表达式用二叉树表示Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《表达式用二叉树表示Word格式文档下载.docx(18页珍藏版)》请在冰点文库上搜索。
对二叉树表达式进行前序遍历。
中缀表达式:
对二叉树表达式进行中序遍历,若结点操作符的优先级高于其左或右子树,在打印相应的子树之前先打印开括号,在打印相应的子树最后在打印一个闭括号。
后缀表达式:
对二叉树表达式进行后序遍历。
建立表达式树就是建立树中的每一个结点,将每一个结点链接起来就是整棵树。
而在建立深度低的结点时要将其左右指针指向之前建立的深度比它高一级的结点(如’*’要指向’2’和’3’,而’+’又要指向’*’)。
这样我们可以用栈来存放每次建立的结点,按照优先级(表达式为中缀型)或顺序扫描表达式(表达式为波兰式与逆波兰式)建立每一个结点。
建立结点的顺序即为表达式求值的顺序。
如果扫描到操作数则直接新建一个左右指针为空的结点,并压入结点栈中(存放结点指针)。
遇到运算符时首先新建一个结点,然后从栈中依次弹出两个结点,并让新建立的结点的左右指针域指向它们。
当所有结点建立完毕时,如果表达式没有错误(这里假设输入表达式正确),这时栈中应该只剩下一个结点,它就是所建立的表达式的根结点。
4.详细设计:
(具体方法)
首先创建一个节点类TNode:
包含操作符oper、左孩子left、右孩子right,isOper()判断是否为操作符,getOperOrder()返回运算符op所对应的优先级,freeTree()程序结束销毁二叉树,postOrder()先序遍历,preOrder()后序遍历,inOrder()中序遍历,ExpTree1()后缀表达式生成二叉树,ExpTree3()前缀表达式生成二叉树,ExpTree2()中后缀表达式生成二叉树,count()求值函数,paint()输出函数
附程序:
#include<
iostream>
stack>
queue>
string>
#include<
math.h>
usingnamespacestd;
classTNode//节点类
{public:
charoper;
TNode*left;
TNode*right;
ints;
intt;
TNode()
{left=right=NULL;
oper=0;
}
TNode(charop)
oper=op;
}};
boolisOper(charop)//判断是否为运算符
{
charoper[]={'
('
'
)'
+'
-'
*'
/'
^'
};
for(inti=0;
i<
sizeof(oper);
i++)
{if(op==oper[i])
{
returntrue;
}}
returnfalse;
intgetOperOrder(charop)//返回运算符op所对应的优先级
{switch(op)
{case'
:
return1;
case'
return2;
return3;
return4;
default:
//定义在栈中的右括号和栈底字符的优先级最低
return0;
}}
voidfreeTree(TNode*&
p)//释放树
{if(p->
left!
=NULL)
freeTree(p->
left);
if(p->
right!
right);
delete(p);
cout<
<
"
Memoryfree"
;
}
voidpostOrder(TNode*p)//先序遍历
{if(p)
{postOrder(p->
postOrder(p->
cout<
p->
oper;
voidpreOrder(TNode*p)//后序遍历
{cout<
preOrder(p->
voidinOrder(TNode*p)//中序遍历
left)
{if(isOper(p->
left->
oper)
&
&
getOperOrder(p->
<
getOperOrder(p->
oper))
{cout<
("
inOrder(p->
cout<
)"
}else{
}}
if(p->
right)
right->
=getOperOrder(p->
}}}}
voidExpTree1(TNode*&
p,stringstr)//后缀表达式生成二叉树
{stack<
TNode*>
nodeStack;
chartemp;
inti=0;
temp=str[i++];
while(temp!
='
\0'
)
{if(temp!
!
isOper(temp))//不是运算符,则进栈
{p=newTNode(temp);
//以temp为结点值构造二叉树结点
nodeStack.push(p);
temp=str[i++];
else
{p=newTNode(temp);
if(nodeStack.size())
{p->
right=nodeStack.top();
//若非空则弹栈并设为结点的右孩子
nodeStack.pop();
}
left=nodeStack.top();
//若非空则弹栈并设为结点的左孩子
nodeStack.push(p);
temp=str[i++];
}}}
voidExpTree3(TNode*&
p,stringstr)//前缀表达式生成二叉树
{stack<
inti=str.size()-1;
temp=str[i--];
isOper(temp))
//以temp为内容来建立新的结点
temp=str[i--];
{p=newTNode(temp);
if(nodeStack.size())//若栈顶指针所指结点左孩子为空
{p->
//则当前结点设置成其左孩子
}if(nodeStack.size())//若栈顶指针所指结点右孩子为空
{p->
//则当前结点设置成其右孩子
//栈顶元素左右孩子指针设置完毕弹出}
nodeStack.push(p);
temp=str[i--];
voidExpTree2(TNode*&
p,stringstr)//中缀表达式转换成后缀表达式生成二叉树
{stack<
char>
a;
chartemp;
stringPostfixexp="
inti=0;
temp=str[i++];
{if(!
{Postfixexp+=temp;
elseif(temp=='
)//进栈
{a.push(temp);
temp=str[i++];
elseif(temp=='
){
while(a.top()!
)//脱括号
{Postfixexp+=a.top();
a.pop();
//在碰到开括号和栈为空前反复弹出栈中元素}
a.pop();
temp=str[i++];
}elseif(temp=='
||temp=='
)//出栈{
while(!
a.empty()&
a.top()!
getOperOrder(a.top())>
=getOperOrder(temp))//若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时,
//将栈顶元素弹出到后缀表达式中,并且str下标加1
{Postfixexp+=a.top();
a.pop();
a.push(temp);
temp=str[i++];
}}
a.empty())
{Postfixexp+=a.top();
a.pop();
}
ExpTree1(p,Postfixexp);
voidcount(TNode*p,int&
height,intn)//求值函数
left==NULL&
right==NULL)
{if(n>
height)
height=n;
if(p->
count(p->
left,height,n+1);
count(p->
right,height,n+1);
voidpaint(TNode*p)//输出函数
{intheight=0;
inth=0;
inti;
usingstd:
queue;
queue<
aQueue;
count(p,height,1);
TNode*pointer=p;
TNode*lastpointer;
if(pointer)
{pointer->
s=1;
pointer->
t=1;
aQueue.push(pointer);
while(!
aQueue.empty())
{lastpointer=pointer;
pointer=aQueue.front();
aQueue.pop();
if(pointer->
s>
h)
{cout<
endl;
h=pointer->
s;
t==1)
{for(i=0;
pow(2,height-pointer->
s)-1;
"
elseif(lastpointer->
s!
=pointer->
s){
for(i=0;
(pointer->
t-1)*(pow(2,height-pointer->
s+1)-1)+(pointer->
t-1)-1+pow(2,height-pointer->
s);
cout<
else
{for(i=0;
t-lastpointer->
t)*(pow(2,height-pointer->
t)-1;
cout<
pointer->
=NULL){
pointer->
s=pointer->
s+1;
t=pointer->
t*2-1;
aQueue.push(pointer->
if(pointer->
t*2;
aQueue.push(pointer->
}}}
intmain()
{stringexpression;
TNode*tree;
endl<
请输入字符串表达式:
cin>
>
expression;
if(isOper(expression[0]))
ExpTree3(tree,expression);
elseif(isOper(expression[1]))
ExpTree2(tree,expression);
else
ExpTree1(tree,expression);
paint(tree);
中缀表达式为:
inOrder(tree);
前缀表达式为:
preOrder(tree);
后缀表达式为:
postOrder(tree);
freeTree(tree);
system("
pause"
);
return0;
5.测试数据:
(1)请输入字符串表达式:
-+1*234
-
+4
1*
23
中缀表达式为:
1+2*3-4
123*+4-
memoryfreememoryfreememoryfreememoryfreememoryfree
请按任意键继续………………………..
(2)请输入字符串表达式:
(3)请输入字符串表达式:
测试截图:
6.总结:
程序调试中的问题及解决方法:
前缀表达式建树,通过入栈出栈操作求出前缀表达式的逆序,针对得到的逆序表达式通过后缀表达式建立二叉树的方法,遇到操作数则入栈,遇到操作符则从栈中弹出两个操作数构建一棵小的二叉树,然后将小树的根节点入栈以便于下次操作。
经过循环,小树“长成”大树,表达式读完二叉树即建成。
心得体会:
由于之前的上机较简单,经过这次作业我才深深感受到编程的滋味,真是苦中有乐,完成之后觉得知识点掌握的更加透彻了,因为有好多问题是不上机根本想不到的,只有经过了实践才会有提高,自己还是太缺乏锻炼,应该多动手编程,从整理思路、编写代码、调试程序修改错误等各方面不断完善自己
7.使用说明:
可为前缀、中缀、后缀表达式(程序自动判断)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 表达式 二叉 表示