- 1 -
PRAM 模型下二叉树的中序遍历的并行算法
刘全升
西南大学 计算机与信息科学学院 重庆 （400715）
摘要 本文基于 PRAM（Parallel Random Access Machine,并行共享
存储器模型）模型讨论二叉树的中序遍历问题，提出了二叉树的中序
遍历的一种并行算法，同时对该算法的复杂度进行了分析。
关键词 中序遍历 并行算法 二叉树
1、引言
二叉树的遍历是指对二叉树进行线性化的一个过程。树，尤其是
二叉树在递归与非递归转换，数据挖掘以及人工智能等领域都有重要
的应用。在二叉树的应用中，很大一部分问题都要转化对二叉树进行
遍历。由遍历时根的顺序不同可以引出三种不同的的遍历二叉树的方
法：一种是先序遍历二叉树，即：先访问树的根结点，然后依次先序
遍历根的左子树，右子树；另一种是中序遍历二叉树，即：先中序遍
历左子树，然后访问根结点，再中序遍历右子树；还有一种方法是后
序遍历二叉树，即：先中序遍历左子树，然后中序遍历右子树，再访
问根结点。目前对于二叉树的遍历问题主要采用的是串行算法，串行
计算在较小规模问题的领域具有优势，但对于大规模的问题，并行计
算是解决的有效途径。通过并行方式基于边的角度来考虑树的遍历，
最初由 Tarjan 等提出并实现了树的先根遍历的并行算法［１］，后来，
熊家军等人提出了树的后根遍历的并行算法，本文旨在介绍一种通过
构造图论中著名的欧拉圈［２］（注：欧拉圈即遍历欧拉图中的边所得
到的欧拉闭迹，欧拉图既图内每个顶点的度数为偶数的图）来实现二
叉树的并行中序遍历。
本文第二部分介绍我们常用的二叉树遍历的串行算法；第三部分
介绍并行计算中常用的 PRAM 模型；第四部分结合 PRAM 实现对二叉树
中序遍历算法的改进，提出改进算法 ；然后对其复杂度与常用遍历
- 2 -
算法进行对比，最后得出结论。
2 二叉树中序遍历的串行算法
在串行算法中，二叉树的中序遍历的递归描述如下 ［３］：
Inorder(Node* root) root 为根结点
Begin
If root=null then return;
Inorder(root->lchild); 先遍历左子树
Visit(root—>data); 访问结点
Inorder(root->rchild);后遍历右子树
End
二叉树的遍历实质是对二叉树中的结点进行线性化的一个过程，如果
我们换一个角度去思考二叉树的遍历，则可把二叉树的遍历的过程看
成是求二叉树的线性化后结点在线性序列中的编号的过程，如果把树
当作一个图的特例来看的话，树的遍历实际上也遍历了树的所有边，
并且每条边都是遍历两次（父结点->子结点，子结点->父结点），如
果将树的无向边看成是两条有向边的组合，是树的遍历问题可看成是
图中边的遍历问题（欧拉图），如果将每条有向边分配一个独立的处
理器进行处理，利用多处理机实现数据并行，则可实现树的遍历的并
行算法。
3 并行计算的 PRAM 模型［４］
并行计算的直连网络中，各个处理器之间是通过物理链路直接连
接的，而在 PRAM（Parallel Access Machine）模型中，所有的处理
器都与全局大内存相连并且共享此内存（如下图所示）。在此模型中，
每个处理器都能对整个内存进行读写操作，各个处理器之间的通信也
是通过共享全局大内存来实现。该模型是对一类共享存储并行计算机
的特征提取，假设了网络带宽充足，可直接开发原始算法内在细粒度
并行。PRAM 模型的优点是易于实现数据的共享。
- 3 -
图 1 PRAM 模型图
PRAM 模型一般以 SIMD 模型方式工作，在 PRAM 中，根据多个处理器
对一个存储单元读写数据的能力，可以分为四种不同类型：
互斥读互斥写 PRAM（EREW） 并发读互斥写 PRAM（CREW）
互斥读并发写 PRAM（ERCW） 并发读并发写 PRAM（CRCW）
4 中序遍历并性算法的实现
算法步骤：通过二叉树的领接表构造欧拉圈，通过欧拉圈求出二叉树
中每一结点的中序遍历编号。
（1）构造欧拉圈
算法 Euler Circuit
输入：具有附加的指针（Parent，Lchild，Rchild）且由邻接表所表
示的树 Root
输出：每个弧<u,v>的后继函数 Sucessor(<u,v>)
Begin
For every arc<u,v>,do step PR in parallel 对每一条弧进行下列操作
PR: Successor(<u,v>)=<v,w>,where w occurs next to u in the
ordered list of vertices adjacent to v. If u appears last in
the list of vertices adjacent to v,then w is the first int the
list
End
例：假定 v 是顶点，u0,u1,u2 是与 v 相邻的顶点，则
Successor(<u0,v>)=<v,u1>
Successor(<u1,v>)=<v,u2>
- 4 -
Successor(<u2,v>)=<v,u0>
复杂度分析：该算法使用 O(n)个处理器在 O(1)的时间内可以完成。n
是树中有向边（弧）的条数。
（2）求结点的中序遍历编号
算法 Inorder Numbering
输入：亲--子关系给定一棵二叉树 Root；由(1)算法求出的 Root 的
欧拉圈
输出：对于每一个顶点 v，输出其在中序遍历中的编号 In(v)
Begin
For every arc<u,v> do in parallel
If u=v->Parent and v=u->Rchild ,（<父结点,右子树>赋权 1）
then assign the weight 1;
If u=v->Lchild and u->Rchild=null,(<右子树为空的左孩子结点，父结点>)
then assign the weight 1;
If u=v->Rchild and u->Rchild=null, (<右子树为空的右孩子结点，父结点>)
then assign the weight 1;
Else assign the weight 0 to the arc<u,v>,end parallel
Find the prefix sum of the list of weights specified by the
successor function
For every arc<u,v> do in parallel
If u=v->Parent and v=u->Rchild （<父结点,右子树>赋权 1）
then In(u)=prefix sum of the arc<u,v>
If u=v->Lchild and u->Rchild=null (<右子树为空的左孩子结点，父结点>)
then In(u)=prefix sum of the arc<u,v>
If u=v->Rchild and u->Rchild=null (<右子树为空的右孩子结点，父结点>)
then In(u)=prefix sum of the arc<u,v>
If u=Root and u->Rchild=null then In(u)=n （没有右子树的根结点中序
遍历序号为 n）
- 5 -
End parallel
End Inorder Numbering
例：如图所示的二叉树，其欧拉圈以及中序遍历所得的各条弧前缀和
如下图所示：
图 2 二叉树示例
欧拉路 权重 前缀和 欧拉路 权重 前缀和
<1,2> 0 0 <1,3> 1 6Æln(1)=6
<2,4> 0 0 <3,6> 0 6
<4,8> 0 0 <6,10> 0 6
<8,4> 1 1Æln(8)=1 <10,6> 1 7Æln(10)=7
<4,9> 1 2Æln(4)=2 <6,3> 1 8Æln(6)=8
<9,4> 1 3Æln(9)=3 <3,7> 1 9Æln(3)=9
<4,2> 0 3 <7,11> 1 10ÆIn(7)=10
<2,5> 1 4Æln(2)=4 <11,7> 1 11Æln(11)=11
<5,2> 1 5Æln(5)=5 <7,3> 0 11
<2,1> 0 5 <3,1> 0 11
中序遍历顺序：8—4—9—2—5—1—10—6—3—7—11
图 3 中序遍历作为前缀和
复杂度分析：算法所有的处理器个数为 O(N),执行时间为 O(log N),N
为有向弧数。因为在求各条弧的前缀和时要共享读，因此需要执行
CREW PRAM 模型。
5 算法复杂度分析及比较/实验结果：
在串行算法中，无论是递归还是非递归的求解，都必须串行执行的一
- 6 -
条语句是：访问结点（VISITED（NODE）），因此对于一棵有 n 个结
点的二叉树，其时间复杂度为 O（n）。
在该算法中，一棵有 n 个结点的二叉树有 n-1 条边，将每条边转换成
两条弧，因此它共有 2n-2 条弧，因此，该算法需要 2n-2 个处理机。
该算法中时间主要花费在求结点的中序遍历编号上，其计算时间复杂
度为 O（㏒ n），算法的其余部分的计算时间是常数，所以，该算法
的时间复杂度为 O（㏒ n）， n 为二叉树所有的结点数。
6．小结
通过比较，我们可以发现，在并行计算时，用 O（㏒ n）的时间可以
完成二叉树的中序遍历，与串性算法相比，有明显的优势，本算法使
用的并行计算模型是 CREW，在以后，可以探索将其改进为用 EREW 模
型。随着计算机科学的发展，并行计算将是算法发展的一种趋势
参考文献
[1]Tarjan R E,U Vishkin ,An efficient parallel bin connectivity
algorithm [J]SIAM Journal of Computer ,1985:14:862-874
[2] （印）等著，张云泉等译 并行算法导论 北京 机械工
业出版社 2003
[3]严蔚敏 数据结构（C 语言版）北京 清华大学出版社 1997
[4]朱立华 并行拓扑排序算法的设计与实现 中国科技论文在线
2004
A Parallel Algorithm of Inorder-traversal of Bi-Tree Based
on PRAM Model
LiuQuanSheng
(Faculty of Computer and Information Technology Southwest University
Chongqing 400715 )
Abstract: It talked about bi-tree researched based on PRAM model and
proposed a parallel algorithm of inorder-traversal of bi-tree. In
addition, it analyzed the complexity of the parallel algorithm.
Keywords: Inorder-traversal, parallel algorithm, bi-tree
