工大數(shù)據(jù)結(jié)構(gòu)第三章作業(yè)(共43頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)第三章 樹一、選擇題1、在一棵樹中，如果結(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則B的度為 D A. 1B. 2C. 3D. 42、深度為h的完全二叉樹至少有 D 個(gè)結(jié)點(diǎn)，至多有 B 個(gè)結(jié)點(diǎn)A. 2hB. 2h-1C. 2h+1D. 2h-12(h-1) -1 +1=2(h-1)前（n-1）層滿，第h層只有一結(jié)點(diǎn)3、具有n個(gè)結(jié)點(diǎn)的滿二叉樹有 C 個(gè)葉結(jié)點(diǎn)。A. n/2B. (n-1)/2C. (n+1)/2D. n/2+1因?yàn)?二叉樹中，有這樣一個(gè)性質(zhì)，如果其終端結(jié)點(diǎn)數(shù)（也就是）的個(gè)數(shù)為n1，度為2的結(jié)點(diǎn)數(shù)為n2，則n1=n2+1;假設(shè)有x個(gè)，則度為2的

2、個(gè)數(shù)為 x-1：所以： 2x-1 = n; 所以 x = (n+1)/2 ()所以 個(gè)數(shù)為 ：(n+1)/2非終端結(jié)點(diǎn)為 ： (n+1)/2-14、一棵具有25個(gè)葉結(jié)點(diǎn)的完全二叉樹最多有 B 個(gè)結(jié)點(diǎn)。A. 48B. 49C. 50D. 515、已知二叉樹的先根遍歷序列是ABCDEF，中根遍歷序列是CBAEDF，則后根遍歷序列是 A 。A. CBEFDAB. FEDCBAC. CBEDFAD. 不定6、具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有 B 個(gè)度為2的結(jié)點(diǎn)。A. 8B. 9C. 10D. 117、一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足 C 。A. 所有非葉結(jié)點(diǎn)均無左孩子

3、B. 所有非葉結(jié)點(diǎn)均無右孩子C. 只有一個(gè)葉子結(jié)點(diǎn)D. A和B同時(shí)成立8、在線索二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是 B 。A. t->left=NULLB. t->ltag=TRUEC. t->ltag=TRUE且t->left=NULLD. 以上都不對(duì)9、n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為 C 。A. 2nB. n-1C. n+1D. nn-1表示結(jié)點(diǎn)的左右子樹，其余n-1指針為空線索取代原來的空鏈10、二叉樹按照某種順序線索化后，任一結(jié)點(diǎn)都有指向其前驅(qū)和后繼的線索，這種說法 B 。A. 正確B. 錯(cuò)誤C. 不確定D. 都有可能11、具有n(n>1)個(gè)

4、結(jié)點(diǎn)的完全二叉樹中，結(jié)點(diǎn)i(2i>n)的左孩子結(jié)點(diǎn)是 D 。A. 2i B. 2i+1C. 2i-1D. 不存在12、具有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 C 。A. 5B. 6C.7D. 813、將一顆有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下、從左到右一次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為45的結(jié)點(diǎn)的右孩子的編號(hào)為 C 。A. 46B. 47C. 90D. 912i舉個(gè)簡單的例子就可以看出來，比如7個(gè)節(jié)點(diǎn)時(shí)（也就是三層時(shí)），編號(hào)為1的左子樹編號(hào)是2，編號(hào)2的左子樹是4，編號(hào)3的左子樹編號(hào)為6。以此就可以看出來。 左結(jié)點(diǎn)是2i,右結(jié)點(diǎn)才是2i+1 14、在結(jié)點(diǎn)數(shù)為n的堆中插入一個(gè)結(jié)點(diǎn)時(shí)，

