第16章樹(shù)離散數(shù)學(xué)

1、第16章 樹(shù)離 散 數(shù) 學(xué)本章說(shuō)明樹(shù)是圖論中重要內(nèi)容之一。本章所談回路均指初級(jí)回路（圈）或簡(jiǎn)單回路，不含復(fù)雜回路（有重復(fù)邊出現(xiàn)的回路）。16.1 無(wú)向樹(shù)及其性質(zhì)16.2 生成樹(shù)16.3 根樹(shù)及其應(yīng)用（不講） 本章小結(jié) 習(xí) 題 作 業(yè)本章說(shuō)明16.1 無(wú)向樹(shù)及其性質(zhì)無(wú)向樹(shù)連通無(wú)回路的無(wú)向圖，簡(jiǎn)稱樹(shù)，用T表示。平凡樹(shù)平凡圖。森林若無(wú)向圖G至少有兩個(gè)連通分支（每個(gè)都是樹(shù)）。樹(shù)葉無(wú)向圖中懸掛頂點(diǎn)。分支點(diǎn)度數(shù)大于或等于2的頂點(diǎn)。舉例如圖為九個(gè)頂點(diǎn)的樹(shù)。 設(shè)G是n階m條邊的無(wú)向圖，則下面各命題是等價(jià)的：（1）G是樹(shù)。（2）G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑。（3）G中無(wú)回路且mn1。（4）G是連通的且mn

2、1。（5）G是連通的且G中任何邊均為橋。（6）G中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈。無(wú)向樹(shù)的等價(jià)定義(1)(2)如果G是樹(shù)，則G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑。存在性。 由G的連通性及定理14.5的推論（在n階圖G中，若從頂點(diǎn)vi到vj(vivj)存在通路，則vi到vj 一定存在長(zhǎng)度小于等于n-1的初級(jí)通路(路徑)）可知，u,vV，u與v之間存在路徑。唯一性（反證法）。 若路徑不是唯一的，設(shè)1與2都是u到v的路徑，易知必存在由1和2上的邊構(gòu)成的回路，這與G中無(wú)回路矛盾。(2)(3)如果G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑，則G中無(wú)回路且mn-1

3、。首先證明 G中無(wú)回路。若G中存在關(guān)聯(lián)某頂點(diǎn)v的環(huán)，則v到v存在長(zhǎng)為0和1的兩條路經(jīng)(注意初級(jí)回路是路徑的特殊情況)，這與已知矛盾。若G中存在長(zhǎng)度大于或等于2的圈，則圈上任何兩個(gè)頂點(diǎn)之間都存在兩條不同的路徑，這也與已知矛盾。(2)(3)如果G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑，則G中無(wú)回路且mn-1。其次證明 mn-1。（歸納法）n1時(shí)，G為平凡圖，結(jié)論顯然成立。設(shè)nk(k1)時(shí)結(jié)論成立，當(dāng)n=k+1時(shí)，設(shè)e(u,v)為G中的一條邊，由于G中無(wú)回路，所以G-e為兩個(gè)連通分支G1、G2。設(shè)ni、mi分別為Gi中的頂點(diǎn)數(shù)和邊數(shù)，則nik ，i1,2，由歸納假設(shè)可知mini-1，于是mm1+m2+1n

4、1-1+n2-1+1n1+n2-1n-1。只需證明G是連通的。（采用反證法）假設(shè)G是不連通的，由s(s2)個(gè)連通分支G1,G2,Gs組成，并且Gi中均無(wú)回路，因而Gi全為樹(shù)。由(1)(2)(3)可知，mini-1。于是，由于s2，與mn-1矛盾。(3)(4)如果G中無(wú)回路且mn-1，則G是連通的且mn -1。如果G是連通的且mn1，則G是連通的且G中任何邊均為橋。只需證明G中每條邊均為橋。 eE，均有|E(G-e)|n-1-1n-2，由習(xí)題十四題49（若G是n階m條邊的無(wú)向連通圖，則mn-1）可知，G-e已不是連通圖，所以，e為橋。 (4)(5)如果G是連通的且G中任何邊均為橋，則G中沒(méi)有回路

