Vol123No15第23卷第5期2002年5月小型微型计算机系统MINI-MICROSYSTEM文章编号:100021220(2002)0520580203树的后根遍历的一种并行算法熊家军1,2李庆华1张志祥11(华中科技大学计算机学院,湖北武汉430074)2(空军雷达学院,湖北武汉430019)摘要:例.本文运用并行计算的PRAM模型研究树的遍历问题,提出了树的后根遍历的一种并行算法,并给出了一个实关键词:后序遍历;并行算法;树文献标识码:A:TP301.61引言2并行计算的PRAM模型PRAM(parallelrandomaccessmachine)模型〔4〕使并行算法的设计者可以把处理器的能力看成是无限的,就像程序员有了虚拟内存后可以把内存看成无限的一样.一个PRAM由一个控制单元,全局内存,和一组处理器集合组成,每个处理器有它自己的私有内存.所有处理器执行相同的指令,但每个处理器处理的数据不一样.PRAM模型有四种不同之处主要在于它们处理读写冲突的方式的差异〔5〕.树是一种重要的数据结构,它是n(n≥0)个结点的有限集.在任意一棵非空树中:(1)有且仅有一个特定的称为根的(Root)的结点;(2)当n>1时其余结点可分为m(m>0)个互不相交的有限集T1,T2,,Tm,其中每个集合本身又是一棵树,并且称为根的子树〔1〕.由根的定义可以引出两种次序遍历树的方法:一种是先根遍历(也称先序遍历)树,即:先访问树的根结点,然后依次先根遍历根的每棵子树;另一种是后根遍历(也称后序遍历)树,即:先依次后根遍历每棵子树,然后访问根结点.本文将研究树的后根遍历.树的后根遍历的递归描述如下〔2〕:POSTORDERTRAVERSAL(nodeptr)BeginIfnodeptr≠nullthenPOSTORDER.TRAVERSAL(nodeptr.mostleft){mostleft是最左边的一棵子树}POSTORDER.TRAVERSAL(nodeptr.otherforest){otherforest是剩下的子树森林}Visit(node)EndifEnd基本的操作是按照后序遍历过程访问结点,让每个结点被且仅被访问一次.这种方式实现的算法称之为串行算法.但是如果我们换个角度来研究树的遍历问题,从串行算法中以树的结点为重点考察对象,转变为重点研究树的边的遍历问题,情况会怎样呢?当进行树的一次遍历时实际也遍历了树的所有边,而且每条边遍历了两次,一次是从双亲结点到子结点,另一次则相反,是从子结点到双亲结点.如果将每条图1树的两种表示本文算法中采用“并行读排他写”PRAM模型,即CREW(ConcurrentReadExclusiveWrite)方式.3算法的实现过程算法的实现使用了一个特殊的数据结构来表示树.对每个树结点,数据结构保存结点的双亲,右边最接近的兄弟和最左边的孩子,利用这三个参数来描述一个树结点在树中的相对位置.对如图1(a)所示的树,其数据结构表示如下:表1结点关系结点APARENTNULLSIBLINGNULLBACECADDANULLEBFFBGDHGNULLNULLNULLCHILDBNULLGNULLNULLHNULL整个算法可以分为4步:收稿日期:2001201203作者简介:熊家军,副教授,华中科技大学博士研究生,主要研究领域为计算机网络体系结构、计算机网络互连技术网络并行计算和网络安全.李庆华,教授,博士导师.张志祥,博士研究生.一种情况是结点j有孩子结点,如图3(a)所示,则根据后序遍历的思想可得,边(i,j)的后继边是从结点j指向结点j的最左边的孩子结点Child构成的边;另一种情况是结点j没有孩子结点,即结点j为叶结点,如图3(b)所示.则根据后序遍历的思想可得,边(i,j)的后继边是结点j指向结点i的向上边.第二步,给单链表中的每个元素赋权值.与第一步一样,也是所有的处理器同时对分配给它的一个元素赋权值(这里的元素是指第一步形成的单链表的元素).根据后序遍历的思想,对于树的一个结点i(根结点例外,必须作不同处理),如果一条向下遍历的边(i,j)从结点i出发,说明正在寻找从该结点i出发的后继边,结点i没有被访问;如果一条向上遍历的边(i,j)从结点i出发,说明刚访问完结点i.我们将单链表中对应向上边的元素赋权值1(表示遍历向上边时增加了一个被访问结点),对应向下边的元素赋权值0(表示遍历向下边时未增加被访问结点),对应根结点的环形边元素也赋权值0(特殊处理).第一步,构造一个单链表.为了描述的直观、方便,我们可以将无向图改造成一个相对应的有向图,改造方法是将无向图的每条无向边改造成一条向下和另一条向上的两条有向边,结点不变.如图1(a)的无向图可以改造成相应的有向图1(b).构造单链表的...