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