5、復(fù)雜度為 C 。A. O(n)B. O(n2)C. O(log2n)D. O(logn2)15、兩個(gè)二叉樹是等價(jià)的，則它們滿足 D 。A. 它們都為空B. 它們的左右子樹都具有相同的結(jié)構(gòu)C. 它們對(duì)應(yīng)的結(jié)點(diǎn)包含相同的信息 D. A、B和C16、包含n個(gè)元素的堆的高度為 C 。（符號(hào)a表示取不小a最小整數(shù)）A. nB. log2nC. log2(n+1)D. n+117、以下說法錯(cuò)誤的是 B 。A. 存在這樣的二叉樹，對(duì)其采用任何次序的遍歷其結(jié)點(diǎn)訪問序列均相同B. 二叉樹是樹的特殊情形C. 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的D. 在二叉樹中只有一棵子樹的情形下，也要指出是左子樹還是右子樹

6、18、設(shè)F是一個(gè)森林，B是由F變換得到的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中沒有右孩子的結(jié)點(diǎn)有 C 個(gè)。A. n-1B. nC. n+1D. n+219、將一棵樹T轉(zhuǎn)換為二叉樹B，則T的后根序列是B的 B 。A. 先根序列B. 中根序列C. 后根序列D. 層次序列20、將一棵樹轉(zhuǎn)換為二叉樹后，這顆二叉樹的形態(tài)是 A 。A. 唯一的，根結(jié)點(diǎn)沒有左孩子B. 唯一的，根結(jié)點(diǎn)沒有右孩子C. 有多種，根結(jié)點(diǎn)都沒有左孩子D. 有多種，根結(jié)點(diǎn)都沒有右孩子樹轉(zhuǎn)換成二叉樹，根節(jié)點(diǎn)是沒有右孩子的，這由轉(zhuǎn)換規(guī)則應(yīng)該不難理解，且轉(zhuǎn)換規(guī)則是唯一的，所以轉(zhuǎn)換成的二叉樹是唯一的21、設(shè)樹T的度為4，其中度為1, 2, 3

7、, 4的結(jié)點(diǎn)個(gè)數(shù)分別為4, 2, 1, 1，則T中的葉結(jié)點(diǎn)的個(gè)數(shù)為 D 。A. 5B. 6C. 7D. 822、設(shè)森林F中有三棵樹，第一、第二、第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1, M2, M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)為 D 。A. M1-1B. M1+M2C. M2D. M2+M323、若以二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是 C 。A. 二叉排序樹B. 哈夫曼樹C. 堆D. 線索二叉樹24、用5個(gè)權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是 B 。A. 32B. 33C. 34D. 15二、填空題1、一棵二叉樹有67

8、個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的度是0和2。問這棵二叉樹中度為2的結(jié)點(diǎn)有 33 個(gè)。2、含A, B, C三個(gè)結(jié)點(diǎn)的不同形態(tài)的二叉樹有 5 棵。3、含有4個(gè)度為2的結(jié)點(diǎn)和5個(gè)葉子結(jié)點(diǎn)的完全二叉樹，有 1或0 個(gè)度為1的結(jié)點(diǎn)。4、具有100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為 50 。5、在用左右鏈表示的具有n個(gè)結(jié)點(diǎn)的二叉樹中，共有 2n 個(gè)指針域，其中 n-1 個(gè)指針域用于指向其左右孩子，剩下的 n+1 個(gè)指針域是空的。 6、如果一顆完全二叉樹的任意一個(gè)非終結(jié)結(jié)點(diǎn)的元素都 不小于 其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)(如果有的話)的元素，則稱此完全二叉樹為最大堆。7、堆是一種特殊形式的 完全 二叉樹，對(duì)于最大堆而言，其根結(jié)點(diǎn)的元

