數(shù)據(jù)結(jié)構(gòu)課件：10 第四章 樹3[新]

1、4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應(yīng)用第四章 樹4.4.1樹與二叉樹的轉(zhuǎn)換4.4.2樹的順序存儲4.4.3樹的鏈接存儲4.4.4樹和森林的遍歷4.4 樹和森林4.4.1樹與二叉樹的轉(zhuǎn)換 1) 樹轉(zhuǎn)換成二叉樹 2) 森林轉(zhuǎn)換成二叉樹 3) 二叉樹轉(zhuǎn)換成樹 4) 二叉樹轉(zhuǎn)換成森林1）樹轉(zhuǎn)換成二叉樹 所有兄弟結(jié)點之間加一線； 對每個結(jié)點，除了保留與其長子的連線外，去掉該結(jié)點與其他孩子的連線。 按順時針方向?qū)⑺D(zhuǎn)45。 ACBFDEACBFDE樹由樹轉(zhuǎn)換的二叉樹 把森林中第一棵樹T1的根作為整個森林的根； 把森林中其它樹的根依次作為T1的兄弟結(jié)點

2、。2）森林轉(zhuǎn)換成二叉樹 二叉樹GJHIFEACBDACBDFEGJHI3)二叉樹轉(zhuǎn)換成樹ACBFDE由二叉樹轉(zhuǎn)換的樹ACBFDE二叉樹 GJHIFEACBDACBDFEGJHI4）二叉樹轉(zhuǎn)成森林4.4.1樹與二叉樹的轉(zhuǎn)換4.4.2樹的順序存儲4.4.3樹的鏈接存儲4.4.4樹和森林的遍歷4.4 樹和森林樹的順序存儲結(jié)構(gòu)1)先根序列及結(jié)點次數(shù)表示法2)后根序列及結(jié)點次數(shù)表示法3)層次序列及結(jié)點次數(shù)表示法4)層次序列及Father數(shù)組表示法1) 樹的先根序列及結(jié)點次數(shù)表示法樹的先根遍歷的定義（1）訪問根結(jié)點（2）從左到右依次先根次序遍歷樹的諸子樹RADEFCBGKH先根序列RADEBCFGHK定理

3、4.2 如果已知一個樹的先根序列和每個結(jié)點相應(yīng)的次數(shù)，則能唯一確定該樹的結(jié)構(gòu)。證明：用數(shù)學(xué)歸納法1. 若樹中只有一個結(jié)點，定理顯然成立。2. 假設(shè)樹中結(jié)點個數(shù)小于n(n2)時定理成立。3. 當(dāng)樹中有n個結(jié)點時，由樹的先根序列可知，第一個結(jié)點是根結(jié)點，設(shè)該結(jié)點的次數(shù)為k, k1，因此根結(jié)點有k個子樹。第一個子樹排在最前面，第k個子樹排在最后面，并且每個子樹的結(jié)點個數(shù)小于n，由歸納假設(shè)可知，每個子樹可以唯一確定，從而整棵樹的樹形可以唯一確定。證畢。 例：先根序列： A B C D E F G H I J K L 結(jié)點的次數(shù): 4 0 3 0 0 0 0 2 2 0 0 0 2) 后根序列和結(jié)點次數(shù)

4、表示法后根序列 B D E F C G J K I L H A結(jié)點的次數(shù) 0 0 0 0 3 0 0 0 2 0 2 43) 層次序列和結(jié)點次數(shù)表示法已知一個樹的層次序列和每個結(jié)點次數(shù)，則能唯一確定該樹的結(jié)構(gòu)。層次序列 A B C D E F結(jié)點的次數(shù) 3 0 2 0 0 04) 層次序列和Father數(shù)組表示法便于涉及祖先的操作，求結(jié)點的孩子時需要遍歷整棵樹。4.4.1樹與二叉樹的轉(zhuǎn)換4.4.2樹的順序存儲4.4.3樹的鏈接存儲4.4.4樹和森林的遍歷4.4 樹和森林 (1) Father鏈接結(jié)構(gòu):ACBFDEACBDFEFather鏈接提供了“向上”訪問的能力，但很難確定一個結(jié)點是否為葉結(jié)

