完全二叉树相邻结点最近共同祖先的一种快速算法  

Fast algorithm for finding the lowest common ancestor of two neighboring nodes in a complete binary tree

作　　者：王珏[1,2] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074 [2]广东丽普盾高新科技有限公司,广东佛山528000

出　　处：《佛山科学技术学院学报（自然科学版）》2013年第6期55-58,共4页Journal of Foshan University(Natural Science Edition)

基　　金：广东省工业攻关项目(2012B010600018);佛山市科技发展专项资金项目(2011AA100021;2011GY006;2011B1023);佛山市产学研专项资助课题(2010C012)

摘　　要：寻找二叉树中两结点的最近共同祖先问题一直是图论与计算机科学关注的问题。首先,证明了完全求解二叉树相邻结点最近共同祖先的一个定理,该定理的求解方法主要涉及到位运算,无需递归搜索,既易于软件编程实现又易于通过硬件实现,然后给出了一个具有对数时间复杂度O(lnn)的快速算法及C++示例。Finding the lowest common ancestor （LCA） of two nodes in a binary tree has been focused both in graph theory and computer science. The paper first proves a theorem for finding the LCA of two neighboring nodes in a complete binary tree. The method in the theorem mainly concerns bitwise operations, needs no recursive searching procedures and thus is easy to be realized by software programming as well as firmware mode. In the end of the paper, an algorithm that has logarithmic time complexity is also presented with C＋＋ implementation.

关 键 词：二叉树 最近共同祖先 计算 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]