??? 下面分析本文中的算法步驟。
2.1.1 改造二叉樹并構造單鏈表
??? 首先可以將二叉樹改造成一個對應的有向圖。方法是將二叉樹的每條無向邊改成一條向下和另一條向上的有向邊，結點不變。如圖1的二叉樹可以改造成如圖2的有向圖。
??? 根據(jù)改造后的有向圖構造單鏈表的過程就是在該有向圖中尋找后繼邊的過程，按照后序遍歷的思想，所有的處理器同時處理分配給它的一條邊的后繼邊的問題，最終得到由全部有向邊構成的一個單鏈表。單鏈表的每個元素對應于改造后的有向圖中的一條有向邊。
??? 設分配給處理器P[(i，j)]處理的有向邊是(i，j)，即該邊從結點i指向j，則尋找有向邊(i，j)后繼邊的問題可以根據(jù)有向邊(i，j)的不同類型分別處理。
??? (1)PARENT(i)=j，說明邊(i，j)是一條向上邊，即從一個結點指向它的雙親結點。從數(shù)據(jù)結構的概念中可以得到以下結論，一條向上的邊(i，j)在二叉樹中的相對位置可以有三種情況：①結點j有右孩子結點，如圖3(a)所示。則根據(jù)后序遍歷的思想可得邊(i，j)的后繼邊是從結點j指向結點j的右孩子結點構成的邊；②結點i沒有右兄弟結點，而結點j有雙親結點，如圖3(b)所示。若根據(jù)后序遍歷的思想可得邊(i，j)的后繼邊是從結點j指向結點j的雙親結點(parent)構成的邊；③結點i既沒有兄弟結點，同時也沒有雙親結點，如圖3(c)所示，說明已經(jīng)回到了根結點處，邊(i，j)沒有后繼邊。但為了方便起見，假設存在一條后繼邊，從結點j到它自身。

?

??? (2)PARENT(i)≠j，也就是邊(i，j)是從雙親結點到它的孩子的向下的邊。
??? 同理，從數(shù)據(jù)結構的概念中可以得出這樣的結論，即一條向下的邊(i，j)在二叉樹中的位置可以有如下情況：①結點j有左孩子結點(不管有無右孩子結點)，如圖4(a)所示。根據(jù)后序遍歷的思想可知，邊(i，j)的后繼邊是從結點j指向結點j的左孩子結點構成的邊。②結點j沒有左孩子，但有右孩子，如圖4(b)所示。根據(jù)后序遍歷的思想可得，邊(i，j)的后繼邊是從結點j指向結點j的右孩子結點構成的邊。③結點j沒有孩子結點，即結點j是葉子結點，如圖4(c)所示。則根據(jù)后序遍歷的思想可得，邊(i，j)的后繼邊是結點j指向結點i的向上邊。

?

2.1.2 給單鏈表中的每個元素賦權值0或1
??? 此過程也是所有的處理器同時對分配給它的一個元素賦權值（前面構造的單鏈表中的元素）。根據(jù)后序遍歷的思想，對于二叉樹的一個結點i（根結點例外，必須作不同處理），如果一條向下遍歷的邊(i，j)從結點i出發(fā)，則說明正在尋找從該結點i出發(fā)的后繼邊，結點i沒有被訪問；如果一條向上遍歷的邊(i，j)從結點i出發(fā)，則說明剛訪問完結點i。將單鏈表中對應向上邊的元素賦權值1（表示遍歷向上邊時增加了一個被訪問結點），對應向下邊的元素賦權值0（表示遍歷向下邊時未增加被訪問結點），對應根結點的環(huán)形邊元素也賦權值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的位序，從而可以得到二叉樹中全部結點的位序。結點的位序是結點被訪問的先后順序的逆序。只要用結點個數(shù)N減去每個結點的位序就可以得到每個結點的后序遍歷順序號。與前幾步一樣，這里也是一個處理器計算一個結點的順序號，多個處理器并行工作，最后，得到一棵二叉樹的后序遍歷的結點順序。
2.2 算法示意代碼
??? 算法描述如下：
??? int n；????//二叉樹的結點個數(shù)
??? int parent[n]；???//父結點數(shù)組
??? int lchild[n]；???//左孩子結點數(shù)組
??? int rchild[n]；???//右孩子結點數(shù)組
??? int succ[(n，n)]；??//后繼邊數(shù)組
??? int position[(n，n)]；??//鏈表元素的位序數(shù)組
??? int postnode[n]；??//結點順序號數(shù)組
??? 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???? ??? {?position[(i，j)]=position[(i，j)]+position[succ[(i，j)]]；
???????? ??succ[(i，j)]=succ[succ[(i，j)]]；
???????? }//for
????????? if(parent[i]==j)???? //求結點的后序遍歷順序號
???????????postnode[i]=postion[(i，j)]；
???????? }//forall
??? }
3? 結束語
??? 以圖1所示的二叉樹為例，按照上述算法構造的單鏈表（帶權值）如圖5所示。表2為二叉樹單鏈表的位序。

?

?