计算机工程与应用2011，Vol.47Issue(9)：16-20,40,6.DOI:10.3778/j.issn.1002-8331.2011.09.005
二叉树演绎于结点序号内蕴性质的快速算法
Fast algorithms educed from intrinsic properties of node indices of binary trees.
摘要
Abstract
Through a study on properties of node-indices of a binary tree,the paper derives for processing binary trees several new non-recursive and stack-free algorithms,including an algorithm to query the Lowest Common Ancestor(LCA) of two nodes in a complete binary tree,an algorithm for fast inorder traverse,an algorithm for inter-conversions between the sequential sequence and the inorder sequence,and an algorithm to restore a complete binary tree from its sequential sequence or inorder sequence.All the new algorithms are of excellent time-complexity and spatial complexity.In aspect of time-complexity,the new LCA-query algorithm can answer without any preprocessing a query of LCA of two nodes in a complete binary tree in constant time and the other new algorithms are linear time complexity.In aspect of spatial complexity, all the new algorithms are constant spatial complexity.Furthermore,all new algorithms contain merely addition,subtraction and bitwise operations and thus fit both conventional programming and expert developments such as embedded system and so on.关键词
算法设计/二叉树/中序遍历/快速访问Key words
algorithm design/ binary tree/ inorder traversal/ fast query分类
信息技术与安全科学引用本文复制引用
王兴波..二叉树演绎于结点序号内蕴性质的快速算法[J].计算机工程与应用,2011,47(9):16-20,40,6.基金项目
数学机械化证明国家重点实验室开放基金(the Open Research Foundation of State Key Laboratory of Mathematics Mechanization under Grant No.KLMM0906) （the Open Research Foundation of State Key Laboratory of Mathematics Mechanization under Grant No.KLMM0906）
广东省自然科学基金(No.10158000100016) （No.10158000100016）
佛山市产学研项目(No.2010C012). （No.2010C012）
