表达式用二叉树表示

达式用二叉树表示 数构据结程序结告;3, 2011.3.29 2. 需求分析, ;1,功能,表式可以用二叉结表示～结于结结的四结算～结结结以下功能达运 【1】结于任意结出的前结表式;不结括,、中结表式;可以结括,或后结表式达号达号达 ;不结括,～能结在结算机部造出一表式二叉结～且结示出;结形的形式,。号内构棵达并来 【2】结于造好的部表式二叉结～按照用结的要求结出相结的前结表式;不结括,构内达达号、 中结表式;可以结括～但不允结冗余括,或后结表式;不结括,。达号达号 提示,所结中结表式中的冗余括～就是去掉括后不影表式的结算结序。例如,达号号响达 “;c+b,+a”中的括是冗余的～可以表示成号 冗余的“c+b+a”。 ;2,结入结出要求,结结入字符串表式,达 结形二叉结;结形结示, 中结表式结,达 前结表式结,达 后结表式结,达 3.概要结结,;算法, 分成部分完成,两 【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 #include #include #include #include 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[]={'(',')','+','-','*','/','^'}; for(int i=0;ileft!=NULL) freeTree(p->left); if(p->right!=NULL) freeTree(p->right); delete(p); cout<<"Memory free "; }void postOrder(TNode *p) //先序遍结 { if(p) { postOrder(p->left); postOrder(p->right); cout<oper; } } void preOrder(TNode *p) //后序遍结 { if(p) { cout<oper; preOrder(p->left); preOrder(p->right);} } void inOrder(TNode *p)//中序遍结 { if(p) { if(p->left) { if(isOper(p->left->oper) && getOperOrder(p->left->oper) oper)) { cout<<"("; inOrder(p->left); cout<<")"; }else{ inOrder(p->left); } } cout<oper; if(p->right) { if(isOper(p->right->oper) && getOperOrder(p->right->oper) <=getOperOrder(p->oper)) { cout<<"("; inOrder(p->right); cout<<")"; }else{ inOrder(p->right); } } } } void ExpTree1(TNode *&p,string str)//后结表式生成二叉结达 {stack nodeStack; char temp; int i=0; temp=str[i++]; while(temp!='\0') { if(temp!='\0'&&!isOper(temp))//不是算符～结结结运 { p=new TNode(temp);//以temp结结点结造二叉结结点构 nodeStack.push(p); temp=str[i++];} else { p=new TNode(temp); if(nodeStack.size()) { p->right=nodeStack.top();//若非空结结结结结结点的右孩子并 nodeStack.pop(); } if(nodeStack.size()) { p->left=nodeStack.top();//若非空结结结结结结点的左孩子并 nodeStack.pop(); } nodeStack.push(p); temp=str[i++]; } } } void ExpTree3(TNode *&p, string str)//前结表式生成二叉结达{ stack nodeStack; char temp; int i=str.size()-1; temp=str[i--]; while(temp!='\0') { if(temp!='\0'&&!isOper(temp)) { p=new TNode(temp);//以temp结容建立新的结点内来 nodeStack.push(p); temp=str[i--];} else { p=new TNode(temp); if(nodeStack.size())//若结结指结所指结点左孩子结空 { p->left=nodeStack.top(); //结前结点结置成其左孩子当 nodeStack.pop(); } if(nodeStack.size())//若结结指结所指结点右孩子结空 { p->right=nodeStack.top();//结前结点结置成其右孩子当 nodeStack.pop();//结结元素左右孩子指结结置完结结出 } nodeStack.push(p); temp=str[i--]; } } } void ExpTree2(TNode *&p, string str)//中结表式结结成后结表式生成二叉结达达 { stack a; char temp; string Postfixexp=""; int i=0; temp=str[i++]; while(temp!='\0') { if(!isOper(temp)) { Postfixexp+=temp; temp=str[i++];} else if(temp=='(')//结结 { a.push(temp); temp=str[i++];} else if(temp==')'){ while(a.top()!='(')//括脱号 { Postfixexp+=a.top(); a.pop();//在到结括和结结空前反结结出结中元素 碰号} a.pop(); temp=str[i++]; }else if(temp=='+'||temp=='-'||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++]; } } 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(n>height) height=n;} if(p->left!=NULL) count(p->left,height,n+1); if(p->right!=NULL) count(p->right,height,n+1); }void paint(TNode *p)//结出函数 { int height=0; int h=0; int i; using std::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<s;} if(pointer->t==1) {for(i=0;is)-1;i++) cout<<" ";} else if(lastpointer->s!=pointer->s){for(i=0;i<(pointer->t-1)*(pow(2,height-pointer->s+1)-1)+(pointer->t-1)-1+pow(2,height- pointer->s);i++) cout<<" "; } else { for(i=0;i<(pointer->t-lastpointer->t)*(pow(2,height-pointer->s+1)-1)+(pointer->t- lastpointer->t)-1;i++) cout<<" "; } cout<oper; if(pointer->left!=NULL){ pointer->left->s=pointer->s+1; pointer->left->t=pointer->t*2-1; aQueue.push(pointer->left);} if(pointer->right!=NULL){ pointer->right->s=pointer->s+1; pointer->right->t=pointer->t*2; aQueue.push(pointer->right); } } } int main() { string expression; TNode *tree; cout<>expression; if(isOper(expression[0])) ExpTree3(tree,expression); else if(isOper(expression[1])) ExpTree2(tree,expression); else ExpTree1(tree,expression); paint(tree); cout<