js中查找最近的共有祖先元素的实现代码
更新时间：2010年12月30日 22:32:49 作者：
司徒正美给出的题，也尝试着写一下。希望大家多多交流。
（福利推荐：【腾讯云】服务器最新限时优惠活动，云服务器1核2G仅99元/年、2核4G仅768元/3年，立即抢购>>>：9i0i.cn/qcloud）
（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）
先来看概念，首先DOM是一棵树，其根节点是Document，大致可以用下图来表示：
所谓“最近的共有祖先元素”，是指给定一系列元素，找出在树中深度最大的，但同时为所有这些元素的祖先元素的元素。
比如上图中，I和G的结果为C，G和H的结果为A，D和E的结果为html，C和B的结果为html等。
测试驱动
对于偏逻辑的题，并没有十足的把握函数是正确的，因此还是先构造测试的用命，力求让函数通过测试。
本次就以上图的结构作为DOM结构，A表示body，B表示head，其他节点均使用div元素，同时以上文中所说的作为测试的输入和输出，先构造一下测试：
function test() {
var result;
result = find('i', 'g');
result.id !== 'c' && alert('fail (i, g)');
result = find('g', 'h');
result.id !== 'a' && alert('fail (g, h)');
result = find('d', 'e');
result.nodeName.toLowerCase() !== 'html' && alert('fail (d, e)');
result = find('c', 'b');
result.nodeName.toLowerCase() !== 'html' && alert('fail (c, b)');
}
基本逻辑
这次的逻辑大致是这样的：
1、针对每个给定的元素，从父元素到document依次向上遍历。
2、对遍历过程中经过的每个元素，保存到一个有序的map中，以元素为键，以遍历到的次数为值。
2、最后遍历map，找同第一个值与给定元素个数相同的项，就是第一个被所有元素的遍历都经过的元素，也即最近的共同祖先元素了。
细节问题
在实际过程中，对map的构建比较重要，这里涉及到2个问题：
1、map不能直接以元素作为键，必须转换为合适的基元类型（如number, string, Regex等）。
2、chrome对object中的键会有自动排序，因此尽量避免使用number类型作为键。
对于第一个问题，必须给元素绑定一个合适的字段，起到唯一性标识符的作用。好在HTML5提供了data-*属性，使DOM的元数据承载能力有了很大的提高，可以大胆地添加希望的属性了。
对于第二个问题，本身也不难，生成的标识符避开number就行了，方便的方法是加个下划线，或者使用String.fromCharCode转成字符，无论怎么样都无所谓。
实现代码
代码有点长，主要是个人比较喜欢偏JAVA的风格，每一个语句每一个分支都清清楚楚，不喜欢用&&或者||来处理条件分支，所以有很多行只有一个大括号之类的情况，其实真正有效的代码还是精简的。懒得装类似toggle之类的插件，也不想看到滚动条，就随便扔在这了。
function find() {
var length = arguments.length,
i = 0,
node, //当前节点
parent, //父节点
counter = 0,
uuid, //给DOM的唯一标识符
hash = {}; //最后结果的map
//对每一个元素，向上遍历至document
//这个双层的循环是不可避免的
for (; i < length; i++) {
//获取node
node = arguments[i];
if (typeof node == 'string') {
node = document.getElementById(node);
}
//向上遍历
while (parent = node.parentElement || node.parentNode) {
//到document就停下来，不然就是死循环
if (parent.nodeType == 9) {
break;
}
//获取或添加一下标识符
uuid = parent.getAttribute('data-find');
if (!uuid) {
uuid = '_' + (++counter); //避免chrome对hash重排序
parent.setAttribute('data-find', uuid);
}
//增加计数
if (hash[uuid]) {
hash[uuid].count++;
}
else {
hash[uuid] = {node: parent, count: 1};
}
node = parent;
}
}
//hash中只存有各节点向上遍历经过的父节点，不应该很大
//因此这个循环是比较快的
for (i in hash) {
if (hash[i].count == length) {
return hash[i].node;
}
}
};
点评
测试没问题，但测试用例是否完善实在不好说，期待网友帮我找出问题来，对于逻辑型的实在是没啥自信说100%没问题。
对于取父元素，习惯性兼容IE写成parentElement || parentNode，这是因为IE的一个BUG，当一个元素刚被创建出来但未进入DOM时，parentNode是不存在的。不过本次函数保证节点在DOM树中，其实parentElement就没有必要了。所以有时候习惯性的兼容代码也不见得就一定是好事，最适合当前环境的代码才是好代码。
虽然说2重循环不可避免，但总隐隐感觉循环还是有办法在特定情况下少做点事，比如向上遍历的时候发现某个元素已经不可能是所有元素的共有祖先了，那么就不要再去递增count值了。
最后的for..in循环有没有办法省掉呢？在上面的2重循环中有没有办法实时地就通过一个变量始终保存最合适的节点呢？
所谓“最近的共有祖先元素”，是指给定一系列元素，找出在树中深度最大的，但同时为所有这些元素的祖先元素的元素。
比如上图中，I和G的结果为C，G和H的结果为A，D和E的结果为html，C和B的结果为html等。
测试驱动
对于偏逻辑的题，并没有十足的把握函数是正确的，因此还是先构造测试的用命，力求让函数通过测试。
本次就以上图的结构作为DOM结构，A表示body，B表示head，其他节点均使用div元素，同时以上文中所说的作为测试的输入和输出，先构造一下测试：
复制代码 代码如下:
function test() {
var result;
result = find('i', 'g');
result.id !== 'c' && alert('fail (i, g)');
result = find('g', 'h');
result.id !== 'a' && alert('fail (g, h)');
result = find('d', 'e');
result.nodeName.toLowerCase() !== 'html' && alert('fail (d, e)');
result = find('c', 'b');
result.nodeName.toLowerCase() !== 'html' && alert('fail (c, b)');
}
基本逻辑
这次的逻辑大致是这样的：
1、针对每个给定的元素，从父元素到document依次向上遍历。
2、对遍历过程中经过的每个元素，保存到一个有序的map中，以元素为键，以遍历到的次数为值。
2、最后遍历map，找同第一个值与给定元素个数相同的项，就是第一个被所有元素的遍历都经过的元素，也即最近的共同祖先元素了。
细节问题
在实际过程中，对map的构建比较重要，这里涉及到2个问题：
1、map不能直接以元素作为键，必须转换为合适的基元类型（如number, string, Regex等）。
2、chrome对object中的键会有自动排序，因此尽量避免使用number类型作为键。
对于第一个问题，必须给元素绑定一个合适的字段，起到唯一性标识符的作用。好在HTML5提供了data-*属性，使DOM的元数据承载能力有了很大的提高，可以大胆地添加希望的属性了。
对于第二个问题，本身也不难，生成的标识符避开number就行了，方便的方法是加个下划线，或者使用String.fromCharCode转成字符，无论怎么样都无所谓。
实现代码
代码有点长，主要是个人比较喜欢偏JAVA的风格，每一个语句每一个分支都清清楚楚，不喜欢用&&或者||来处理条件分支，所以有很多行只有一个大括号之类的情况，其实真正有效的代码还是精简的。懒得装类似toggle之类的插件，也不想看到滚动条，就随便扔在这了。
复制代码 代码如下:
function find() {
var length = arguments.length,
i = 0,
node, //当前节点
parent, //父节点
counter = 0,
uuid, //给DOM的唯一标识符
hash = {}; //最后结果的map
//对每一个元素，向上遍历至document
//这个双层的循环是不可避免的
for (; i < length; i++) {
//获取node
node = arguments[i];
if (typeof node == 'string') {
node = document.getElementById(node);
}
//向上遍历
while (parent = node.parentElement || node.parentNode) {
//到document就停下来，不然就是死循环
if (parent.nodeType == 9) {
break;
}
//获取或添加一下标识符
uuid = parent.getAttribute('data-find');
if (!uuid) {
uuid = '_' + (++counter); //避免chrome对hash重排序
parent.setAttribute('data-find', uuid);
}
//增加计数
if (hash[uuid]) {
hash[uuid].count++;
}
else {
hash[uuid] = {node: parent, count: 1};
}
node = parent;
}
}
//hash中只存有各节点向上遍历经过的父节点，不应该很大
//因此这个循环是比较快的
for (i in hash) {
if (hash[i].count == length) {
return hash[i].node;
}
}
};
点评
测试没问题，但测试用例是否完善实在不好说，期待网友帮我找出问题来，对于逻辑型的实在是没啥自信说100%没问题。
对于取父元素，习惯性兼容IE写成parentElement || parentNode，这是因为IE的一个BUG，当一个元素刚被创建出来但未进入DOM时，parentNode是不存在的。不过本次函数保证节点在DOM树中，其实parentElement就没有必要了。所以有时候习惯性的兼容代码也不见得就一定是好事，最适合当前环境的代码才是好代码。
虽然说2重循环不可避免，但总隐隐感觉循环还是有办法在特定情况下少做点事，比如向上遍历的时候发现某个元素已经不可能是所有元素的共有祖先了，那么就不要再去递增count值了。
最后的for..in循环有没有办法省掉呢？在上面的2重循环中有没有办法实时地就通过一个变量始终保存最合适的节点呢？
相关文章
这篇文章主要介绍了微信小程序使用百度AI识别接口的通用封装Promise,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下2023-04-04
本文详细介绍了javascript函数的四种调用模式。具有一定的参考价值，下面跟着小编一起来看下吧2017-01-01
这篇文章主要介绍了微信小程序提交form操作,结合实例形式分析了微信小程序开发中使用form组件实现数据提交与数据处理相关操作技巧,需要的朋友可以参考下2018-12-12
这篇文章主要介绍了使用typescript推导已有变量的盲盒类型详情，文章围绕主题展开详细的内容介绍，具有一定的参考价值，需要的小伙伴可以参考一下2022-08-08
这篇文章主要介绍了JS实现时间校验的代码,本文通过实例代码给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下2020-05-05
这篇文章主要介绍了jquery实现简单的遮罩层相关代码，内容很丰富，教大家实现遮罩层效果，感兴趣的小伙伴们可以参考一下2016-01-01
我们在开发项目中都会遇到这种场景,区分开发环境、生产环境、测试环境,不同场景请求不同的接口Api,这时候项目中配置的「环境变量」就登场啦,这篇文章主要给大家介绍了关于Webpack中使用环境变量的各种正确姿势,需要的朋友可以参考下2021-09-09
用JavaScript绘图 ——JS2D函数集...2007-01-01
这篇文章主要介绍了javascript触发模拟鼠标点击事件,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下2019-06-06
JS window对象的top、parent、opener含义介绍
本文为大家介绍下JS window对象的top、parent、opener含义，不了解的朋友可以参考下，希望对大家有所帮助2013-12-12
最新评论