北工大數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告3

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

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

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

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

5、讀入的是運(yùn)算符，并且運(yùn)算符棧為空，則將該運(yùn)算符直接進(jìn)棧；如果棧不為空， 則比較該運(yùn)算符和棧頂運(yùn)算符的優(yōu)先級。      若該運(yùn)算符高于棧頂運(yùn)算符的優(yōu)先級，則將該運(yùn)算符直接進(jìn)棧； 若該運(yùn)算符低于或等于棧頂運(yùn)算符的優(yōu)先級，則將棧中高于或等于該運(yùn)算符優(yōu)先級的元 素依次出棧輸出到后綴表達(dá)式中，然后再將該運(yùn)算符進(jìn)棧。 在碰到開括號和棧為空前反復(fù)彈出棧中元素 若棧非空棧頂不是左括號且棧頂元素優(yōu)先級不低于輸入運(yùn)算符時(shí)，/將棧頂元素彈出到后綴表達(dá)式二叉樹表達(dá)式轉(zhuǎn)化為表達(dá)式 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)/中序遍歷，同時(shí)輸出不帶冗余括號的中綴表達(dá)式 if(p)if(p->left) if(如果當(dāng)前節(jié)點(diǎn)的左子樹是運(yùn)算符，且運(yùn)算符優(yōu)先級低于當(dāng)前運(yùn)算符，那么左邊的表達(dá)式要先計(jì)算，需要加括號

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

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

9、符代替TNode *left;TNode *right;int s;int t;/計(jì)算樹的層數(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)/判斷是否為運(yùn)算符char oper='(',')','+','-','*','/',''for(int i=0;i<sizeof(oper);i+) if(op=ope

10、ri) return true; return false;int getOperOrder(char op)/返回運(yùn)算符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)/中序遍歷，同時(shí)輸出不帶冗余括號的中綴表達(dá)式 if(p)if(p->left) /如果當(dāng)前節(jié)點(diǎn)的左子樹是運(yùn)算符，且運(yùn)算符優(yōu)先級低于當(dāng)前運(yùn)算符，/那么左邊的表達(dá)式要先計(jì)算，需要加括號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;/輸出當(dāng)前節(jié)點(diǎn) if(p->right) /如果當(dāng)前節(jié)點(diǎn)的右子樹是運(yùn)算符，且運(yùn)算符優(yōu)先級不高于當(dāng)前運(yùn)算符，/那么右邊的表達(dá)式要先計(jì)算，需要加括號 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)/后綴表達(dá)式生成二叉樹 /（a）碰到操作數(shù)則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點(diǎn)，若棧為空則地址壓棧，/（b）碰到操作符則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點(diǎn)，取棧頂元素，/若當(dāng)前元素的左孩子為空則設(shè)為其左孩子，/左孩子為滿則設(shè)為其右孩子,開始那個(gè)元素地址為根結(jié)點(diǎn)地址，開始時(shí)用變量root保存。stack <TNode*> nodeStack;/用于保存節(jié)

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

16、子 nodeStack.pop(); if(nodeStack.size() p->left=nodeStack.top();/若非空則彈棧并設(shè)為結(jié)點(diǎn)的左孩子 nodeStack.pop(); nodeStack.push(p); temp=stri+; void pre2tree(TNode *&p, string str)/前綴表達(dá)式生成二叉樹/碰到操作數(shù)則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點(diǎn)，地址壓棧；/碰到操作符則把其值賦給相應(yīng)的新申請的二叉樹，并從棧中彈出兩個(gè)地址，/分別作為其左指針和右指針，然后再把其地址壓棧，最后一個(gè)地址即為二叉樹的根結(jié)點(diǎn)地址。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é)點(diǎn) nodeStack.push(p); temp=stri-; else p=new TNode(temp); if(nodeStack.size()/棧非空 p->left=nodeStack.top(); /則棧頂指針?biāo)附Y(jié)點(diǎn)設(shè)置成當(dāng)前結(jié)點(diǎn)左孩子 nodeS

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

19、emp=stri+; while(temp!='0') if(!isOper(temp)/操作數(shù)則直接進(jìn)數(shù)據(jù)棧 Postfixexp+=temp; temp=stri+; else if(temp='(')/進(jìn)棧 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)先級不低于輸入運(yùn)算符時(shí)，/將棧頂元素彈出到后綴表達(dá)式中，并且str下標(biāo)加 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