支持可重构计算的满二叉树中序存储策略和快速遍历算法.pdfVIP

第29卷第1期 佛山科学技术学院学报(自然科学版) V01．29No．1 of JournalFoshan ScienceEdition) 2011年1月 University(Natural Jan．2011 文覃编号11008一0171(2011)01—0047一06 支持可重构计算的满二叉树中序存储策略及 快速遍历算法 王兴波 (佛山科学技术学院机电工程系。广东佛山528000) 摘要：通过对满二叉树顺序存储序列与中序序列之间解析关系的研究，推导与证明了完全二叉树的一些重要性 质，给出了一种可快速访问的满二叉树中序序列存储方法并设计出相应的遍历算法。基于该方法。一颗具有Ⅳ 个结点的满二叉树中序序列仅需要线性时间复杂度0(Ⅳ)即可遍历．相关计算过程可嵌入在可重构系统中形 成可重构计算单元．还给出了算法的C++实现过程及可重构系统的设计方案． 关键词：可重构计算；满二叉树；中序序列；快速访问 中图分类号：TP311．12 文献标志码：A 二叉树作为一种重要的数据结构在计算应用中发挥着重要作用．二叉树的访问也一直是计算机科 学技术领域的研究热点之一。 人们知道，除以2的运算在计算机上可以利用右移位实现，不仅高效而且易于通过硬件来实现。鉴 于这样的性质，工业上会将一些需要高速进行的运算转换为二分运算的实现过程，并设计相应的硬件以 提高运算的综合效率。例如，文献[1—2]介绍的高速高精插补器就是这样设计的，该插补器的执行过程 是，首先计算插补曲线的中点并以该中点将插补曲线分成2段子曲线，然后分别对2段子曲线作中分得 到2个点，如此往复直到被中分的子曲线段可以近似成为1个点。采用一颗满二叉树来存储这些中点， 则该二叉树的中序遍历绍果就对应于所插补曲线上的插补点。 上述计算过程及二叉树的中序遍历可简单明了地用递归方法表现出来，但是由于递归运算占用的 时间开销过大，工业上多采用2个或者多个相同的可重构计算单元(如DSP或者FPGA)并行计算，并 且以多个线性存储结构按照顺序存储的方法来存储计算结果【3{]。这样一来，就涉及从多个线性存储结 构中获取一颗满二叉树中序序列的算法问题。由于受制于可重构电路结构，可重构运算与PC级运算在 程序设计、数据存储方面都有差异，致使PC级程序设计与数据结构的诸多方法不能移植应用[6‘7]。因 此，需要研究相应的可重构算法。本文主要研究适用于可重构计算的满二叉树中序序列存储与访问模式 及相关问题。 1 问题的描述、分析及求解算法 1．1问题的描述及关联知识 显然，假如采用2个线性结构的存储器，引言中提出的问题与要求可抽象表述为问题I。 问题I 设丁是一棵深度为以(，z≥o)的满二叉树，丁。是丁的根节点，丁。与乃分别是兀的左右儿 收稿日期：2010一12．16 基金项目：广东省自然科学基金资助项目(10158000100016) 作者简介。王兴波(1963一)．男．湖北安陆人．佛山科学技术学院教授．博士，博士生导师． 万方数据 48 佛山科学技术学院学报(自然科学版) 第29卷 子(子树)，％是存放n的存储结构，％与耽是顺序存储丁。与于。的线性存储结构，给出一种从％、 M。、M：中快速访问丁的中序序列的可重构计算方法。 如果以记号A表示一棵满二叉树，{A}表示A的顺序序列，符号B铸A表示B是对应于A的线性 存储结构，记号(A}表示A的中序遍历序列，则上述问题I的数学描述为： 已知：T=丁o 求从胍、舰、％得到{丁)的方法。 为方便起见，下文采用记号Ⅳ(¨，表示二叉树第量层的第歹个结点，num(A)表示以A为根的满二 叉树所包含的结点个数，懿、5二分别表示结点A的左、右儿子，F胛表示X与y的父结点，％是X与y 的最近共同祖先。本文还将引用以下引理的知识[8]。 引理对于含有忍个结点的完全二叉树，设_f(1≤歹≤力)是其顺序存储序列的第歹个结点，则有 (1)若-『=1，则