摘要
基于对满二叉树结点序号的研究,得到了满二叉树的层次结构、顺序序列与后序序列三者之间在数学上的对应关系,演绎出了满二叉树的层次结构及其顺序序列与后序序列之间互相转换的快速算法。算法可在常数时间内完成单个结点的查询、在线性时间内完成整个序列的遍历。算法编码简洁,仅包含加、减、乘法与位运算,无递归调用无堆栈开销,几乎没有分支与跳转,不仅适合常规程序设计,而且适合于片上系统的专业开发。文中还指出了算法在机电设计方面的应用点。
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.
出处
《计算机工程与设计》
CSCD
北大核心
2013年第3期873-877,共5页
Computer Engineering and Design
基金
广东省工业攻关基金项目(2012B010600018)
佛山市科技发展专项基金项目(2011AA100021
2011GY006
2011B1023)
佛山市产学研专项基金项目(2010C012)
关键词
二叉树
非递归
后序遍历
片上系统
机电系统
binary tree non-recursive
postorder traversal system-on-chip mechatronic systems
