二叉树演绎于结点序号内蕴性质的快速算法

摘要：

通过研究二又树结点顺序存储序号的性质,演绎出了二叉树非递归无堆栈的一些新算法,包括完全二叉树两结点最近共同祖先(LCA)的查询算法、中序遍历算法、顺序序列与中序序列的互转算法以及从中序序列恢复层次结构的算法.新的算法都具有很好的时间复杂度,其中LCA查询算法可在常数时间内实现且不需要任何顸处理过程,其他算法均为线性时问复杂度.所有算法均为常数空间复杂度,仅涉及到简单的加减运算与位运算,既可用于常规程序设计也可用于嵌入式等专业开发.

关键词：算法设计、二叉树、中序遍历、快速访问

所属期刊栏目：47

分类号：TP29;TN710(自动化技术及设备)

资助基金：数学机械化证明国家重点实验室开放基金the Open Research Foundation of State Key Laboratory of Mathematics Mechanization under Grant KLMM0906;广东省自然科学基金10158000100016;佛山市产学研项目2010C012

在线出版日期：2011-09-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：16-20,40