5、，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈。因?yàn)镚中每條邊均為橋，刪掉任何邊，將使G變成不連通圖，所以，G中沒(méi)有回路，也即G中無(wú)圈。又由于G連通，所以G為樹(shù)，由(1) (2)可知，u,vV，且uv，則u與v之間存在唯一的路徑，則(u,v)（(u,v)為加的新邊）為G中的圈，顯然圈是唯一的。(5)(6)如果G中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈，則G是樹(shù)。只需證明G是連通的。u,vV，且uv，則新邊(u,v)G產(chǎn)生唯一的圈C，顯然有C -(u,v)為G中u到v的通路，故uv，由u,v的任意性可知，G是連通的。(6)(

6、1) 設(shè)T是n階非平凡的無(wú)向樹(shù)，則T中至少有兩片樹(shù)葉。設(shè)T有x片樹(shù)葉，由握手定理及定理16.1可知，證明由上式解出x2。無(wú)向樹(shù)的性質(zhì)例 畫(huà)出6階所有非同構(gòu)的無(wú)向樹(shù)。 解答 設(shè)Ti是6階無(wú)向樹(shù)。由定理16.1可知，Ti的邊數(shù)mi5，由握手定理可知，dTi(vj)10，且(Ti)1，(Ti)5。于是Ti的度數(shù)列必為以下情況之一。(1) 1，1，1，1，1，5(2) 1，1，1，1，2，4(3) 1，1，1，1，3，3(4) 1，1，1，2，2，3(5) 1，1，2，2，2，2(4)對(duì)應(yīng)兩棵非同構(gòu)的樹(shù)，在一棵樹(shù)中兩個(gè)2度頂點(diǎn)相鄰，在另一棵樹(shù)中不相鄰，其他情況均能畫(huà)出一棵非同構(gòu)的樹(shù)。例人們常稱只有一個(gè)

7、分支點(diǎn)，且分支點(diǎn)的度數(shù)為n-1的n(n3)階無(wú)向樹(shù)為星形圖，稱唯一的分支點(diǎn)為星心。 例 7階無(wú)向圖有3片樹(shù)葉和1個(gè)3度頂點(diǎn)，其余3個(gè)頂點(diǎn)的度數(shù)均無(wú)1和3。試畫(huà)出滿足要求的所有非同構(gòu)的無(wú)向樹(shù)。解答 設(shè)Ti為滿足要求的無(wú)向樹(shù)，則邊數(shù)mi6，于是d(vj)12e+3+d(v4)+d(v5)+d(v6)。由于d(vj)1d(vj)3，而且d(vj)1且d(vj)6，j4,5,6，可知d(vj)2，j4,5,6。于是Ti 的度數(shù)列為1，1，1，2，2，2，3由度數(shù)列可知，Ti中有一個(gè)3度頂點(diǎn)vi，vi的鄰域N(vi)中有3個(gè)頂點(diǎn)，這3個(gè)頂點(diǎn)的度數(shù)列只能為以下三種情況之一：1,1,21,2,22,2,2設(shè)

8、它們對(duì)應(yīng)的樹(shù)分別為T(mén)1，T2，T3。此度數(shù)列只能產(chǎn)生這三棵非同構(gòu)的7階無(wú)向樹(shù)。例例題例題 已知無(wú)向樹(shù)T中，有1個(gè)3度頂點(diǎn)，2個(gè)2度頂點(diǎn)，其余頂點(diǎn)全是樹(shù)葉，試求樹(shù)葉數(shù)，并畫(huà)出滿足要求的非同構(gòu)的無(wú)向樹(shù)。 解答 設(shè)有x片樹(shù)葉，于是結(jié)點(diǎn)總數(shù)為n1+2+x3+x 由握手定理和樹(shù)的性質(zhì)mn1可知，2m2(n1)2(2+x) 13+22+x解出x3，故T有3片樹(shù)葉。故T的度數(shù)應(yīng)為1、1、1、2、2、3。例題 已知無(wú)向樹(shù)T有5片樹(shù)葉，2度與3度頂點(diǎn)各1個(gè)，其余頂點(diǎn)的度數(shù)均為4，求T的階數(shù)n，并畫(huà)出滿足要求的所有非同構(gòu)的無(wú)向樹(shù)。解答設(shè)T的階數(shù)為n, 則邊數(shù)為n1，4度頂點(diǎn)的個(gè)數(shù)為n7。由握手定理得 2m = 2

