北工大數(shù)據(jù)結(jié)構(gòu)上機實驗報告3

1、上機題三報告 姓名： 學號： 完成日期：2015年5月5日題目：表達式可以用表達式二叉樹來表示。對于簡單的四則運算表達式，請實現(xiàn)以下功能；（1）對于任意給出的前綴表達式（不帶括號）、中綴表達式（可以帶括號）或后綴表達式（不帶括號），能夠在計算機內(nèi)部構(gòu)造出一棵表達式二叉樹，并且以圖示顯示出來（字符圖或圖形的形式）。（2） 對于構(gòu)造好的內(nèi)部表達式二叉樹，按照用戶要求，輸出相應(yīng)的前綴表達式（不帶括號）、中綴表達式（可以帶括號）或后綴表達式（不帶括號）.1、 需求分析1. 輸入形式、輸入值的范圍；輸入前綴表達式（不帶括號）、中綴表達式（可以帶括號）或后綴表達式（不帶括號）2. 輸出形式；表達式二叉樹，

2、前綴表達式、中綴表達式和后綴表達式。3. 程序功能；用表達式二叉樹表示表達式，并轉(zhuǎn)換為前綴表達式、中綴表達式或后綴表達式。4. 測試數(shù)據(jù) 正確的輸入輸出： 錯誤的輸入輸出： 2、 概要設(shè)計1. ADT定義class TNode/節(jié)點類開始2. 主程序流程結(jié)束輸出各類表達式是是將表達式轉(zhuǎn)換為二叉樹表達式是否是否為中綴表達式是否為前綴表達式輸入表達式是否為后綴表達式否 3. 各程序模塊間的調(diào)用關(guān)系Main（） 刪除樹打印樹求前、中、后綴表達式模塊求二叉樹表達式模塊3、 詳細設(shè)計1. 實現(xiàn)ADT定義的數(shù)據(jù)類型class TNode/節(jié)點類 public:char oper;/數(shù)據(jù)域，為簡便起見，操作

3、數(shù)用單個字符代替TNode *left;TNode *right;int s;int t;/計算樹的層數(shù)使用TNode()/缺省構(gòu)造函數(shù) left=right=NULL; oper=0; TNode(char op)/賦值構(gòu)造函數(shù) left=right=NULL; oper=op;2. 算法描述表達式轉(zhuǎn)化為二叉樹void pre2tree(TNode *&p, string str)/前綴表達式生成二叉樹 碰到操作數(shù)則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，地址壓棧；碰到操作符則把其值賦給相應(yīng)的新申請的二叉樹，并從棧中彈出兩個地址，分別作為其左指針和右指針，然后再把其地址壓棧，最后一個地址

4、即為二叉樹的根結(jié)點地址。void post2tree(TNode *&p,string str)/后綴表達式生成二叉樹 /碰到操作數(shù)則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，若棧為空則地址壓棧，/碰到操作符則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，取棧頂元素，/若當前元素的左孩子為空則設(shè)為其左孩子，/左孩子為滿則設(shè)為其右孩子,開始那個元素地址為根結(jié)點地址，開始時用變量root保存。void in2tree(TNode *&p, string str)/中綴表達式轉(zhuǎn)換成后綴表達式生成二叉樹 從中綴表達式中自左至右依次讀入各個字符。  如果讀入操作數(shù)，直接輸出到后綴表達式。 如果

5、讀入的是運算符，并且運算符棧為空，則將該運算符直接進棧；如果棧不為空， 則比較該運算符和棧頂運算符的優(yōu)先級。      若該運算符高于棧頂運算符的優(yōu)先級，則將該運算符直接進棧； 若該運算符低于或等于棧頂運算符的優(yōu)先級，則將棧中高于或等于該運算符優(yōu)先級的元 素依次出棧輸出到后綴表達式中，然后再將該運算符進棧。 在碰到開括號和棧為空前反復(fù)彈出棧中元素 若棧非空棧頂不是左括號且棧頂元素優(yōu)先級不低于輸入運算符時，/將棧頂元素彈出到后綴表達式二叉樹表達式轉(zhuǎn)化為表達式 void postOrder(TNode *p) /先序遍

