完全二叉树非递归无堆栈先序遍历算法的研究  

Study on non-recursive and stack-free algorithms for preorder traversal of complete binary trees

作　　者：王兴波[1] 

机构地区：[1]佛山大学机电与信息工程学院,广东佛山528000

出　　处：《计算机工程与设计》2011年第9期3077-3081,共5页Computer Engineering and Design

基　　金：广东省自然科学基金项目(10158000100016);佛山市产学研专项基金项目(2010C012)

摘　　要：通过对满二叉树的层次结构、顺序序列与先序序列三者之间解析关系的研究,得到了满二叉树的层次结构及顺序序列与先序序列之间互相转换的算法,并由此演绎出了非递归无堆栈方式的完全二叉树先序遍历以及先序与顺序互转算法。该算法可在常数时间内完成单个结点的查询,在线性时间内完成整个序列的遍历或互转。以精准二进制编码的解析公式为基础,易于与位运算结合,不仅适合常规程序设计,而且适合于嵌入式及相关的专业开发。通过一个简单的示例,说明了该算法在虚拟植物建模方面的应用。Through a study on the analytic relationship among a full binary tree,its sequential storage sequence and its preorder-traversal sequence,a algorithms is obtained,which can convert a full binary tree and its sequential storage sequence into its preorder-traversal sequence.Consequently,non-recursive and stack-free algorithms are deduced for preorder traversal of a complete binary tree and for inter-conversions between the sequential storage sequence and the preorder-traversal sequence.The algorithms can answer a query of a node in constant time and perform a traversal in linear time.Being derived from exact mathematical analysis and inosculated with deductions of binary encodes that naturally fit the bitwise operation,the algorithms are available for both conventional programming and professional developments such as embedded system and so on.A sample example is presented to demonstrate the application of the algorithms in virtual-plants modeling.

关 键 词：二叉树 顺序存储 先序遍历 非递归无堆栈 虚拟植物 

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