9、(n1) = 51+21+31+4(n7)解出n = 8，所以4度頂點(diǎn)為1個(gè)。故T的度數(shù)列為1、1、1、1、1、2、3、4。例題小節(jié)結(jié)束例題16.2 生成樹(shù) 設(shè)G為無(wú)向圖，（1）T為G的樹(shù)T是G的子圖并且是樹(shù)。（2）T為G的生成樹(shù)T是G的生成子圖并且是樹(shù)。（3）e為T(mén)的樹(shù)枝設(shè)T是G的生成樹(shù)，eE(G)，若eE(T)。（4）e為T(mén)的弦設(shè)T是G的生成樹(shù)，eE(G)，若eE(T)。（5）生成樹(shù)T的余樹(shù)導(dǎo)出子圖GE(G)-E(T) 。記作注意： 不一定連通，也不一定不含回路。說(shuō)明 無(wú)向圖G具有生成樹(shù)當(dāng)且僅當(dāng)G連通。證明必要性，顯然。充分性（破圈法）。 若G中無(wú)回路，G為自己的生成樹(shù)。 若G中含圈，任取

10、一圈，隨意地刪除圈上的一條邊，若再有圈再刪除圈上的一條邊，直到最后無(wú)圈為止。易知所得圖無(wú)圈(當(dāng)然無(wú)回路)、連通且為G的生成子圖，所以為G的生成樹(shù)。生成樹(shù)的存在條件 推論1G為n階m條邊的無(wú)向連通圖，則mn1。證明 由定理16.3可知，G有生成樹(shù)，設(shè)T為G的一棵生成樹(shù)，則m|E(G)|E(T)|n-1。推論2 設(shè)G是n階m條邊的無(wú)向連通圖，T為G的生成樹(shù)，則T的余樹(shù)中含有m-n+1條邊（即T有m-n+1條弦）。推論3 設(shè)T是連通圖G的一棵生成樹(shù)，T為T(mén)的余樹(shù)，C為G中任意一個(gè)圈，則E(T)E(C)。證明若E(T)E(C)，則E(C)E(T)，這說(shuō)明C為T(mén)中圈，與T為樹(shù)矛盾。 所以推論正確。推論

11、設(shè)T為無(wú)向連通圖G中一棵生成樹(shù)，e為T(mén)的任意一條弦，則Te中含G中只含一條弦其余邊均為樹(shù)枝的圈，而且不同的弦對(duì)應(yīng)的圈也不同。證明Te中含G中只含一條弦其余邊均為樹(shù)枝的圈。設(shè)e(u,v)，由定理16.1可知，在T中，u, v之間存在惟一的路徑 (u,v)，則 (u,v)e為所要求的圈。不同的弦對(duì)應(yīng)的圈也不同是顯然的。定理16.4 設(shè)T是n階m條邊的無(wú)向連通圖G的一棵生成樹(shù)，設(shè)e1, e2, , emn+1為T(mén)的弦。設(shè)Cr為T(mén)添加弦er產(chǎn)生的G中只含弦er，其余邊均為樹(shù)枝的圈，稱Cr為G的對(duì)應(yīng)T的弦er的基本回路或基本圈，r1, 2, , mn+1。稱C1, C2, , Cmn+1為G對(duì)應(yīng)T的基本

12、回路系統(tǒng)，稱mn+1為G的圈秩，記作(G)。求基本回路的算法設(shè)弦e=(u,v)，先求T中u到v的路徑(u,v)，再并上弦e，即得對(duì)應(yīng)e的基本回路?；净芈放c基本回路系統(tǒng)的定義對(duì)應(yīng)生成樹(shù)的弦分別為e6,e7,e8,e10,e11。設(shè)它們對(duì)應(yīng)的基本回路分別為C1,C2,C3,C4,C5，從對(duì)應(yīng)的弦開(kāi)始，按逆時(shí)針（也可都按順時(shí)針）的順序?qū)懗鏊鼈?，分別為此圖的圈秩為5，基本回路系統(tǒng)為C1,C2,C3,C4,C5。無(wú)向連通圖G的圈秩與生成樹(shù)的選取無(wú)關(guān)，但不同生成樹(shù)對(duì)應(yīng)的基本回路系統(tǒng)可能不同。 說(shuō)明求下圖中的基本回路系統(tǒng)。舉例C1e6e4e5C2e7e2e1C3e8e9e2e1C4e10e3e5e2C5e