6、歷 if(p) postOrder(p->left); postOrder(p->right); cout<<p->oper; void preOrder(TNode *p) /后序遍歷 if(p) cout<<p->oper; preOrder(p->left); preOrder(p->right); void inOrder(TNode *p)/中序遍歷，同時輸出不帶冗余括號的中綴表達式 if(p)if(p->left) if(如果當前節(jié)點的左子樹是運算符，且運算符優(yōu)先級低于當前運算符，那么左邊的表達式要先計算，需要加括號

7、) cout<<"(" inOrder(p->left); cout<<")" else/否則直接輸出左子樹 inOrder(p->left); cout<<p->oper;/輸出當前節(jié)點 if(p->right) if(如果當前節(jié)點的右子樹是運算符，且運算符優(yōu)先級不高于當前運算符，那么右邊的表達式要先計算，需要加括號) cout<<"(" inOrder(p->right); cout<<")" else inOrder(p

8、->right); 4、 程序測試5、 用戶使用說明運行程序后，按照提示選擇表達式類型（-1：前綴表達式；0：中綴表達式；1：后綴表達式）然后輸入相應(yīng)的表達式，回車后可以得到二叉樹表達式及出前綴、中綴、后綴表達式6、 源程序#include <iostream>#include <stack>#include <queue>#include <string>#include<math.h>using namespace std;class TNode/節(jié)點類 public:char oper;/數(shù)據(jù)域，為簡便起見，操作數(shù)用單個字

9、符代替TNode *left;TNode *right;int s;int t;/計算樹的層數(shù)使用TNode()/缺省構(gòu)造函數(shù) left=right=NULL; oper=0; TNode(char op)/賦值構(gòu)造函數(shù) left=right=NULL; oper=op;bool isOper(char op)/判斷是否為運算符char oper='(',')','+','-','*','/',''for(int i=0;i<sizeof(oper);i+) if(op=ope

10、ri) return true; return false;int getOperOrder(char op)/返回運算符op所對應(yīng)的優(yōu)先級/ 左括號優(yōu)先級，加減號為，乘除號為，方冪為，右括號，棧底返回switch(op)case '(': return 1; case '+': case '-':return 2; case '*': case '/':return 3; case '':return 4; default: /定義在棧中的右括號和棧底字符的優(yōu)先級最低 return 0; void

11、 freeTree(TNode *&p) /遞歸刪除樹 if(p->left!=NULL) freeTree(p->left); if(p->right!=NULL) freeTree(p->right); delete(p); void postOrder(TNode *p) /先序遍歷 if(p) postOrder(p->left); postOrder(p->right); cout<<p->oper; void preOrder(TNode *p) /后序遍歷 if(p) cout<<p->oper; p

