《表达式用二叉树表示》由会员分享，可在线阅读，更多相关《表达式用二叉树表示（23页珍藏版）》请在金锄头文库上搜索。
1、数据结构程序报告(3)(3)2011.3.292. 需求分析：（1）功能：表达式可以用二叉树表示，对于简单的四则运算，请实现以下功能【1】对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表 达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且图示出来（图形的形 式）。【2】对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达式（不带 括号中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不带括号。提示：所谓中缀表达式中的冗余括号，就是去掉括号后不影响表达式的计算顺序。例 如：（c+b）+a中的括号是冗余的，可以表示成不冗余的c+b+a。（2）输入输出
2、要求：请输入字符串表达式：树形二叉树（图形显示）中缀表达式为：前缀表达式为：后缀表达式为：3. 概要设计：（算法）分成两部分完成：【1】前缀、中缀、后缀表达式-二叉树表达式前缀表达式-二叉树表达式（a）碰到操作数则把其值赋给相应的新申请的二 叉树结点，地址压栈；（b）碰到操作符则把其值赋给相应的新申请的二叉树，并从 栈中弹出两个地址，分别作为其右指针和左指针，然后再把其地址压栈，最后一个 地址即为二叉树的根结点地址。中缀表达式-二叉树表达式：把中缀表达式转换成后缀表达式，然后再建立二 叉树。后缀表达式-二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二 叉树结点，若栈为空则地址压栈，若
3、非空则取栈顶元素，若栈顶元素的左孩子为空 则当前结点设为其左孩子，左孩子为满则设为其右孩子再压栈；（b）碰到操作数则 把其值赋给相应的新申请的二叉树结点，取栈顶元素，若栈顶元素的左孩子为空则 设为其左孩子，左孩子为满则设为其右孩子开始那个元素地址为根结点地址，开始 时用变量root保存。【1】二叉树表达式-前缀、中缀、后缀表达式二叉树表达式-前缀表达式：对二叉树表达式进行前序遍历。二叉树表达式- 中缀表达式：对二叉树表达式进行中序遍历，若结点操作符的 优先级高于其左或右子树，在打印相应的子树之前先打印开括号，在打印相应的子 树最后在打印一个闭括号。二叉树表达式-后缀表达式：对二叉树表达式进行后
4、序遍历。廿()5POU一、旧赐睦四()5POd、( ) 5p0JS0d、 ()*l$M、思蛆冗留垣友底domla回蚁()碧0do苍6、短中谋英Knm鑫录() Edos 一、6一出KW苴一出KW疽do短立堡佃回-|30任亚拒k-、felslss序遍历,ExpTree()后缀表达式生成二叉树,ExpTree(缀表达式生成二叉树,ExpTree2()中后缀表达式生成二叉树，count ()求值函数，paint ()输出函数附程序：#include #include #include #include #includeusing namespace std;class TNode/节点类( publi
5、c:char oper;TNode *left;TNode *right;int s ； int t ；TNode()(left=right二NULL;oper=0;TNode(char op)(left=right二NULL;oper=op;boo 二 sopernhar op)、* 案湖盼苛卸萌 charopemAcw+r-HV;* for(inino=Asizeof(oper)= + +) (if(OPHHOPerm)reium irup二reium fa-seaW geioperordernhar op)、潇回卸萌op孚淫间昏注苗忠(SWKCh(op) case -creium 1;
6、case+3 case -reium 2;case -*3case 二：.reium 3- case -3reium 4;default:/定义在栈中的右括号和栈底字符的优先级最低 return 0; void freeTree(TNode *&p)/释放树 if(p-left!二NULL)freeTree(p-left);if(p-right!二NULL)freeTree(p-right);delete(p);coutleft);postOrder(p-right);coutoper; void preOrder(TNode *p) /后 序遍历 if(p) coutoper;preOrde
7、r(p-left);preOrder(p-right); void inOrder(TNode *p)/中 序遍历 if(p)( if(p-left) if(isOper(p-left-oper)& getOperOrder(p-left-oper)oper) coutleft);coutleft);coutoper;if(p-right) if(isOper(p-right-oper)& getOperOrder(p-right-oper)oper) coutp%s Pou0q9xld )描密W* 番 4WI 您黑()NS.WMJS 1M 二odod.wwjs POU 出KWM贺0M愁亚、蜩
8、症洲 w、odopp%s POUDMCd ) 围只出KW亚蜩&E底亦&EBI您黑()NS.WWJSPOUWKdlus PON-m UHd )S-lJJSHdlu jKdrsnd.wwJS POU 亚、蜩S隔相怅即长只dLU$ M、(dlusPON- mUHd )(a Eg) d OS 一 胡63-。-d Eg)土(o-dEsZM=!JJSHdlu jAoNSES.1LJU 一(dlu Ja5lp PouA1DPONIV p%s ) 宓以 u贺卅宿坦探旅溟ss SUES、d63* PONI)rn*ldxLUpoT.SHdlu jKdrsnd.wwJS Poufodod.wwjs Pou 出Kwg
9、亚甫具愁ft您atiMXLLTTrs/odopIMJS POUDMCd )nodeStack.pop();/栈顶元素左右孩子指针设置完毕弹出nodeStack.push(p);temp=stri-; void ExpTree2(TNode *&p, string str)/中缀表达式转换成后缀表达式生成二叉树( stack a;char temp;string Postfixexp=;int i=0;temp=stri+;while(temp! = 0)( if(!isOper(temp)( Postfixexp+=temp;temp=stri+;else if(temp= = ()/8栈(
10、a.push(temp);temp=stri+;else if(temp= = )(while(a.top()! = ()/脱 括号( Postfixexp+=a.top();a.pop();/在碰到开括号和栈为空前反复弹出栈中元素a.pop()； temp=stri + +;else if(temp = = + |temp= = -|temp= = *|temp= = /)/出 栈while(!a.empty()&a.top()! = (&getOperOrder(a.top()=getOperOrder(temp)/若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时，/将栈顶元素弹出
11、到后缀表达式中，并且str下标加1 Postfixexp+=a.top();a.pop(); a.push(temp);temp=stri+; while(!a.empty() Postfixexp+=a.top();a.pop();ExpTree1(p,Postfixexp); void count(TNode *p,int &height,int n)/求 值函数 if(p-left= = NULL&p-right= = NULL) if(nheight)heighten;if(p-left!二NULL)count(p-left,height,n + 1);count(p-right,height,n+1); void paint(TNode *p)/瀚出函数( int height=0;int h=0;int i;using
