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

摘要

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.%基于对满二叉树结点序号的研究,得到了满二叉树的层次结构、顺序序列与后序序列三者之间在数学上的对应关系,演绎出了满二叉树的层次结构及其顺序序列与后序序列之间互相转换的快速算法.算法可在常数时间内完成单个结点的查询、在线性时间内完成整个序列的遍历.算法编码简洁,仅包含加、减、乘法与位运算,无递归调用无堆栈开销,几乎没有分支与跳转,不仅适合常规程序设计,而且适合于片上系统的专业开发.文中还指出了算法在机电设计方面的应用点.