12、reOrder(p->left); preOrder(p->right); void inOrder(TNode *p)/中序遍歷，同時輸出不帶冗余括號的中綴表達式 if(p)if(p->left) /如果當前節(jié)點的左子樹是運算符，且運算符優(yōu)先級低于當前運算符，/那么左邊的表達式要先計算，需要加括號if(isOper(p->left->oper)&& getOperOrder(p->left->oper)<getOperOrder(p->oper) cout<<"(" inOrder(p-&g

13、t;left); cout<<")" else/否則直接輸出左子樹 inOrder(p->left); cout<<p->oper;/輸出當前節(jié)點 if(p->right) /如果當前節(jié)點的右子樹是運算符，且運算符優(yōu)先級不高于當前運算符，/那么右邊的表達式要先計算，需要加括號 if(isOper(p->right->oper)&& getOperOrder(p->right->oper)<=getOperOrder(p->oper) cout<<"("

14、; inOrder(p->right); cout<<")" else inOrder(p->right); void post2tree(TNode *&p,string str)/后綴表達式生成二叉樹 /（a）碰到操作數(shù)則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，若棧為空則地址壓棧，/（b）碰到操作符則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，取棧頂元素，/若當前元素的左孩子為空則設(shè)為其左孩子，/左孩子為滿則設(shè)為其右孩子,開始那個元素地址為根結(jié)點地址，開始時用變量root保存。stack <TNode*> nodeStack;/用于保存節(jié)

15、點指針的棧 char temp; int i=0; temp=stri+; while(temp!='0') if(temp!='0'&&!isOper(temp)/不是運算符，則進棧 p=new TNode(temp);/以temp為結(jié)點值構(gòu)造二叉樹結(jié)點 nodeStack.push(p); temp=stri+;/讀入下一個 else /如果遇到符號，則彈棧，依次設(shè)為右節(jié)點和左節(jié)點p=new TNode(temp); if(nodeStack.size() p->right=nodeStack.top();/若非空則彈棧并設(shè)為結(jié)點的右孩

16、子 nodeStack.pop(); if(nodeStack.size() p->left=nodeStack.top();/若非空則彈棧并設(shè)為結(jié)點的左孩子 nodeStack.pop(); nodeStack.push(p); temp=stri+; void pre2tree(TNode *&p, string str)/前綴表達式生成二叉樹/碰到操作數(shù)則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，地址壓棧；/碰到操作符則把其值賦給相應(yīng)的新申請的二叉樹，并從棧中彈出兩個地址，/分別作為其左指針和右指針，然后再把其地址壓棧，最后一個地址即為二叉樹的根結(jié)點地址。stack <TN

17、ode*> nodeStack; char temp; int i=str.size()-1; temp=stri-; while(temp!='0') if(temp!='0'&&!isOper(temp) p=new TNode(temp);/以temp為內(nèi)容來建立新的結(jié)點 nodeStack.push(p); temp=stri-; else p=new TNode(temp); if(nodeStack.size()/棧非空 p->left=nodeStack.top(); /則棧頂指針所指結(jié)點設(shè)置成當前結(jié)點左孩子 nodeS

18、tack.pop(); if(nodeStack.size()/棧非空 p->right=nodeStack.top();/則棧頂指針所指結(jié)點設(shè)置成當前結(jié)點右孩子 nodeStack.pop();/棧頂元素左右孩子指針設(shè)置完畢彈出 nodeStack.push(p); temp=stri-; /當?？涨覓呙璧阶詈髸r，樹根由P帶回void in2tree(TNode *&p, string str)/中綴表達式轉(zhuǎn)換成后綴表達式生成二叉樹 stack<char> a; char temp; string Postfixexp="" int i=0; t

19、emp=stri+; while(temp!='0') if(!isOper(temp)/操作數(shù)則直接進數(shù)據(jù)棧 Postfixexp+=temp; temp=stri+; else if(temp='(')/進棧 a.push(temp); temp=stri+; else if(temp=')') while(a.top()!='(')/脫括號 Postfixexp+=a.top(); a.pop();/在碰到開括號和棧為空前反復(fù)彈出棧中元素 a.pop(); temp=stri+; else if(temp='+

20、9;|temp='-'|temp='*'|temp='/')/出棧while(!a.empty()&&a.top()!='('&&getOperOrder(a.top()>=getOperOrder(temp)/若棧非空棧頂不是左括號且棧頂元素優(yōu)先級不低于輸入運算符時，/將棧頂元素彈出到后綴表達式中，并且str下標加 Postfixexp+=a.top(); a.pop(); a.push(temp);temp=stri+; /end while(temp!='0') whil

21、e(!a.empty() Postfixexp+=a.top();a.pop(); Postfixexp+='0' /cout<<Postfixexp; post2tree(p,Postfixexp);void count(TNode *p,int &height,int n)/求值函數(shù)/求樹的高度if(p->left=NULL&&p->right=NULL) if(n>height) height=n; if(p->left!=NULL)count(p->left,height,n+1); if(p->r

22、ight!=NULL) count(p->right,height,n+1);void paint(TNode *p)/打印樹 int height=0; int h=0; int i; using std:queue; queue<TNode*> 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=

23、pointer; pointer=aQueue.front(); aQueue.pop(); if(pointer->s>h) cout<<endl; h=pointer->s; if(pointer->t=1) for(i=0;i<pow(2,height-pointer->s)-1;i+) cout<<" " else if(lastpointer->s!=pointer->s)for(i=0;i<(pointer->t-1)*(pow(2,height-pointer->s+1)

24、-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<<pointer->oper; if(pointer->left!=NULL) pointer->left->s=pointer->s+1; pointer->left->t=pointer-&g