文献类型：期刊文章

作　　者：王兴波[1]

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

出　　处：《计算机工程与应用》

基　　金：数学机械化证明国家重点实验室开放基金(No.KLMM0906);广东省自然科学基金(No.10158000100016);佛山市产学研项目(No.2010C012)~~

年　　份：2011

卷　　号：47

期　　号：9

起止页码：16-20

语　　种：中文

收录情况：AJ、BDHX、BDHX2008、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、INSPEC、JST、RCCSE、ZGKJHX、核心刊

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

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

分 类 号：TP29] TN710]