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

?

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

?

2.1.2 給單鏈表中的每個(gè)元素賦權(quán)值0或1
??? 此過(guò)程也是所有的處理器同時(shí)對(duì)分配給它的一個(gè)元素賦權(quán)值（前面構(gòu)造的單鏈表中的元素）。根據(jù)后序遍歷的思想，對(duì)于二叉樹的一個(gè)結(jié)點(diǎn)i（根結(jié)點(diǎn)例外，必須作不同處理），如果一條向下遍歷的邊(i，j)從結(jié)點(diǎn)i出發(fā)，則說(shuō)明正在尋找從該結(jié)點(diǎn)i出發(fā)的后繼邊，結(jié)點(diǎn)i沒有被訪問(wèn)；如果一條向上遍歷的邊(i，j)從結(jié)點(diǎn)i出發(fā)，則說(shuō)明剛訪問(wèn)完結(jié)點(diǎn)i。將單鏈表中對(duì)應(yīng)向上邊的元素賦權(quán)值1（表示遍歷向上邊時(shí)增加了一個(gè)被訪問(wèn)結(jié)點(diǎn)），對(duì)應(yīng)向下邊的元素賦權(quán)值0（表示遍歷向下邊時(shí)未增加被訪問(wèn)結(jié)點(diǎn)），對(duì)應(yīng)根結(jié)點(diǎn)的環(huán)形邊元素也賦權(quán)值0（特殊處理）。
2.1.3 計(jì)算單鏈表中各元素的位序
??? 單鏈表中每個(gè)元素需要分配一個(gè)處理器去計(jì)算其位序。一棵有N個(gè)結(jié)點(diǎn)的二叉樹具有（N-1）條無(wú)向邊。由于我們將每條無(wú)向邊轉(zhuǎn)換成一條向上邊和一條向下邊，所以它共有2（N-1）條邊，這意味著單鏈表中有2（N-1）個(gè)元素。所以，需要2（N-1）個(gè)處理器來(lái)計(jì)算單鏈表中元素的位序。利用計(jì)算單鏈表位序的后綴和算法可以算出單鏈表中每個(gè)元素的位序^[6]。
2.1.4 求權(quán)值為1的元素的相應(yīng)結(jié)點(diǎn)的遍歷順序號(hào)
??? 由于權(quán)值為1（向上的邊）的元素所代表的邊都是向上的邊(不妨設(shè)該邊為(i，j))，即結(jié)點(diǎn)i在邊(i，j)遍歷時(shí)被訪問(wèn)，而結(jié)點(diǎn)j還未被訪問(wèn)。因此，用單鏈表中權(quán)值為1的元素的位序表示它所代表的邊(i，j)中結(jié)點(diǎn)i的位序，從而可以得到二叉樹中全部結(jié)點(diǎn)的位序。結(jié)點(diǎn)的位序是結(jié)點(diǎn)被訪問(wèn)的先后順序的逆序。只要用結(jié)點(diǎn)個(gè)數(shù)N減去每個(gè)結(jié)點(diǎn)的位序就可以得到每個(gè)結(jié)點(diǎn)的后序遍歷順序號(hào)。與前幾步一樣，這里也是一個(gè)處理器計(jì)算一個(gè)結(jié)點(diǎn)的順序號(hào)，多個(gè)處理器并行工作，最后，得到一棵二叉樹的后序遍歷的結(jié)點(diǎn)順序。
2.2 算法示意代碼
??? 算法描述如下：
??? int n；????//二叉樹的結(jié)點(diǎn)個(gè)數(shù)
??? int parent[n]；???//父結(jié)點(diǎn)數(shù)組
??? int lchild[n]；???//左孩子結(jié)點(diǎn)數(shù)組
??? int rchild[n]；???//右孩子結(jié)點(diǎn)數(shù)組
??? int succ[(n，n)]；??//后繼邊數(shù)組
??? int position[(n，n)]；??//鏈表元素的位序數(shù)組
??? int postnode[n]；??//結(jié)點(diǎn)順序號(hào)數(shù)組
??? PostOrder(bitree *t)? //P[(i，j)]是處理對(duì)應(yīng)邊(i，j)的一個(gè)處理器，共2(n-1)個(gè)
??? {
??? 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é)點(diǎn)
?????????????????? }//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é)點(diǎn)
??????????????????????}//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
???? ??? //給單鏈表中的每個(gè)元素賦權(quán)值
???????? if(parent[i]==j)
????????? ??position[(i，j)]=1；
???? ??? else
????????? ??position[(i，j)]=0；
???? ??? //計(jì)算單鏈表中元素的位序
???? ??? 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)???? //求結(jié)點(diǎn)的后序遍歷順序號(hào)
???????????postnode[i]=postion[(i，j)]；
???????? }//forall
??? }
3? 結(jié)束語(yǔ)
??? 以圖1所示的二叉樹為例，按照上述算法構(gòu)造的單鏈表（帶權(quán)值）如圖5所示。表2為二叉樹單鏈表的位序。

?

?