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

• 作者: 王兴波
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 算法设计 二叉树 中序遍历 快速访问
• 年，卷（期）: 2011,（9）
• 所属期刊栏目: 博士论坛
• 页码范围: 16-20,40
• 分类号: TP29/TN710
• 字数: 7783字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2011.09.005

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王兴波	佛山大学机电与信息工程学院	4	11	2.0	3.0