5、點，也很難求結(jié)點的子結(jié)點，且不易實現(xiàn)遍歷操作。(2)孩子鏈接結(jié)構(gòu)*會出現(xiàn)大量指針為空的情況，浪費空間。 *節(jié)省了空間，但給操作和管理帶來不便。(3)孩子鏈表表示法*孩子鏈表表示法是為樹中每個結(jié)點設(shè)置一個孩子鏈表，并將這些結(jié)點及相應(yīng)的孩子鏈表的頭指針存放在一個數(shù)組中。孩子結(jié)點的數(shù)據(jù)域僅存放了它們在數(shù)組空間的下標(biāo)。*與Father鏈接表示法相反，孩子鏈表表示便于實現(xiàn)涉及孩子及其子孫的運算，但不便于實現(xiàn)與父結(jié)點有關(guān)的操作。 (4)父親孩子鏈表表示*將Father數(shù)組表示法和孩子鏈表表示法結(jié)合起來，可形成父親孩子鏈表表示法。 結(jié)點結(jié)構(gòu)firstChildnextBrotherData(5)左孩子-右兄

6、弟鏈接結(jié)構(gòu)（二叉樹表示法）*這種存儲結(jié)構(gòu)的最大優(yōu)點是：它和二叉樹的二叉鏈表表示完全一樣?？衫枚鏄涞乃惴▉韺崿F(xiàn)對樹的操作。RADEFCBGKHRADECHFGBK左孩子-右兄弟表示法示例：樹的左孩子右兄弟表示法的實現(xiàn)結(jié)點類TreeNodetemplate class TreeNode friend class Tree ; private: T data ; TreeNode *firstChild，*nextBrother ; pulic: TreeNode(T value , TreeNode*L, TreeNode *R ) / 構(gòu)造函數(shù) TreeNode( ) ；樹類Tree的聲明t

7、emplateclass Tree private : TreeNode *root ;/ 根結(jié)點 public : Tree ( ); / 構(gòu)造函數(shù) Tree ( ); / 析構(gòu)函數(shù) TreeNode * FirstChild (TreeNode *p); /返回結(jié)點p的大兒子結(jié)點 TreeNode * NextBrother ( TreeNode *p); /返回結(jié)點p的下一個兄弟結(jié)點 TreeNode * FindFather ( TreeNode *t , TreeNode *p ); /在樹t中搜索p的父結(jié)點TreeNode * FindTarget ( TreeNode *t ,

8、T target ); /在樹t中搜索值為target的結(jié)點 void DelSubtree ( TreeNode *t ,TreeNode *p ); /在樹t中刪除以p為根的子樹 void Del ( TreeNode *p ); void PreOrder (TreeNode * t); /先根遍歷以t為根結(jié)點的樹 void NorecPreOrder (TreeNode * t ); /非遞歸先根遍歷以t為根結(jié)點的樹 void LevelOrder ( TreeNode * t ); /層次遍歷以t為根結(jié)點的樹 ;FindFather(t, p)算法思想：令q指向t的大兒子結(jié)點，若q=

9、p，t就是p的父結(jié)點；否則，在以q為根的子樹中找p的父結(jié)點，即 FindFather(q,p);若未找到，令q指向t的下一個兒子結(jié)點，即q的右兄弟結(jié)點，重復(fù)上述步驟，直至找到p的父結(jié)點或找完t的所有兒子結(jié)點。 搜索父結(jié)點 算法FindFather( t, p. result)FF1尋找t的第一棵子樹 IF t OR p THEN RETURN result ELSE qFistChild (t).FF2從t的第一棵子樹開始搜索，若搜索到，則返回；否則，搜索t的下一棵子樹 WHILE q AND qp DO ( FindFather( q , p. result) IF result THEN

10、qNextBrother(q) ELSE RETURN result . )FF3遞歸出口：若p是t的一個子結(jié)點，令指針 result 指向t IF q p THEN RETURN result t . ELSE RETURN result . ACBFDEACBFDEFindTarget (t , target )算法思想：若t的數(shù)據(jù)域為target，則指針result指向t；否則，p指向t的大兒子結(jié)點，在以p為根的樹中進行搜索(遞歸調(diào)用)若在以p為根的樹中搜索失敗，p指向其右兄弟結(jié)點，繼續(xù)進行上述搜索，直到找到數(shù)據(jù)域等于target的結(jié)點或p為空。 搜索指定數(shù)據(jù)域的結(jié)點算法FindTarg

