??? 摘? 要： 本文運用網(wǎng)格環(huán)境下的并行計算模型G-PRAM來研究二叉樹的后序遍歷問題，提出了二叉樹后序遍歷的一種并行算法，并給出示例和說明。
??? 關(guān)鍵詞： 網(wǎng)格環(huán)境? 二叉樹? 后序遍歷? 并行算法
?
??? 二叉樹[1]是一種重要的數(shù)據(jù)結(jié)構(gòu)，它是n(n≥0)個結(jié)點的有限集。它或者是空集（n=0），或者由一個根結(jié)點和兩棵互不相交的分別稱為這個根的左、右子樹的二叉樹組成。二叉樹的遍歷可以分為三種：一種是先序遍歷，即先訪問二叉樹的根結(jié)點，然后先序遍歷左子樹，最后先序遍歷右子樹；第二種是中序遍歷，即先中序遍歷左子樹，再訪問二叉樹的根結(jié)點，最后中序遍歷右子樹；第三種是后序遍歷，即先后序遍歷左子樹，再后序遍歷右子樹，最后訪問二叉樹的根結(jié)點。最常見的實現(xiàn)按照遍歷過程訪問結(jié)點，讓每個結(jié)點被訪問且僅被訪問一次，這種方式稱為串行算法。但是，可以換個角度來研究二叉樹的遍歷問題，即從串行算法中以二叉樹的結(jié)點為重點考察對象轉(zhuǎn)變?yōu)橹攸c研究二叉樹的邊的遍歷問題[2][4]。當(dāng)進(jìn)行二叉樹的一次遍歷時實際也遍歷了二叉樹的所有邊，而且每條邊遍歷了兩次。一次是從雙親結(jié)點到子結(jié)點，另一次則是從子結(jié)點到雙親結(jié)點。如果將每條邊變成兩條有向邊，一條有向邊對應(yīng)向下的遍歷，另一條有向邊對應(yīng)向上的遍歷，則遍歷二叉樹的結(jié)點問題變成了一個遍歷二叉樹的邊的問題。
??? 因為網(wǎng)格環(huán)境具有一般的并行環(huán)境所不具有的強(qiáng)處理能力，所以可以給每條邊分配一個獨立的處理單元（單處理器的網(wǎng)格節(jié)點或者多處理器網(wǎng)格節(jié)點的一個處理器）進(jìn)行處理，利用多個處理單元同時對所有的邊進(jìn)行處理，從而并行實現(xiàn)網(wǎng)格環(huán)境下的二叉樹后序遍歷。
1? 網(wǎng)格環(huán)境下的G-PRAM模型
??? 由Fortune和Wyllie形式化的PRAM[5]模型是一個理想化的并行計算模型，被廣泛用來評估并行算法的理論性能。PRAM的思想是假設(shè)一個共享存儲多處理機(jī)系統(tǒng)是由一個具有無限存儲容量的共享存儲器以及可對它進(jìn)行訪問的許多處理機(jī)所組成的系統(tǒng)。并行算法的設(shè)計者可以把處理器的能力看成是無限的。一個PRAM由一個控制單元、全局內(nèi)存和一組處理器集合組成。每個處理器有其自己的私有內(nèi)存，所有處理器執(zhí)行相同的指令，但每個處理器處理的數(shù)據(jù)不同。PRAM模型有四種，不同之處主要在于它們處理讀寫沖突的方式有差異，包括：互斥讀互斥寫(Exclusive Read，Exclusive Write，EREW PRAM)，并行讀互斥寫(Concurrent Read，Exclusive Write，CREW PRAM），互斥讀并行寫(Exclusive Read，Concurrent Write，ERCW PRAM)，并行讀并行寫(Concurrent Read，Concurrent Write，CRCW PRAM)。網(wǎng)格環(huán)境往往由相當(dāng)多的網(wǎng)格結(jié)點組成，這些結(jié)點有的是多處理器的高性能計算結(jié)點，有的是高容量的數(shù)據(jù)結(jié)點，并且往往有一個性能不錯且容量也很大的控制結(jié)點。因此提出相應(yīng)的G-PRAM模型。G-PRAM可以看作是一般PRAM的現(xiàn)實化。
??? 定義1 一個G-PRAM由網(wǎng)格環(huán)境下的一個控制結(jié)點、一個全局?jǐn)?shù)據(jù)結(jié)點和一組計算結(jié)點集合組成。每個網(wǎng)格計算結(jié)點有其自己的私有內(nèi)存，所有網(wǎng)格計算結(jié)點的各個處理器執(zhí)行相同的指令，但每個處理器處理的數(shù)據(jù)不一樣。相應(yīng)的G-PRAM也有4種方式：EREW G-PRAM、CREW G-PRAM、ERCW G-PRAM、CRCW G-PRAM。
2? 并行實現(xiàn)二叉樹的后序遍歷
2.1 算法過程說明
??? 這里的算法采用并行讀互斥寫（CREW G-PRAM），算法在實現(xiàn)中對每個二叉樹結(jié)點保存結(jié)點的雙親、左孩子和右孩子，利用這三個參數(shù)來描述一個二叉樹結(jié)點在二叉樹中的相對位置。
??? 對于如圖1所示的二叉樹，其數(shù)據(jù)結(jié)構(gòu)描述如表1所示。
?
??????????? 
??? 
??? 下面分析本文中的算法步驟。
2.1.1 改造二叉樹并構(gòu)造單鏈表
??? 首先可以將二叉樹改造成一個對應(yīng)的有向圖。方法是將二叉樹的每條無向邊改成一條向下和另一條向上的有向邊，結(jié)點不變。如圖1的二叉樹可以改造成如圖2的有向圖。
??? 根據(jù)改造后的有向圖構(gòu)造單鏈表的過程就是在該有向圖中尋找后繼邊的過程，按照后序遍歷的思想，所有的處理器同時處理分配給它的一條邊的后繼邊的問題，最終得到由全部有向邊構(gòu)成的一個單鏈表。單鏈表的每個元素對應(yīng)于改造后的有向圖中的一條有向邊。
??? 設(shè)分配給處理器P[(i，j)]處理的有向邊是(i，j)，即該邊從結(jié)點i指向j，則尋找有向邊(i，j)后繼邊的問題可以根據(jù)有向邊(i，j)的不同類型分別處理。
??? (1)PARENT(i)=j，說明邊(i，j)是一條向上邊，即從一個結(jié)點指向它的雙親結(jié)點。從數(shù)據(jù)結(jié)構(gòu)的概念中可以得到以下結(jié)論，一條向上的邊(i，j)在二叉樹中的相對位置可以有三種情況：①結(jié)點j有右孩子結(jié)點，如圖3(a)所示。則根據(jù)后序遍歷的思想可得邊(i，j)的后繼邊是從結(jié)點j指向結(jié)點j的右孩子結(jié)點構(gòu)成的邊；②結(jié)點i沒有右兄弟結(jié)點，而結(jié)點j有雙親結(jié)點，如圖3(b)所示。若根據(jù)后序遍歷的思想可得邊(i，j)的后繼邊是從結(jié)點j指向結(jié)點j的雙親結(jié)點(parent)構(gòu)成的邊；③結(jié)點i既沒有兄弟結(jié)點，同時也沒有雙親結(jié)點，如圖3(c)所示，說明已經(jīng)回到了根結(jié)點處，邊(i，j)沒有后繼邊。但為了方便起見，假設(shè)存在一條后繼邊，從結(jié)點j到它自身。
?
??? (2)PARENT(i)≠j，也就是邊(i，j)是從雙親結(jié)點到它的孩子的向下的邊。
??? 同理，從數(shù)據(jù)結(jié)構(gòu)的概念中可以得出這樣的結(jié)論，即一條向下的邊(i，j)在二叉樹中的位置可以有如下情況：①結(jié)點j有左孩子結(jié)點(不管有無右孩子結(jié)點)，如圖4(a)所示。根據(jù)后序遍歷的思想可知，邊(i，j)的后繼邊是從結(jié)點j指向結(jié)點j的左孩子結(jié)點構(gòu)成的邊。②結(jié)點j沒有左孩子，但有右孩子，如圖4(b)所示。根據(jù)后序遍歷的思想可得，邊(i，j)的后繼邊是從結(jié)點j指向結(jié)點j的右孩子結(jié)點構(gòu)成的邊。③結(jié)點j沒有孩子結(jié)點，即結(jié)點j是葉子結(jié)點，如圖4(c)所示。則根據(jù)后序遍歷的思想可得，邊(i，j)的后繼邊是結(jié)點j指向結(jié)點i的向上邊。
?
2.1.2 給單鏈表中的每個元素賦權(quán)值0或1
??? 此過程也是所有的處理器同時對分配給它的一個元素賦權(quán)值（前面構(gòu)造的單鏈表中的元素）。根據(jù)后序遍歷的思想，對于二叉樹的一個結(jié)點i（根結(jié)點例外，必須作不同處理），如果一條向下遍歷的邊(i，j)從結(jié)點i出發(fā)，則說明正在尋找從該結(jié)點i出發(fā)的后繼邊，結(jié)點i沒有被訪問；如果一條向上遍歷的邊(i，j)從結(jié)點i出發(fā)，則說明剛訪問完結(jié)點i。將單鏈表中對應(yīng)向上邊的元素賦權(quán)值1（表示遍歷向上邊時增加了一個被訪問結(jié)點），對應(yīng)向下邊的元素賦權(quán)值0（表示遍歷向下邊時未增加被訪問結(jié)點），對應(yīng)根結(jié)點的環(huán)形邊元素也賦權(quán)值0（特殊處理）。
2.1.3 計算單鏈表中各元素的位序
??? 單鏈表中每個元素需要分配一個處理器去計算其位序。一棵有N個結(jié)點的二叉樹具有（N-1）條無向邊。由于我們將每條無向邊轉(zhuǎn)換成一條向上邊和一條向下邊，所以它共有2（N-1）條邊，這意味著單鏈表中有2（N-1）個元素。所以，需要2（N-1）個處理器來計算單鏈表中元素的位序。利用計算單鏈表位序的后綴和算法可以算出單鏈表中每個元素的位序[6]。
2.1.4 求權(quán)值為1的元素的相應(yīng)結(jié)點的遍歷順序號
??? 由于權(quán)值為1（向上的邊）的元素所代表的邊都是向上的邊(不妨設(shè)該邊為(i，j))，即結(jié)點i在邊(i，j)遍歷時被訪問，而結(jié)點j還未被訪問。因此，用單鏈表中權(quán)值為1的元素的位序表示它所代表的邊(i，j)中結(jié)點i的位序，從而可以得到二叉樹中全部結(jié)點的位序。結(jié)點的位序是結(jié)點被訪問的先后順序的逆序。只要用結(jié)點個數(shù)N減去每個結(jié)點的位序就可以得到每個結(jié)點的后序遍歷順序號。與前幾步一樣，這里也是一個處理器計算一個結(jié)點的順序號，多個處理器并行工作，最后，得到一棵二叉樹的后序遍歷的結(jié)點順序。
2.2 算法示意代碼
??? 算法描述如下：
??? int n；????//二叉樹的結(jié)點個數(shù)
??? int parent[n]；???//父結(jié)點數(shù)組
??? int lchild[n]；???//左孩子結(jié)點數(shù)組
??? int rchild[n]；???//右孩子結(jié)點數(shù)組
??? int succ[(n，n)]；??//后繼邊數(shù)組
??? int position[(n，n)]；??//鏈表元素的位序數(shù)組
??? int postnode[n]；??//結(jié)點順序號數(shù)組
??? PostOrder(bitree *t)? //P[(i，j)]是處理對應(yīng)邊(i，j)的一個處理器，共2(n-1)個
??? {
??? forall P[(i，j)] do??//構(gòu)造單鏈表
??? {
??? ??? if(lchild[j]==i)
??? ??? {?if(rchild[j]!=null)
??????????? ?????? succ[(i，j)]=(j，j.rchild)；
??????? ??else???? if(parent[j]!=null)
?????????????????????? ?????succ[(i，j)]=(j,，j.parent)；
??????????? ?????? else{
?????????????????????? ?????succ[(i，j)]=(j，j)；
????????????????????????????postnode[j]=0；//j是根結(jié)點
?????????????????? }//else
??????? ??}//if
??????? ??else???? if(rchild[j]==i)
?????????????????? {??if(j.parent!=null)
???????????????????? ??????succ[(i，j)]=(j，j.parent)；
???????????????? ?????else{
???????????????????? ??????succ[(i，j)]=(j，j)；
???????????????????? ??????postnode[j]=0；//j是根結(jié)點
??????????????????????}//else
?????????????????? }//if
??????? ??else???? if(parent[j]==i)
??????????? ?????? {??if(lchild[j]!=null)
???????????????????? ??????succ[(i，j)]=(j，j.lchild)；
??????????????????????else?if(rchild[j]!=null)
?????????????????????????????????succ[(i，j)]=(j，j.rchild)；
???????????????????? ??????else succ[(i，j)]=(j，i)；
??????????????????? }//if
???? ??? //給單鏈表中的每個元素賦權(quán)值
???????? if(parent[i]==j)
????????? ??position[(i，j)]=1；
???? ??? else
????????? ??position[(i，j)]=0；
???? ??? //計算單鏈表中元素的位序
???? ??? where 0≤k
???????? ??succ[(i，j)]=succ[succ[(i，j)]]；
???????? }//for
????????? if(parent[i]==j)???? //求結(jié)點的后序遍歷順序號
???????????postnode[i]=postion[(i，j)]；
???????? }//forall
??? }
3? 結(jié)束語
??? 以圖1所示的二叉樹為例，按照上述算法構(gòu)造的單鏈表（帶權(quán)值）如圖5所示。表2為二叉樹單鏈表的位序。
?
?
??? 從表2中選出權(quán)值為1的邊(D，B)、(B，A)、(E，C)、(G，F(xiàn))、(F，C)、(C，A)，所以結(jié)點D、B、E、G、F、C、A的位序就是6、5、4、3、2、1、0。即后序遍歷順序號是：1、2、3、4、5、6、7，可得出后序遍歷的順序是D、B、E、G、F、C、A。
??? 一棵有N個結(jié)點的二叉樹具有(N-1)條無向邊。由于要將每條無向邊轉(zhuǎn)換成一條向上邊和一條向下邊，所以它共有2(N-1)條有向邊。因此，該算法需要2(N-1)個網(wǎng)格處理單元（處理器），而網(wǎng)格計算技術(shù)的發(fā)展為并行算法的實現(xiàn)提供了環(huán)境的支持。在本算法中求單鏈表中元素的位序的計算時間復(fù)雜度為O(logN)，而算法的其余部分的計算時間是常數(shù)，所以算法的復(fù)雜度為O(logN)。
參考文獻(xiàn)
1?? 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版).北京：清華大學(xué)出版社，1997
2?? Tarjan R E，Vishkin U.An efficient parallel biconnectivity algorithm.SIAM Journal of Computer，1985；1(14)
3?? Foster I.The Grid：A New Infrastructure for 21st Century Science.Physics Today，2002；55(2)
4?? 熊家軍，岳大為，李肯立.基于SIMD-SM模型的樹的后根遍歷并行算法.計算機(jī)工程與應(yīng)用，2002；38(06)
5?? Wilkinson B，Allen M.Parallel programming: techniques and applications using networked workstation and parallel computers.Prentice Hall Inc，1999
6?? Karp R M，Ramachandran V.Parallel Algorithms for Shared-Memory Machines.Handbook of Theoretical Computer Science，vol A，MIT Press，1990