9、素的值應(yīng)該是所有結(jié)點(diǎn)元素中 最大 的。8、二叉樹的復(fù)制是指按照一棵已知的二叉樹復(fù)制一個(gè)副本，使兩者 等價(jià) 。復(fù)制二叉樹最長用的方法是 后根遍歷遞歸算法 。9、在定義堆時(shí)，通常采用 結(jié)構(gòu)體 方式定義相應(yīng)的二叉樹，這樣可以很容易實(shí)現(xiàn)其相關(guān)操作。10、在構(gòu)建選擇樹時(shí)，根據(jù)孩子結(jié)點(diǎn)的獲勝者確定他們雙親結(jié)點(diǎn)所得到的選擇樹稱為 勝者樹 。根據(jù)孩子結(jié)點(diǎn)的失敗者確定他們雙親結(jié)點(diǎn)所得到的選擇樹稱為 敗者樹 。11、樹的表示方法包括 數(shù)組 、 鄰接表 和 左右鏈 。12、表達(dá)式(a+b*(c-d)-e/f的波蘭式(前綴式)是 -+a*b-cd/ef ，逆波蘭式(后綴式)是 abcd-*+ef/- 。13、設(shè)F是由

10、T1、T2、T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B。已知T1, T2, T3的結(jié)點(diǎn)數(shù)分別為n1, n2和n3，則二叉樹B的左子樹中有 n1-1 個(gè)結(jié)點(diǎn)，二叉樹B的右子樹中有 n2+n3 個(gè)結(jié)點(diǎn)。14、設(shè)二叉樹的中根序列為ABCDEFG，后根序列為BDCAFGE。則該二叉樹的先根序列為 EACBDGF 。該二叉樹對(duì)應(yīng)的森林中包含 2 棵樹。15、先根次序遍歷森林等同于按 先根 遍歷對(duì)應(yīng)的二叉樹，后根次序遍歷森林等同與按 中根 遍歷對(duì)應(yīng)的二叉樹。16、一棵哈夫曼樹有19個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)的個(gè)數(shù)為 10 。17、設(shè)有數(shù)據(jù)WG=7, 19, 2, 6, 32, 3, 21, 10葉節(jié)點(diǎn)權(quán)重集合，

11、則所構(gòu)建哈夫曼樹的高是 5 ，帶權(quán)路徑長度WPL為 169 。18、設(shè)有一份電文中共使用6個(gè)字符a, b, c, d, e, f，其中出現(xiàn)頻率依次為2，3，4，7，8，19，則字符c的哈夫曼編碼是 001 ，電文編碼的總長度為 80 。20、在有n個(gè)結(jié)點(diǎn)的哈夫曼樹中，葉子結(jié)點(diǎn)總數(shù)為 (n+1)/2 ，非葉結(jié)點(diǎn)的總數(shù)為 (n-1)/2 。3、 試分別畫出具有4個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。四、已知一棵二叉樹的中根序列和后根序列分別是BDCEAHFG和DECBHGFA，請畫出此二叉樹。五、已知非空二叉樹T，寫一個(gè)算法，求度為2的結(jié)點(diǎn)的個(gè)數(shù)。要求：1、定義二叉樹的抽象數(shù)據(jù)類型和型BTREE，并定義基

12、本操作。2、編寫函數(shù)count2(BTREE T)，返回度為2的節(jié)點(diǎn)的個(gè)數(shù)。 3、在主函數(shù)中，構(gòu)建一個(gè)二叉樹，并驗(yàn)證所編寫的算法。六、用遞歸方法寫一個(gè)算法，求二叉樹的葉子結(jié)點(diǎn)數(shù)int leafnum(BTREE T)。要求：1、 定義二叉樹的抽象數(shù)據(jù)類型和型BTREE，并定義基本操作。2、 編寫函數(shù)leafnum(BTREE T)，返回樹T的葉子節(jié)點(diǎn)的個(gè)數(shù)。在主函數(shù)中，構(gòu)建一個(gè)二叉樹，并驗(yàn)證所編寫的算法。7、 畫出下圖所表示的二叉樹的中序線索二叉樹和先序線索二叉樹。 八、已知二叉樹的先根序列是AEFBGCDHIKJ，中根序列是EFAGBCHKIJD，畫出此二叉樹，并畫出后序線索二叉樹。九、在中