11、et(t, target. result)FT1t不存在或為所求 IF t THEN RETURN result . IF Data (t) target THEN ( RETURN result t . )FT2從t的第一棵子樹開始搜索 p FistChild ( t ) . WHILE p DO ( FindTarget (p , target. result). IF result THEN pNextBrother( p ) ELSE RETURN result . )FT3在以t為根的樹中，沒有搜索到數(shù)據(jù)成員等于target的結(jié)點 RETURN result . 搜索大兒子結(jié)點和大兄

12、弟結(jié)點算法GFC(p. q)GFC1. 指針p所指結(jié)點存在，并且存在大兒子結(jié)點 IF p AND FistChild (p ) THEN RETURN q FistChild (p ) . GFC2. 大兒子結(jié)點不存在 RETURN q . 算法GNB ( p . q )GNB1. 指針p所指結(jié)點存在，并且存在下一個兄弟結(jié)點 IF p AND NextBrother (p ) THEN RETURN q NextBrother (p ). GNB2. 大兒子結(jié)點不存在 RETRUN q . 三種情況：1、刪除以根結(jié)點R為根的樹2、刪除以大兒子結(jié)點A為根的子樹3、刪除以結(jié)點B或C(非大兒子)為根

13、的子樹RADEFCBGKH 刪除子樹 刪除子樹算法DS (t, p ) /修改p的父結(jié)點指針域DS1. t或p不存在 IF t OR p THEN RETURN.DS2. 確定p所指結(jié)點的父結(jié)點是否存在 FindFather( t , p . result). IF result THEN Del(p) RETURN.DS3. 若p所指結(jié)點的父結(jié)點存在，并且p是其父結(jié)點的大兒子結(jié)點 IF FistChild ( result ) p THEN (FistChild ( result ) NextBrother ( p ). Del ( p ). RETURN. )DS4. 若p所指結(jié)點的父結(jié)點

14、存在，并且p不是其父結(jié)點的大兒子結(jié)點，則搜索p的前一個兄弟結(jié)點q q FistChild ( result ). WHILE NextBrother ( q ) p DO q NextBrother ( q ). NextBrother ( q ) NextBrother ( p ). Del ( p ). RETURN. 算法Del ( p )/*釋放根為p的子樹所占用的空間 */ Del1. 指針p所指結(jié)點不存在，則返回 IF p THEN RETURN.Del2. 從左到右刪除p的子樹 q FistChild ( p ). WHILE q DO ( next NextBrother (

15、q ) . Del ( q ) . q next . ) AVAIL p . ACBFDEACBFDE4.4.1樹與二叉樹的轉(zhuǎn)換4.4.2樹的順序存儲4.4.3樹的鏈接存儲4.4.4樹和森林的遍歷4.4 樹和森林1、樹的遍歷 先根遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷每棵子樹。先根遍歷序列：A B C E F DACBFDE后根遍歷：先依次后根遍歷每棵子樹，然后訪問樹的根結(jié)點。 后根遍歷序列：B E F C D AACBFDE 2、森林的遍歷先根遍歷 訪問森林中第一棵樹的根結(jié)點； 先序遍歷第一棵樹中的諸子樹； 先序遍歷其余的諸樹。ACBDFEGJHI森林的先根遍歷序列：A B C D E F

16、 G H I J GJHIFEACBD二叉樹的先根序列：A B C D E F G H I J 后根遍歷森林： 后序遍歷第一棵樹的諸子樹； 訪問森林中第一棵樹的根結(jié)點； 后序遍歷其余的諸樹。 森林的后根遍歷序列： B C D A F E H J I GGJHIFEACBDACBDFEGJHI二叉樹的中根序列： B C D A F E H J I G遞歸算法先根遍歷以t為根的樹算法PreOrder( t )PreOrder1. 若t為空返回 IF t = THEN RETURN.PreOrder2. 訪問t所指結(jié)點 PRINT(Data ( t ) ).PreOrder3. 將指針 t 定位到它

