??? 摘? 要： 本文運用網格環境下的并行計算模型G-PRAM來研究二叉樹的后序遍歷問題，提出了二叉樹后序遍歷的一種并行算法，并給出示例和說明。
??? 關鍵詞： 網格環境? 二叉樹? 后序遍歷? 并行算法
?
??? 二叉樹[1]是一種重要的數據結構，它是n(n≥0)個結點的有限集。它或者是空集（n=0），或者由一個根結點和兩棵互不相交的分別稱為這個根的左、右子樹的二叉樹組成。二叉樹的遍歷可以分為三種：一種是先序遍歷，即先訪問二叉樹的根結點，然后先序遍歷左子樹，最后先序遍歷右子樹；第二種是中序遍歷，即先中序遍歷左子樹，再訪問二叉樹的根結點，最后中序遍歷右子樹；第三種是后序遍歷，即先后序遍歷左子樹，再后序遍歷右子樹，最后訪問二叉樹的根結點。最常見的實現按照遍歷過程訪問結點，讓每個結點被訪問且僅被訪問一次，這種方式稱為串行算法。但是，可以換個角度來研究二叉樹的遍歷問題，即從串行算法中以二叉樹的結點為重點考察對象轉變為重點研究二叉樹的邊的遍歷問題[2][4]。當進行二叉樹的一次遍歷時實際也遍歷了二叉樹的所有邊，而且每條邊遍歷了兩次。一次是從雙親結點到子結點，另一次則是從子結點到雙親結點。如果將每條邊變成兩條有向邊，一條有向邊對應向下的遍歷，另一條有向邊對應向上的遍歷，則遍歷二叉樹的結點問題變成了一個遍歷二叉樹的邊的問題。
??? 因為網格環境具有一般的并行環境所不具有的強處理能力，所以可以給每條邊分配一個獨立的處理單元（單處理器的網格節點或者多處理器網格節點的一個處理器）進行處理，利用多個處理單元同時對所有的邊進行處理，從而并行實現網格環境下的二叉樹后序遍歷。
1? 網格環境下的G-PRAM模型
??? 由Fortune和Wyllie形式化的PRAM[5]模型是一個理想化的并行計算模型，被廣泛用來評估并行算法的理論性能。PRAM的思想是假設一個共享存儲多處理機系統是由一個具有無限存儲容量的共享存儲器以及可對它進行訪問的許多處理機所組成的系統。并行算法的設計者可以把處理器的能力看成是無限的。一個PRAM由一個控制單元、全局內存和一組處理器集合組成。每個處理器有其自己的私有內存，所有處理器執行相同的指令，但每個處理器處理的數據不同。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)。網格環境往往由相當多的網格結點組成，這些結點有的是多處理器的高性能計算結點，有的是高容量的數據結點，并且往往有一個性能不錯且容量也很大的控制結點。因此提出相應的G-PRAM模型。G-PRAM可以看作是一般PRAM的現實化。
??? 定義1 一個G-PRAM由網格環境下的一個控制結點、一個全局數據結點和一組計算結點集合組成。每個網格計算結點有其自己的私有內存，所有網格計算結點的各個處理器執行相同的指令，但每個處理器處理的數據不一樣。相應的G-PRAM也有4種方式：EREW G-PRAM、CREW G-PRAM、ERCW G-PRAM、CRCW G-PRAM。
2? 并行實現二叉樹的后序遍歷
2.1 算法過程說明
??? 這里的算法采用并行讀互斥寫（CREW G-PRAM），算法在實現中對每個二叉樹結點保存結點的雙親、左孩子和右孩子，利用這三個參數來描述一個二叉樹結點在二叉樹中的相對位置。
??? 對于如圖1所示的二叉樹，其數據結構描述如表1所示。
?
??????????? 
??? 
??? 下面分析本文中的算法步驟。
2.1.1 改造二叉樹并構造單鏈表
??? 首先可以將二叉樹改造成一個對應的有向圖。方法是將二叉樹的每條無向邊改成一條向下和另一條向上的有向邊，結點不變。如圖1的二叉樹可以改造成如圖2的有向圖。
??? 根據改造后的有向圖構造單鏈表的過程就是在該有向圖中尋找后繼邊的過程，按照后序遍歷的思想，所有的處理器同時處理分配給它的一條邊的后繼邊的問題，最終得到由全部有向邊構成的一個單鏈表。單鏈表的每個元素對應于改造后的有向圖中的一條有向邊。
??? 設分配給處理器P[(i，j)]處理的有向邊是(i，j)，即該邊從結點i指向j，則尋找有向邊(i，j)后繼邊的問題可以根據有向邊(i，j)的不同類型分別處理。
??? (1)PARENT(i)=j，說明邊(i，j)是一條向上邊，即從一個結點指向它的雙親結點。從數據結構的概念中可以得到以下結論，一條向上的邊(i，j)在二叉樹中的相對位置可以有三種情況：①結點j有右孩子結點，如圖3(a)所示。則根據后序遍歷的思想可得邊(i，j)的后繼邊是從結點j指向結點j的右孩子結點構成的邊；②結點i沒有右兄弟結點，而結點j有雙親結點，如圖3(b)所示。若根據后序遍歷的思想可得邊(i，j)的后繼邊是從結點j指向結點j的雙親結點(parent)構成的邊；③結點i既沒有兄弟結點，同時也沒有雙親結點，如圖3(c)所示，說明已經回到了根結點處，邊(i，j)沒有后繼邊。但為了方便起見，假設存在一條后繼邊，從結點j到它自身。
?
??? (2)PARENT(i)≠j，也就是邊(i，j)是從雙親結點到它的孩子的向下的邊。
??? 同理，從數據結構的概念中可以得出這樣的結論，即一條向下的邊(i，j)在二叉樹中的位置可以有如下情況：①結點j有左孩子結點(不管有無右孩子結點)，如圖4(a)所示。根據后序遍歷的思想可知，邊(i，j)的后繼邊是從結點j指向結點j的左孩子結點構成的邊。②結點j沒有左孩子，但有右孩子，如圖4(b)所示。根據后序遍歷的思想可得，邊(i，j)的后繼邊是從結點j指向結點j的右孩子結點構成的邊。③結點j沒有孩子結點，即結點j是葉子結點，如圖4(c)所示。則根據后序遍歷的思想可得，邊(i，j)的后繼邊是結點j指向結點i的向上邊。
?
2.1.2 給單鏈表中的每個元素賦權值0或1
??? 此過程也是所有的處理器同時對分配給它的一個元素賦權值（前面構造的單鏈表中的元素）。根據后序遍歷的思想，對于二叉樹的一個結點i（根結點例外，必須作不同處理），如果一條向下遍歷的邊(i，j)從結點i出發，則說明正在尋找從該結點i出發的后繼邊，結點i沒有被訪問；如果一條向上遍歷的邊(i，j)從結點i出發，則說明剛訪問完結點i。將單鏈表中對應向上邊的元素賦權值1（表示遍歷向上邊時增加了一個被訪問結點），對應向下邊的元素賦權值0（表示遍歷向下邊時未增加被訪問結點），對應根結點的環形邊元素也賦權值0（特殊處理）。
2.1.3 計算單鏈表中各元素的位序
??? 單鏈表中每個元素需要分配一個處理器去計算其位序。一棵有N個結點的二叉樹具有（N-1）條無向邊。由于我們將每條無向邊轉換成一條向上邊和一條向下邊，所以它共有2（N-1）條邊，這意味著單鏈表中有2（N-1）個元素。所以，需要2（N-1）個處理器來計算單鏈表中元素的位序。利用計算單鏈表位序的后綴和算法可以算出單鏈表中每個元素的位序[6]。
2.1.4 求權值為1的元素的相應結點的遍歷順序號
??? 由于權值為1（向上的邊）的元素所代表的邊都是向上的邊(不妨設該邊為(i，j))，即結點i在邊(i，j)遍歷時被訪問，而結點j還未被訪問。因此，用單鏈表中權值為1的元素的位序表示它所代表的邊(i，j)中結點i的位序，從而可以得到二叉樹中全部結點的位序。結點的位序是結點被訪問的先后順序的逆序。只要用結點個數N減去每個結點的位序就可以得到每個結點的后序遍歷順序號。與前幾步一樣，這里也是一個處理器計算一個結點的順序號，多個處理器并行工作，最后，得到一棵二叉樹的后序遍歷的結點順序。
2.2 算法示意代碼
??? 算法描述如下：
??? int n；????//二叉樹的結點個數
??? int parent[n]；???//父結點數組
??? int lchild[n]；???//左孩子結點數組
??? int rchild[n]；???//右孩子結點數組
??? int succ[(n，n)]；??//后繼邊數組
??? int position[(n，n)]；??//鏈表元素的位序數組
??? int postnode[n]；??//結點順序號數組
??? PostOrder(bitree *t)? //P[(i，j)]是處理對應邊(i，j)的一個處理器，共2(n-1)個
??? {
??? forall P[(i，j)] do??//構造單鏈表
??? {
??? ??? 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是根結點
?????????????????? }//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是根結點
??????????????????????}//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
???? ??? //給單鏈表中的每個元素賦權值
???????? 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)???? //求結點的后序遍歷順序號
???????????postnode[i]=postion[(i，j)]；
???????? }//forall
??? }
3? 結束語
??? 以圖1所示的二叉樹為例，按照上述算法構造的單鏈表（帶權值）如圖5所示。表2為二叉樹單鏈表的位序。
?
?
??? 從表2中選出權值為1的邊(D，B)、(B，A)、(E，C)、(G，F)、(F，C)、(C，A)，所以結點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個結點的二叉樹具有(N-1)條無向邊。由于要將每條無向邊轉換成一條向上邊和一條向下邊，所以它共有2(N-1)條有向邊。因此，該算法需要2(N-1)個網格處理單元（處理器），而網格計算技術的發展為并行算法的實現提供了環境的支持。在本算法中求單鏈表中元素的位序的計算時間復雜度為O(logN)，而算法的其余部分的計算時間是常數，所以算法的復雜度為O(logN)。
參考文獻
1?? 嚴蔚敏，吳偉民.數據結構(C語言版).北京：清華大學出版社，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模型的樹的后根遍歷并行算法.計算機工程與應用，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