| 完全二叉树相邻结点最近共同祖先的一种快速算法 |
| |
| 引用本文： | 王珏.完全二叉树相邻结点最近共同祖先的一种快速算法[J].佛山科学技术学院学报(自然科学版),2013(6):55-58. |
| |
| 作者姓名： | 王珏 |
| |
| 作者单位： | 华中科技大学计算机科学与技术学院,湖北武汉430074;广东丽普盾高新科技有限公司广东佛山528000 |
| |
| 基金项目： | 广东省工业攻关项目（2012B010600018）;佛山市科技发展专项资金项目（2011AA100021,2011GY006,2011B1023）;佛山市产学研专项资助课题（2010C012） |
| |
| 摘 要： | 寻找二叉树中两结点的最近共同祖先问题一直是图论与计算机科学关注的问题.首先,证明了完全求解二叉树相邻结点最近共同祖先的一个定理,该定理的求解方法主要涉及到位运算,无需递归搜索,既易于软件编程实现又易于通过硬件实现,然后给出了一个具有对数时间复杂度O（lnn）的快速算法及C＋＋示例.
|
| 关 键 词： | 二叉树 最近共同祖先 计算 |
Fast algorithm for finding the lowest common ancestor of two neighboring nodes in a complete binary tree |
| |
| WANG Jue.Fast algorithm for finding the lowest common ancestor of two neighboring nodes in a complete binary tree[J].Journal of Foshan University(Natural Science Edition),2013(6):55-58. |
| |
| Authors: | WANG Jue |
| |
| Institution: | WANG Jue (1. Huazhong University of Science and Technology,Wuhan 430074,China 2. Neptune High Tech Co Ltd of Gnangdong, Foshan 528000 ,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | binary tree lowest common ancestor computation |
| 本文献已被 CNKI 维普 等数据库收录！ |
