完全二叉树相邻结点最近共同祖先的一种快速算法
王珏
华中科技大学计算机科学与技术学院,湖北武汉430074;广东丽普盾高新科技有限公司,广东佛山528000
摘要：寻找二叉树中两结点的最近共同祖先问题一直是图论与计算机科学关注的问题.首先,证明了完全求解二叉树相邻结点最近共同祖先的一个定理,该定理的求解方法主要涉及到位运算,无需递归搜索,既易于软件编程实现又易于通过硬件实现,然后给出了一个具有对数时间复杂度O(lnn)的快速算法及C++示例.
关键词：二叉树最近共同祖先计算
分类号：TP311.12(计算技术、计算机技术)
资助基金：广东省工业科技攻关计划(2012B010600018)佛山市科技发展专项(2011AA100021,2011GY006,2011B1023)佛山市产学研专项(2010C012)
论文发表日期：2013-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：4( 55-58 )
英文信息