13、11e3e5e2e9 設(shè)T是連通圖G的一棵生成樹(shù)，e為T(mén)的樹(shù)枝，則G中存在只含樹(shù)枝e，其余邊都是弦的割集，且不同的樹(shù)枝對(duì)應(yīng)的割集也不同。證明 由定理16.1可知，e是T的橋，因而Te有兩個(gè)連通分支T1和T2，令See|eE(G)且e的兩個(gè)端點(diǎn)分別屬于V(T1)和V(T2)，由構(gòu)造顯然可知，Se為G的割集，eSe且Se中除e外都是弦。不同的樹(shù)枝對(duì)應(yīng)的割集也不同是顯然的?；靖罴c基本割集系統(tǒng)的定義 設(shè)T是n階連通圖G的一棵生成樹(shù)，e1,e2,en1為T(mén)的樹(shù)枝，Si是G的只含樹(shù)枝ei的割集，則稱Si為G的對(duì)應(yīng)于生成樹(shù)T由樹(shù)枝ei生成的基本割集，i1,2,n1。稱S1,S2,Sn1為G對(duì)應(yīng)T的基本割

14、集系統(tǒng)，稱n1為G的割集秩，記作(G)。求基本割集的算法設(shè)e為生成樹(shù)T的樹(shù)枝，Te為兩棵小樹(shù)T1與T2，令Se e|eE(G)且e的兩個(gè)端點(diǎn)分別屬于T1與T2，則Se為e對(duì)應(yīng)的基本割集。樹(shù)枝為e1,e2,e3,e4,e5,e9。設(shè)它們對(duì)應(yīng)的基本割集分別為S1,S2,S3,S4,S5,S6。此圖的割集秩為6，基本割集系統(tǒng)為S1,S2,S3,S4,S5,S6。S1e1,e7,e8 無(wú)向連通圖G的割集秩與生成樹(shù)的選取無(wú)關(guān)，但不同生成樹(shù)對(duì)應(yīng)的基本割集系統(tǒng)可能不同。 說(shuō)明求下圖中的基本割集系統(tǒng)。舉例S2e2,e7,e8,e10,e11 S3e3,e10,e11 S4e4,e6 S5e5,e6,e10,e

15、11 S6e9,e8,e11 最小生成樹(shù) 設(shè)T是無(wú)向連通帶權(quán)圖G的一棵生成樹(shù)，T的各邊權(quán)之和稱為T(mén)的權(quán)，記作W(T)。G的所有生成樹(shù)中權(quán)最小的生成樹(shù)稱為G的最小生成樹(shù)。求最小生成樹(shù)的算法（避圈法(Kruskal)）(1)設(shè)n階無(wú)向連通帶權(quán)圖G有m條邊。不妨設(shè)G中沒(méi)有環(huán)（否則，可以將所有的環(huán)先刪去），將m條邊按權(quán)從小到大排序：e1,e2,em。(2)取e1在T中。(3)依次檢查e2,em ，若ej(j2)與已在T中的邊不構(gòu)成回路，取ej也在T中，否則棄去ej。(4)算法停止時(shí)得到的T為G的最小生成樹(shù)為止。例 求下圖所示兩個(gè)圖中的最小生成樹(shù)。 W(T1)6 W(T2)12 例題例如 求所示圖的一棵

