下面分析本文中的算法步骤。
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 { 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为二叉树单链表的位序。