17、所指結(jié)點的第一個子結(jié)點 GFC( t . child );PreOrder4. 先根遍歷t所指結(jié)點的諸子樹 WHILE child DO ( PreOrder (child). GNB(child . child). ) ACBFDE首先，將結(jié)點p設(shè)為根結(jié)點。(1)若結(jié)點p不為空，訪問結(jié)點p，將結(jié)點p壓入棧，并將其大兒子結(jié)點設(shè)為結(jié)點p；反復(fù)執(zhí)行(1)，直至結(jié)點p為空。(2)從棧中彈出一個結(jié)點，若它有大兄弟結(jié)點，則訪問該結(jié)點，并將其大兄弟結(jié)點壓入棧；否則，反復(fù)執(zhí)行(2)，直至彈出的結(jié)點有大兄弟結(jié)點或?？铡?3)反復(fù)執(zhí)行(1)(2)，直至棧為空。 迭代算法先根遍歷以t為根的樹算法NPO( t )N

18、PO1. 初始化堆棧S S AVAILNPO2. 保存根指針 p t .NPO3. 若p所指結(jié)點不為空，訪問p所指結(jié)點，將p壓入棧，并將其FistChild指針設(shè)為p. WHILE p DO (PRINT ( Data ( p ) ). Push (S , p ). p FistChild (p ). ) 迭代算法先根遍歷以t為根的樹NPO4. 從棧中彈出指針，直至彈出的指針?biāo)附Y(jié)點有大兄弟結(jié)點或?？找灾翢o結(jié)點可彈出。 WHILE p = AND S非空 DO ( Pop ( S . p ). p NextBrother ( p ). )NPO5. 重復(fù)上述過程 IF S非空 THEN GOT