16、最小生成樹(shù)。解答最小生成樹(shù) W(T)=38小節(jié)結(jié)束16.3 根樹(shù)及其應(yīng)用設(shè)D是有向圖，若D的基圖是無(wú)向樹(shù)，則稱D為有向樹(shù)。在所有的有向樹(shù)中，根樹(shù)最重要，所以我們只討論根樹(shù)。二叉樹(shù)的應(yīng)用 根樹(shù)的定義 T是n(n2)階有向樹(shù)，(1) T為根樹(shù) T中有一個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)的入度均為1(2) 樹(shù)根入度為0的頂點(diǎn)(3) 樹(shù)葉入度為1，出度為0的頂點(diǎn)(4) 內(nèi)點(diǎn)入度為1，出度不為0的頂點(diǎn)(5) 分支點(diǎn)樹(shù)根與內(nèi)點(diǎn)的總稱(6) 頂點(diǎn)v的層數(shù)從樹(shù)根到v的通路長(zhǎng)度(7) 樹(shù)高T中層數(shù)最大頂點(diǎn)的層數(shù)(8) 根樹(shù)平凡樹(shù)根樹(shù)的畫(huà)法樹(shù)根放上方，省去所有有向邊上的箭頭。樹(shù)葉8片內(nèi)點(diǎn) 6個(gè)分支點(diǎn) 7個(gè)高度 5家族樹(shù)常將

17、根樹(shù)看成家族樹(shù)，家族中成員之間的關(guān)系如下定義。 定義16.7 設(shè)T為一棵非平凡的根樹(shù)，vi、vjV(T)，若vi可達(dá)vj，則稱vi為vj的祖先，vj為vi的后代。若vi鄰接到vj（即E(T)），則稱vi為vj的父親，而vj為vi的兒子。若vj、vk的父親相同，則稱vj與vk是兄弟。 設(shè)v為根樹(shù)T中任意一頂點(diǎn)，稱v及其后代的導(dǎo)出子圖為以v為根的根子樹(shù)。根樹(shù)的分類(lèi)(1)設(shè)T為根樹(shù)，若將T中層數(shù)相同的頂點(diǎn)都標(biāo)定次序，則稱T為有序樹(shù)。 (2)分類(lèi)：根據(jù)根樹(shù)T中每個(gè)分支點(diǎn)兒子數(shù)以及是否有序r叉樹(shù)每個(gè)分支點(diǎn)至多有r個(gè)兒子r叉有序樹(shù)r叉樹(shù)是有序的r叉正則樹(shù)每個(gè)分支點(diǎn)恰有r個(gè)兒子r叉正則有序樹(shù)r叉正則樹(shù)是有序

18、的r叉完全正則樹(shù)樹(shù)葉層數(shù)均為樹(shù)高的r叉正則樹(shù)r叉完全正則有序樹(shù)r叉完全正則樹(shù)是有序的最優(yōu)二叉樹(shù)定義16.9 設(shè)2叉樹(shù)T有t片樹(shù)葉v1, v2, , vt，權(quán)分別為w1, w2, , wt，稱 為T(mén)的權(quán)，其中l(wèi)(vi)是vi的層數(shù)，在所有有t片樹(shù)葉、帶權(quán)w1, w2, , wt的2叉樹(shù)中，權(quán)最小的2叉樹(shù)稱為最優(yōu)2叉樹(shù)。舉例下圖所示的三棵2叉樹(shù)T1,T2,T3都是帶權(quán)為2、2、3、3、5的2叉樹(shù)。 W(T1)=22+22+33+53+32=38W(T2)=34+54+33+22+21=47W(T3)=33+33+52+22+22=36 求最優(yōu)樹(shù)的算法(Huffman算法)給定實(shí)數(shù)w1, w2, ,

