用于片上系统的二叉树快速遍历算法  

Fast algorithms for traversal of binary trees available for SoC

作　　者：王兴波[1] 

机构地区：[1]佛山大学机电系,广东佛山528000

出　　处：《计算机工程与设计》2013年第3期873-877,共5页Computer Engineering and Design

基　　金：广东省工业攻关基金项目(2012B010600018);佛山市科技发展专项基金项目(2011AA100021;2011GY006;2011B1023);佛山市产学研专项基金项目(2010C012)

摘　　要：基于对满二叉树结点序号的研究,得到了满二叉树的层次结构、顺序序列与后序序列三者之间在数学上的对应关系,演绎出了满二叉树的层次结构及其顺序序列与后序序列之间互相转换的快速算法。算法可在常数时间内完成单个结点的查询、在线性时间内完成整个序列的遍历。算法编码简洁,仅包含加、减、乘法与位运算,无递归调用无堆栈开销,几乎没有分支与跳转,不仅适合常规程序设计,而且适合于片上系统的专业开发。文中还指出了算法在机电设计方面的应用点。A mathematical corresponding relationship among a full binary tree, its sequential storage and its postorder-traversal storage are obtained by study of the node-indices of the binary tree. Based on the relationship, the algorithm is introduced that can fast convert a full binary tree and its sequential storage into its postorder-traversal storage, or vice versa. The algorithms can answer a query in constant time and perform a traversal in linear time. Being non-recursive and stack-free, having almost no branches or jumps and containing merely addition, subtraction, multiplication and bitwise operations, the algorithms are very concise and available for both conventional programming and professional developments such as systems-on-chip, embedded systems and so on. A guidance is presented for the algorithms to be used in design of mechatronic systems.

关 键 词：二叉树 非递归 后序遍历 片上系统 机电系统 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论] TP39[自动化与计算机技术—计算机科学与技术]