13、序線索二叉樹中插入一個(gè)結(jié)點(diǎn)Q作為樹中某個(gè)結(jié)點(diǎn)P的左孩子，試給出相應(yīng)的算法。要求：1、 定義中序線索二叉樹的型THTREE以及基本操作。2、 定義函數(shù)void LInsert(THTREE P, THTREE Q); 實(shí)現(xiàn)題目要求的操作。在主函數(shù)中，利用操作RInsert和LInsert構(gòu)造一個(gè)線索二叉樹，并中序輸出二叉樹的結(jié)點(diǎn)的元素，驗(yàn)證結(jié)果。#include<iostream>#include<iomanip>#include<cmath>#include<cstdlib>#include<string>using namespac

14、e std;typedef int elementtype;struct node/節(jié)點(diǎn)的型 node* lchild;node* rchild;bool ltag;bool rtag;elementtype element;typedef node* head;/指向樹根roottypedef node* tree;/指向線索樹的根節(jié)點(diǎn) void makeNull(head& h)/將線索二叉樹置空 h->lchild=h;h->ltag=false;h->rchild=h;h->rtag=true; head pointTotree(head& h,

15、tree& t)/令head指向tree,注意head指向的并不是根節(jié)點(diǎn)，tree指向根節(jié)點(diǎn) h->lchild=t;h->rchild=h;h->ltag=true;h->rtag=true; return h; /中根遍歷的下一個(gè)節(jié)點(diǎn)node* inNext(node* p)node* q=p->rchild;if(p->rtag=true)/如果有右子樹，找出右子樹的最左節(jié)點(diǎn) while(q->ltag=true)q=q->lchild;return q; /中根遍歷的上一個(gè)節(jié)點(diǎn) node* inPre(node* p)node *

16、q= p->lchild; if(p->ltag=true)/如果P的左子樹存在，則其前驅(qū)結(jié)點(diǎn)為左子樹的最右結(jié)點(diǎn)while(q->rtag=true) q=q->rchild; return q;/左子樹的最右結(jié)點(diǎn)/中序遍歷 void thInOrder(head h)node* temp;temp=h;dotemp=inNext(temp);if(temp!=h)cout<<temp->element<<" "while(temp!=h); /插入右孩子void rInsert(node* s,node* r)node

17、* w;r->rchild=s->rchild;r->rtag=s->rtag;r->lchild=s;r->ltag=false;/新插入的節(jié)點(diǎn)木有左子樹，所以lchild指向的是父節(jié)點(diǎn)s->rchild=r;s->rtag=true;/原節(jié)點(diǎn)的右孩子為新插入的節(jié)點(diǎn)if(r->rtag=true)/這里是神馬意思呢q|?|p，就是如果被插節(jié)點(diǎn)s有右子樹 ，/找出被插節(jié)點(diǎn)s的的next位置，即右子樹中的最左節(jié)點(diǎn)，令其lchild指向新添加的節(jié)點(diǎn)r /因?yàn)椴迦肭霸撟钭蠊?jié)點(diǎn)的lchild指向的是原來節(jié)點(diǎn)s w=inNext(r);w->l