19、 wt，且w1w2 wt。連接權(quán)為w1, w2的兩片樹(shù)葉，得一個(gè)分支點(diǎn)，其權(quán)為w1+w2。 在w1+w2, w3, , wt中選出兩個(gè)最小的權(quán)，連接它們對(duì)應(yīng)的頂點(diǎn)（不一定是樹(shù)葉），得新分支點(diǎn)及所帶的權(quán)。 重復(fù) ，直到形成t1個(gè)分支點(diǎn)、t片樹(shù)葉為止。算法舉例例如：求帶權(quán)為1、1、2、3、4、5的最優(yōu)樹(shù)。解答W(T)=38 (1)最佳前最碼的定義 設(shè)1, 2, , n-1, n是長(zhǎng)度為n的符號(hào)串，稱其子串1, 12, , 12n1 分別為該字符串的長(zhǎng)度為1,2, ,n的前綴。 設(shè)A=1, 2, , m為一個(gè)符號(hào)串集合，若對(duì)于任意的i, jA，ij，i, j互不為前綴，則稱A為前綴碼。若i(i=1,

20、2,m)中只出現(xiàn)0與1兩個(gè)符號(hào)，則稱A為二元前綴碼。(2)如何產(chǎn)生二元前綴碼？ 由一棵給定的2叉正則樹(shù)，可以產(chǎn)生唯一的一個(gè)二元前綴碼。 最佳前綴碼方法：將每個(gè)分支點(diǎn)引出的兩條邊分別標(biāo)上0和1。結(jié)果： 圖所示樹(shù)產(chǎn)生的前綴碼為00, 10, 11, 011, 0100, 0101。 用Huffman算法產(chǎn)生最佳前綴碼 在通信中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6： 5% 7： 5%求傳輸它們的最佳前綴碼？求傳輸10n（n2）個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字？若用等長(zhǎng)的（長(zhǎng)為3）的碼字傳輸需要多少個(gè)二進(jìn)制數(shù)字？解答

21、以100乘各頻率為權(quán)，并按小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25。產(chǎn)生的最優(yōu)樹(shù)如下。 0 01 1 11 2 001 3 1004 1015 00016 000007 00001傳100個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字個(gè)數(shù)W(T)=285 ，所以傳10n(n2)10n。用等長(zhǎng)碼（長(zhǎng)為3）應(yīng)該用310n個(gè)數(shù)字。由于在每一步選擇兩個(gè)最小的權(quán)的選法不唯一。因?yàn)閮蓚€(gè)權(quán)對(duì)應(yīng)的頂點(diǎn)所放左右位置不同。畫(huà)出的最優(yōu)樹(shù)可能不同，最佳前綴碼并不唯一，但有一點(diǎn)是共同的，就是它們的權(quán)應(yīng)該相等，即它們都應(yīng)該是最優(yōu)樹(shù)。說(shuō)明3、 波蘭符號(hào)法

22、與逆波蘭符號(hào)法對(duì)一棵根樹(shù)的每個(gè)頂點(diǎn)都訪問(wèn)且僅訪問(wèn)一次稱為行遍或周游一棵樹(shù)。對(duì)2叉有序正則樹(shù)的周游方式： 中序行遍法次序?yàn)椋鹤笞訕?shù)、樹(shù)根、右子樹(shù) 前序行遍法次序?yàn)椋簶?shù)根、左子樹(shù)、右子樹(shù) 后序行遍法次序?yàn)椋鹤笞訕?shù)、右子樹(shù)、樹(shù)根 中序行遍法：b a (f d g) c e前序行遍法：a b (c (d f g) e) 后序行遍法：b (f g d) e c) a 例如：用2叉有序正則樹(shù)存放算式： 最高層次的運(yùn)算符放在樹(shù)根上。 依次將運(yùn)算符放在根子樹(shù)的根上。 參加運(yùn)算的數(shù)放在樹(shù)葉上，規(guī)定：被除數(shù)、被減數(shù)放在左子樹(shù)樹(shù)葉上。 例如：用二叉有序正則樹(shù)表示算式 (b+(c+d)a)(ef)(g+h)(ij) 解答波蘭符號(hào)法 按前序行遍法訪問(wèn)存放算式的2叉有序正則樹(shù)，其結(jié)果不加括號(hào)，規(guī)定每個(gè)運(yùn)算符號(hào)與其后面緊鄰兩個(gè)數(shù)進(jìn)行運(yùn)算，運(yùn)算結(jié)果正確。稱此算法為波蘭符號(hào)法或前綴符號(hào)法。上圖前序行遍法的訪問(wèn)結(jié)果為 b + c d a e f + g h i j 逆波蘭符號(hào)法 按后序行遍法訪問(wèn)，規(guī)定每個(gè)運(yùn)算符與前面緊鄰兩數(shù)運(yùn)算，稱為逆波蘭符號(hào)法或后綴符號(hào)法。 上圖后序行遍法的訪問(wèn)結(jié)果為b c d +