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

摘要

寻找二叉树中两结点的最近共同祖先问题一直是图论与计算机科学关注的问题。首先,证明了完全求解二叉树相邻结点最近共同祖先的一个定理,该定理的求解方法主要涉及到位运算,无需递归搜索,既易于软件编程实现又易于通过硬件实现,然后给出了一个具有对数时间复杂度O(lnn)的快速算法及C++示例。