19、O NPO3. 樹和森林的層次遍歷例 ACBDFEGJHI森林的層次遍歷序列： A E G B C D F H I J樹和森林的層次遍歷 是沿NextBrother鏈訪問的過程，指針 FirstChild起承上啟下的作用，可以使用隊列輔助存儲。森林的層次遍歷序列： A E G B C D F H I JGJHIFEACBD算法LevelOrder（t）/ 指針t指向與森林自然對應(yīng)的二叉樹的根L1 創(chuàng)建一個輔助隊列CREATE(Q).L2 根結(jié)點入隊Q t . /根結(jié)點入隊列L3 利用隊列進行層次遍歷WHILE NOT(IsEmpty(Q) DO ( p Q . WHILE pNULL DO (

20、 PRINT(data(p). IF FirstChild(p)NULL THEN Q FirstChild(p). pNextBrother(p) . ) ) GJHIFEACBD4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應(yīng)用第四章 樹4.5.1文件編碼4.5.2擴充二叉樹4.5.3哈夫曼樹與哈夫曼編碼4.5 壓縮與哈夫曼樹 數(shù)據(jù)壓縮是計算機科學(xué)中的重要技術(shù)。數(shù)據(jù)壓縮過程稱為編碼，即將文件中的每個字符均轉(zhuǎn)換為一個唯一的二進制位串。 數(shù)據(jù)解壓過程稱為解碼，即將二進制位串轉(zhuǎn)換為對應(yīng)的字符。壓縮的關(guān)鍵在于編碼的方法，哈夫曼編碼是一種最常用無損壓縮編碼方

21、法。4.5.1 文件編碼 假設(shè)有一個文件僅包含7個字符：a、e、i、s、t、sp（空格）和nl（換行），且文件中有10個a，15個e，12個i，3個s，4個t，13個sp，1個nl。 因為log27 = 3，所以，每個字符都至少由一個3位的二進制串表示。于是文件的總位數(shù)至少應(yīng)該是： 103 + 153 + 123 + 33 + 43 + 133 + 13 = 174 . 在實際應(yīng)用的一些大文件中，字符被使用的比率是非平均的，即有些字符出現(xiàn)的次數(shù)多，而有些字符出現(xiàn)的次數(shù)卻非常少。如果所有字符都由等長的二進制碼表示，那么將造成空間浪費。 如何才能減少不必要的空間浪費呢？文件壓縮的通常策略是：采用不

22、等長的二進制碼，令文件中出現(xiàn)頻率高的字符的編碼盡可能短。但是，采用不等長編碼又可能會產(chǎn)生多義性。例如：如果用01表示a，10表示b，1001表示c，那么對于編碼1001，我們無法確定它表示字符c ，還是表示字符串ba ，其原因是b的編碼與c的編碼的開始（前綴）部分相同。為了避免出現(xiàn)多義性，就必須要求字符集中任何字符的編碼都不是其它字符的編碼的前綴，滿足這個條件的編碼被稱為前綴碼。顯然，等長編碼是前綴碼。怎樣的前綴碼才能使文件的總編碼長度最短？設(shè)組成文件的字符集A=a1,a2,an，其中，ai的編碼長度為li；ai出現(xiàn)的次數(shù)為ci 。要使文件的總編碼最短，就必須要確定li，使 取最小值.如何設(shè)計

23、出使上式最小的前綴碼？Huffman于1952年提出了哈夫曼算法。4.5.1文件編碼4.5.2擴充二叉樹4.5.3哈夫曼樹與哈夫曼編碼4.5 壓縮與哈夫曼樹4.5.2 擴充二叉樹定義4.9 為了使問題的處理更為方便，每當(dāng)原二叉樹中出現(xiàn)空子樹時，就增加特殊的結(jié)點空樹葉，由此生成的二叉樹稱為擴充二叉樹。 擴充二叉樹每一個圓形結(jié)點都有兩個兒子，每一個方形結(jié)點沒有兒子。 規(guī)定空二叉樹的擴充二叉樹只有一個方形結(jié)點。圓形結(jié)點稱為內(nèi)結(jié)點，方形結(jié)點稱為外結(jié)點。 (a) (b)二叉樹和它的擴充二叉樹定義4.10 擴充二叉樹的外通路長度定義為從根到每個外結(jié)點的路徑長度之和，內(nèi)通路長度定義為從根到每個內(nèi)結(jié)點的路徑長

24、度之和。外通路長度為 3 3 2 3 4 4 3 3=25內(nèi)通路長度為 2 1 0 2 3 12=11.定義4.11 給擴充二叉樹中n個外結(jié)點賦上一個實數(shù)，稱為該結(jié)點的權(quán)。樹的加權(quán)外通路長度定義為WPL： 其中，n表示外結(jié)點的個數(shù)，wi和Li分別表示外結(jié)點ki的權(quán)值和根到ki之間的路徑長度。 加權(quán)外通路長度分別是4*2+2*3+3*3+11*1=343*2+4*3+11*3+2*1=53和2*2+11*2+3*2+4*2=40定義4.12 在外結(jié)點權(quán)值分別為w0,w1,wn-1的擴充二叉樹中，加權(quán)外通路長度最小的擴充二叉樹稱為最優(yōu)二叉樹 。4.5.1文件編碼4.5.2擴充二叉樹4.5.3哈夫曼

25、樹與哈夫曼編碼4.5 壓縮與哈夫曼樹文件編碼問題就變成構(gòu)造最優(yōu)二叉樹問題，每個外結(jié)點代表一個字符，該字符的頻率作為其權(quán)值，從根到外結(jié)點的路徑長度就是該字符的編碼長度 .為求得最優(yōu)二叉樹，哈夫曼巧妙的設(shè)計了哈夫曼算法，通過哈夫曼算法可以建立一棵哈夫曼樹，從而為壓縮文本文件建立哈夫曼編碼。哈夫曼算法基本思想： 把每個結(jié)點都作為一棵二叉樹的根結(jié)點，這n個根結(jié)點就組成了一個森林。我們把結(jié)點在文件中出現(xiàn)的次數(shù)定義為該結(jié)點的權(quán)值。 (1) 在森林中取權(quán)值最小的兩個根結(jié)點s和nl，合并成一棵二叉樹，并生成一個新結(jié)點T1，作為這兩個結(jié)點的父結(jié)點，T1的權(quán)值是它的兩個子結(jié)點的權(quán)值之和。顯然，T1成為新的根結(jié)點，

26、而s和nl成為T1的子結(jié)點，同時，森林中減少了一棵樹。 (2) 對新森林重復(fù)上一步操作，直至森林中只有唯一的根結(jié)點時，終止操作。 由上述方法構(gòu)造出的二叉樹，被稱為“哈夫曼樹”。 例: F=7,5,2,4 2475116187524752647524116文件編碼假設(shè)有一個文件僅包含7個字符：a、e、i、s、t、sp(空格)和nl(換行)，且文件中有10個a，15個e，12個i，3個s，4個t，13個sp，1個nl。 定理4.3 在外結(jié)點權(quán)值分別為w0,w1,wn-1的擴充二叉樹中，由哈夫曼算法構(gòu)造出的哈夫曼樹的帶權(quán)路徑長度最小，因此哈夫曼樹為最優(yōu)二叉樹。由觀察可知，字符集中的字符所在的結(jié)點均是

27、哈夫曼樹中的外結(jié)點。哈夫曼樹中沒有度為1的結(jié)點。哈夫曼編碼：將哈夫曼樹每個分支結(jié)點的左分支標(biāo)上0，右分支標(biāo)上1，把從根結(jié)點到每個葉結(jié)點的路徑上的標(biāo)號連接起來，作為該葉結(jié)點所代表的字符的編碼，這樣得到的編碼稱為哈夫曼編碼。根據(jù)定理4.3知道，對于所有的編碼，哈夫曼編碼使文件的總編碼長度最短。實際上，哈夫曼算法的應(yīng)用很廣，這里只是以哈夫曼編碼為例來說明哈夫曼算法。哈夫曼編碼 哈夫曼編碼的主要用途是實現(xiàn)數(shù)據(jù)壓縮。 設(shè)給出一段報文： CAST CAST SAT AT A TASA 字符集合是 C, A, S, T 若給每個字符以等長編碼 A : 00 T : 10 C : 01 S : 11 0100

28、1110 01001110 110010 0010 00 10001100 則總編碼長度為 18 * 2 = 36.例 哈夫曼編碼報文：CAST CAST SAT AT A TASA字符集合是 C, A, S, T ，各個字符出現(xiàn)的頻度(次數(shù))是 W 2, 7, 4, 5 7542011100TACS編碼 A (0) T (10) C (110) S (111)61118總編碼長度：1*7+2*5+3*2+3*4=35在構(gòu)造哈夫曼樹的過程中，沒有一片樹葉是其他樹葉的祖先，所以每個葉結(jié)點對應(yīng)的編碼不可能是其他葉結(jié)點對應(yīng)的編碼的前綴，由此可知哈夫曼編碼是二進制的前綴碼。哈夫曼編碼是否唯一？哈夫曼樹

29、中每個結(jié)點的結(jié)構(gòu)為：其中，LLINK和RLINK為鏈接域，INFO為信息域，Weight為該結(jié)點的權(quán)值。LLINKINFOWeightRLINKHuffman算法假設(shè)給定m個實數(shù)（權(quán)值）所在結(jié)點的地址存于一維數(shù)組H1:m+1中，該數(shù)組按每個結(jié)點的Weight域已經(jīng)排序，即Weight(H1)Weight(Hm) Weight(Hm+1)=+算法Huffman(H, m)Huffman1. 初始化 FOR i1 TO m DO LLINK(Hi) RLINK(Hi) .Huffman2. 組合過程 FOR i1 TO m-1 DO ( t AVAIL. P1 Hi. P2 Hi+1. Weigh

30、t(t) Weight(P1 ) Weight(P2 ). LLINK(t) P1 . RLINK(t) P2 . p t ./*把新結(jié)點p插入到數(shù)組H中Hj位置*/j i 2 .WHILE Weight(p)Weight(Hj) DO ( Hj-1 Hj . j j 1. ) Hj-1 p. )編碼：依次將數(shù)據(jù)文件中的字符按哈夫曼樹轉(zhuǎn)換成哈夫曼編碼。解碼：依次讀入文件的二進制碼，從哈夫曼樹的根結(jié)點出發(fā)，若當(dāng)前讀入0，則走向其左孩子，否則走向其右孩子，到達某一葉結(jié)點時，便可以譯出相應(yīng)的字符。 4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應(yīng)用第四章 樹

31、4.6.1 表達式求值問題1、表達式樹的建立 表達式求值是程序設(shè)計語言編譯的一個基本問題。 表達式有一個內(nèi)在二叉樹結(jié)構(gòu)，表達式(ab)(cd)e對應(yīng)的二叉樹如下圖所示，二叉樹中葉結(jié)點是表達式中的變量或常數(shù)（如：a, b），非葉結(jié)點是操作符。eabcd對表達式樹做后根遍歷可以得到后綴表達式：ab+cd-*e- 由于中綴表達式存在運算符的優(yōu)先級，計算機處理中綴表達式比較復(fù)雜。一個中綴表達式中有多少個運算符，原則上就得對表達式掃描多少遍，才能完成計算。 在編譯系統(tǒng)中，常把中綴表達式轉(zhuǎn)換成后綴表達式，然后對后綴式表達式進行處理。 如果不考慮一元操作符負(fù)號，可以用后綴表達式構(gòu)造表達式對應(yīng)的二叉樹。二叉樹

32、的建立過程如下： 從左向右依次掃描后綴表達式中各個符號，1）如果當(dāng)前被掃描的符號是操作數(shù)，則生成一個新結(jié)點，以此操作數(shù)作為該結(jié)點的數(shù)據(jù)域，將此結(jié)點作為新二叉樹的根結(jié)點壓入堆棧中。2）如果當(dāng)前被掃描的符號為二元操作符，則生成一個新結(jié)點，并以此操作符作為該結(jié)點的數(shù)據(jù)域，從棧頂彈出兩個結(jié)點，創(chuàng)造一棵以新生成結(jié)點為根、以彈出的兩個結(jié)點為其右子結(jié)點和左子結(jié)點的新二叉樹，將新樹根壓入堆棧。 按照上述方法處理完表達式中所有符號后，堆棧中僅包含一個結(jié)點，即所求二叉樹的根結(jié)點。算法 CET(expr . t)/*算法CET利用輔助堆棧S構(gòu)造表達式expr對應(yīng)的二叉樹, 算法結(jié)束時指針t 指向二叉樹根結(jié)點；CET

33、是CreatExpressTree之縮寫*/CET1. 創(chuàng)建一個輔助堆棧 CREATE ( S ). Read ( op ). /讀入表達式序列中的一個符號CET2. 掃描表達式 WHILE op # DO ( IF op= OR op= OR op= OR op= THEN ( rpr S. lpr S. pAVAIL. Data(p)op. Left(p)lpr. Right(p)rpr. Sp . ) ELSE ( pAVAIL. Data(p)op. Left(p). Right(p). Sp . ) Read ( op ). /讀入表達式序列中的一個符號 )CET3 指針t 指向二叉

34、樹根結(jié)點 t S. 練習(xí)：構(gòu)造后綴表達式 ab+cde+*-f-gh+* 對應(yīng)的二叉樹2、后綴表達式求值的方法： 若已知后綴表達式，從左到右讀入后綴表達式的各個符號， 若讀到的是操作數(shù)，將它壓入堆棧。 若讀到的是運算符，就從棧中連續(xù)彈出兩個元素，進行相應(yīng)的運算，并將結(jié)果壓入棧。 讀入結(jié)束符時，棧頂元素就是計算結(jié)果。 操作 后綴表達式 棧T2 =A/T1 T2 DE*+AC*- =; T2 DET3 =D*E T2T3 +AC*- =; T2 T3 T4=T2+T3 T4AC*- =; T4ACT5 =A*C T4 T5 - =; T4 T5 T6 =T4- T5 =; T6T1=B*C AT1/DE*+AC*- =; AT1 ABC*/DE*+AC*- =; ABC例 計算后綴表達式ABC*/DE*+AC*- 在表達式樹的基礎(chǔ)上，通過后根遍歷，可以計算表達式的值：當(dāng)訪問一個葉結(jié)點時，把對應(yīng)的值壓入堆棧中；當(dāng)訪問一個非葉結(jié)點時，從堆棧中連續(xù)彈出兩個值，按此結(jié)點規(guī)定的操作進行運算，并且結(jié)果壓回到堆棧中；當(dāng)遍歷終止時，堆棧中只有一個值，它就是表達式的值。 算法 GetValue( t . value)/*t為表達式對應(yīng)二叉樹根指針,value為求得的表達式值。利用輔助堆棧S和calculator求