18、child=r;/插入左孩子void lInsert(node* s,node* l)node* w;l->lchild=s->lchild;l->ltag=s->ltag;l->rchild=s;l->rtag=false;s->lchild=l;s->ltag=true;if(l->ltag=true)/與插入右孩子方法相似，只需把左右方向?qū)φ{(diào)即可 w=inPre(l);w->rchild=l; int main()head h=new node;node* root=new node;node* lc=new node;node

19、* rc=new node;node* c=new node;root->element=1;lc->element=2;rc->element=3;c->element=4;h->rchild=root;h->lchild=h;h->ltag=true;h->rtag=true;root->lchild=h;root->rchild=h;root->ltag=false;root->rtag=false;/構(gòu)造線索樹213 lInsert(root,lc);rInsert(root,rc);thInOrder(h);co

20、ut<<endl;/root左邊插入ClInsert(root,c);thInOrder(h); return 0;十、假設(shè)現(xiàn)在有如下的元素：7、16、49、82、5、31、6、2、44。畫出將每一個(gè)元素插入堆中以后的最大堆。要求：利用基本操作Insert的基本原理，先用第一個(gè)元素7構(gòu)成一個(gè)二叉樹，然后將第二個(gè)元素16插入該二叉樹中，再將第三個(gè)元素49插入堆中，直到最后一個(gè)元素插入為止。上述過程要求畫圖完成。十一、編寫一個(gè)函數(shù)，在最大堆中查找任意元素，并分析其時(shí)間復(fù)雜度。要求：1、 定義最大堆的型HEAP及其基本操作。2、 定義函數(shù)int Find(HEAP H, Elementt

21、ype e)，查找e是否為堆的元素，如果是，返回該元素在堆中的位置，如果不是，返回0。（提示：利用最大堆的元素特點(diǎn)進(jìn)行查找，可降低復(fù)雜度）在主函數(shù)中首先構(gòu)建一個(gè)二叉樹，然后驗(yàn)證所構(gòu)造的函數(shù)。typedefstryct int key; datathpe data; elementtype; Typedefstruct Elementtype elementsMaxsize; int n; HEAP; Void MaxHeap(HEAP heap)/創(chuàng)建一個(gè)空堆 heap.n=0; Bool HeapEmpty(HEAP heap)/判斷堆是否為空 If(!(heap.n)return true

22、; Else return false; Bool HeapFull(HEAP heap)/判斷堆是否為滿 if(heap.n=Maxsize-1) return true; Else return false; Void Insert(HEAP&heap,elementtype element)/在堆heap中插入元素為element的結(jié)點(diǎn) Int I; If(!HeapFull(heap) I=heap.n+1; While(i!=1)&&(element.data>heap.elementsi/2.data) heap.elementsi=heap.elem

23、entsi/2; i/=2; Heap.n+; Heap.elementsi=element; Elementtype DeleteMax(HEAP&heap)/刪除堆中最大元素 int paraent=1,child=2; Elementtype element,tmp; If(!HeapEmpty(heap) Element=heap.elements1; Tmp=heap.elementsheap.n-; While(child<=heap.n) If(child<heap.n)&&(heap.elementschild.data<heap.el

24、ementschild+1.data)child+; If(tmp.data>=heap.elementschild.data)break; Heap.elementsparaent=heap.elementschild; Paraent=child; Child*=2; Heap.elementsparaent=tmp; Return element; Int Find(HEAP,datatype x) int m=1; While(m<H.n)&&(H.elementsm.data!=x) If(H.elementsm.data<x) If(H.eleme

25、ntsm+1.data>=x) m+; else return 0; else m+; if(m<=H.n)return m; else return 0; Int main() HEAP H; Elementtype element; Int data=1,3,5,7,9,11,13; H.n=0; For(int i=0;i<7;i+) element.key=i+1; Element.data=datai; Insert(H,element); for(int i;i<=H.n;i+)cout<<H.elementsi.data<<endl

26、; DeleteMax(H); For(int i=1;i<=H.n;i+)cout<<H.elementsi.data<< Cout<,endl; Cout<<”查找的元素：”; Int x; Cin>>x; Cout<<Find(H,x)<<endl;十二、給定葉子結(jié)點(diǎn)的權(quán)值集合15, 3,14, 2, 6, 9, 16, 17，構(gòu)造相應(yīng)的哈夫曼樹，并計(jì)算其帶權(quán)路徑長度。十三、已知n=9和一組等價(jià)關(guān)系： 15、68、72、98、37、42、93 試應(yīng)用抽象數(shù)據(jù)類型MFSET設(shè)計(jì)一個(gè)算法，按輸入的等價(jià)關(guān)系進(jìn)行

27、等價(jià)分類。#include<iostream.h> #define n 9 /MEFSET元素個(gè)數(shù)   /MFSET抽象數(shù)據(jù)型struct mfnode  int father;/指向父節(jié)點(diǎn)的鏈 int count;/樹結(jié)點(diǎn)個(gè)數(shù)   typedef mfnode MFSETn+1;  void Union(int A, int B, MFSET 

28、C)/合并A和B  if(CA.count>CB.count)     CB.father=A;/B并入A   CA.count+=CB.count;    else    CA.father=B;/A并入B   CB.count+=CA.count;     int Find(int x, MFSET

29、 C)/求包含元素x的樹的根   int f;  f=x; while(Cf.father!=0)/未到根   f=Cf.father;  return f;   void Initial(int A, MFSET C)/集合A只包含元素A   CA.father=0;  CA.count=1;   /

30、60;等價(jià)分類 void Equivalence(MFSET S)   int i, j, m, k;  for(i=1; i<=n; i+)   Initial(i, S);  cin>>i; cin>>j;  while(!(i=0 && j=0)/輸入0,0結(jié)束等價(jià)分類  &#

31、160;  k=Find(i, S);   m=Find(j, S);   if(k!=m)    Union(k, m, S);   cin>>i; cin>>j;     void print_MFSET(MFSET S)/輸出等價(jià)類   int rn+1n+1

32、=0, k;  for(int i=1; i<=n; i+)     k=Find(i, S);   rk0+;   rkrk0=i;    for(i=1; i<=n; i+)     if(ri0>0)       c

33、out<<''    for(int j=1; j<ri0; j+)   cout<<rij<<',' cout<<riri0<<''<<endl;       void main()   MFSET S;  Equival

34、ence(S);  print_MFSET(S);  十四、畫出下圖所示的森林經(jīng)轉(zhuǎn)換后所對(duì)應(yīng)的二叉樹，并指出在二叉樹中某結(jié)點(diǎn)為葉子結(jié)點(diǎn)時(shí)，所對(duì)應(yīng)的森林中結(jié)點(diǎn)應(yīng)滿足的條件。十五、已知森林F的先根序列為：ABCDEFGHIJKL，后根序列為：CBEFDGAJIKLH，試畫出森林F。提示：先畫出森林F所對(duì)應(yīng)的二叉樹B，然后再將B轉(zhuǎn)換為森林。十六、畫出表達(dá)式(A+B*C/D)*E+F*G所對(duì)應(yīng)的樹結(jié)構(gòu)，并寫出該表達(dá)式的波蘭表示式和逆波蘭表示式。十七、利用逆波蘭表達(dá)式求一個(gè)四則混合元算的值。具體要求：1、 定義二叉樹的型BTREE和位置的型position。2、

35、實(shí)現(xiàn)二叉樹的基本操作。3、 實(shí)現(xiàn)將一個(gè)四則混合運(yùn)算轉(zhuǎn)換成二叉樹的函數(shù)：BTREE convert(char *express)，其中參數(shù)express為四則混合運(yùn)算表達(dá)式，返回值為生成的樹。4、 實(shí)現(xiàn)計(jì)算四則混合運(yùn)算的值的函數(shù)：double computer(BTREE bt)，其中，參數(shù)bt為四則運(yùn)算所對(duì)應(yīng)的樹，返回值為計(jì)算結(jié)果。提示：先求樹的的波蘭表達(dá)式，然后利用棧結(jié)構(gòu)計(jì)算表達(dá)式的值。在主函數(shù)中進(jìn)行測試，求2+3*（5+8）/4-5的值。#include"./stack.cpp"#include<iostream>#include<sstream>

36、;#define MAXSIZE 30using namespace std;char match=">><<<>>>><<<>>>>>><>>>>>><>><<<<<= >>>> >><<<<< ="char opera="+-*/()"const char& Match(const

37、char &ch1,const char &ch2)int i=0,j=0;while(operai!=ch1) i+;while(operaj!=ch2) j+;return matchi*7+j;class TNodepublic:TNode(string str="",int b=0,TNode *l=NULL,TNode *r=NULL,TNode *p=NULL)strcpy(id,str.c_str();bit=b;left=l;right=r;parent=p;TNode(const char ch,TNode *l=NULL,TNode *r

38、=NULL,TNode *p=NULL)id0=ch;id1=0;bit=0;left=l;right=r;parent=p;const TNode& operator=(const TNode& tn)strcpy(id,tn.id);bit=tn.bit;left=tn.left;right=tn.right;parent=tn.parent;char idMAXSIZE;int bit;TNode *parent,*left,*right;int ReadExpr(char *str,char *expr,int start,int bit,int &length

39、)length=0;if(strstart=0)expr0=0;return 0;else if(strstart='*'|strstart='/'|strstart='('|strstart=')'|strstart='')expr0=strstart;expr1=0;length=1;return 2;else if(bit|isdigit(strstart)|strstart='.') /read a digit stringint b=0;int k=0; /index for exprwh

40、ile(strstart='+'|strstart='-') /read signif(strstart='-') b+;start+;length+;if(b%2) exprk+='-'while(isdigit(strstart)|strstart='.')exprk+=strstart+;length+;exprk=0;return 1;else if(strstart='+'|strstart='-') /read a oper '+' or '-&#

41、39;int b=0;while(strstart='+'|strstart='-')if(strstart='-') b+;start+;length+;if(b%2) expr0='-'else expr0='+'expr1=0;return 2;else return -1; /errorTNode *Translate(const string &str) /translate a expression string to a expression treechar substrMAXSIZE;St

42、ack<char> cstk;Stack<TNode*> tstk;char *tempstr=new charstr.length()+2;int start=0,bit=1;int t,length;strcpy(tempstr,str.c_str();tempstrstr.length()=''tempstrstr.length()+1=0;cstk.push('');t=ReadExpr(tempstr,substr,start,bit,length);while(cstk.top()!=''|substr0!=&

43、#39;')if(t=1) /is a digit stringTNode *np=new TNode(substr,1);tstk.push(np);bit=0;else if(t=2) /is a operif(substr0='(') bit=1;else bit=0;char tch=cstk.top();if(Match(tch,substr0)='>')TNode *right=tstk.top();tstk.pop();TNode *left=tstk.top();tstk.pop();TNode *np=new TNode(tch,

44、left,right);left->parent=np;right->parent=np;tstk.push(np);cstk.pop();continue;else if(Match(tch,substr0)='<') cstk.push(substr0);else cstk.pop();start+=length;t=ReadExpr(tempstr,substr,start,bit,length);delete tempstr; return tstk.top();void print(TNode *root)if(root->left)print

45、(root->left);print(root->right);cout<<root->id;else cout<<root->id;void prints(TNode*);double solve(TNode*);void printExpr(string str)TNode *root=Translate(str);cout<<"后綴式:"print(root);cout<<endl; cout<<"中綴式:"prints(root);cout<<&quo

46、t;="<<solve(root)<<endl;void prints(TNode *root) /將逆波蘭式用中綴形式打印出來if(root->left=NULL) cout<<root->id; /is a leafelse if(root->parent=NULL)prints(root->left);cout<<root->id;prints(root->right);else if(root->parent->left=root&&Match(root->i

47、d0,root->parent->id0)='>')prints(root->left);cout<<root->id;prints(root->right);else if(root->parent->right=root)if(Match(root->parent->id0,root->id0)='<'|root->parent->id0='+')prints(root->left); cout<<root->id; pri

48、nts(root->right);elsecout<<"(" prints(root->left); cout<<root->id; prints(root->right); cout<<")"elsecout<<"("prints(root->left);cout<<root->id;prints(root->right);cout<<")"double solve(TNode *root)if(ro

49、ot->left=NULL)istringstream in;in.str(root->id);double value;in>>value;return value;elseswitch(root->id0)case '+':return solve(root->left)+solve(root->right);case '-':return solve(root->left)-solve(root->right);case '*':return solve(root->left)*s

50、olve(root->right);case '/':return solve(root->left)/solve(root->right);void Check(char *str) /判斷為帶符號(hào)且緊跟括號(hào)的情況,酌情在前面添"0-"int k=0,i=0;if(str0='+'|str0='-')int b=0;while(strk='+'|strk='-')if(strk='-') b+;k+;if(strk!='(') return;char *np=new charstrlen(str)+3;if