快捷導(dǎo)航

js中查找最近的共有祖先元素的實(shí)現(xiàn)代碼

更新時(shí)間：2010年12月30日 22:32:49 作者：

司徒正美給出的題，也嘗試著寫一下。希望大家多多交流。

先來看概念，首先DOM是一棵樹，其根節(jié)點(diǎn)是Document，大致可以用下圖來表示：

所謂“最近的共有祖先元素”，是指給定一系列元素，找出在樹中深度最大的，但同時(shí)為所有這些元素的祖先元素的元素。

比如上圖中，I和G的結(jié)果為C，G和H的結(jié)果為A，D和E的結(jié)果為html，C和B的結(jié)果為html等。

測(cè)試驅(qū)動(dòng)
對(duì)于偏邏輯的題，并沒有十足的把握函數(shù)是正確的，因此還是先構(gòu)造測(cè)試的用命，力求讓函數(shù)通過測(cè)試。

本次就以上圖的結(jié)構(gòu)作為DOM結(jié)構(gòu)，A表示body，B表示head，其他節(jié)點(diǎn)均使用div元素，同時(shí)以上文中所說的作為測(cè)試的輸入和輸出，先構(gòu)造一下測(cè)試：

復(fù)制代碼代碼如下:

 
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、針對(duì)每個(gè)給定的元素，從父元素到document依次向上遍歷。
2、對(duì)遍歷過程中經(jīng)過的每個(gè)元素，保存到一個(gè)有序的map中，以元素為鍵，以遍歷到的次數(shù)為值。
2、最后遍歷map，找同第一個(gè)值與給定元素個(gè)數(shù)相同的項(xiàng)，就是第一個(gè)被所有元素的遍歷都經(jīng)過的元素，也即最近的共同祖先元素了。
細(xì)節(jié)問題
在實(shí)際過程中，對(duì)map的構(gòu)建比較重要，這里涉及到2個(gè)問題：

1、map不能直接以元素作為鍵，必須轉(zhuǎn)換為合適的基元類型（如number, string, Regex等）。
2、chrome對(duì)object中的鍵會(huì)有自動(dòng)排序，因此盡量避免使用number類型作為鍵。

對(duì)于第一個(gè)問題，必須給元素綁定一個(gè)合適的字段，起到唯一性標(biāo)識(shí)符的作用。好在HTML5提供了data-*屬性，使DOM的元數(shù)據(jù)承載能力有了很大的提高，可以大膽地添加希望的屬性了。

對(duì)于第二個(gè)問題，本身也不難，生成的標(biāo)識(shí)符避開number就行了，方便的方法是加個(gè)下劃線，或者使用String.fromCharCode轉(zhuǎn)成字符，無論怎么樣都無所謂。
實(shí)現(xiàn)代碼
代碼有點(diǎn)長(zhǎng)，主要是個(gè)人比較喜歡偏JAVA的風(fēng)格，每一個(gè)語句每一個(gè)分支都清清楚楚，不喜歡用&&或者||來處理?xiàng)l件分支，所以有很多行只有一個(gè)大括號(hào)之類的情況，其實(shí)真正有效的代碼還是精簡(jiǎn)的。懶得裝類似toggle之類的插件，也不想看到滾動(dòng)條，就隨便扔在這了。

復(fù)制代碼代碼如下:

 
function find() { 
var length = arguments.length, 
i = 0, 
node, //當(dāng)前節(jié)點(diǎn) 
parent, //父節(jié)點(diǎn) 
counter = 0, 
uuid, //給DOM的唯一標(biāo)識(shí)符 
hash = {}; //最后結(jié)果的map 

//對(duì)每一個(gè)元素，向上遍歷至document 
//這個(gè)雙層的循環(huán)是不可避免的 
for (; i < length; i++) { 
//獲取node 
node = arguments[i]; 
if (typeof node == 'string') { 
node = document.getElementById(node); 
} 
//向上遍歷 
while (parent = node.parentElement || node.parentNode) { 
//到document就停下來，不然就是死循環(huán) 
if (parent.nodeType == 9) { 
break; 
} 
//獲取或添加一下標(biāo)識(shí)符 
uuid = parent.getAttribute('data-find'); 
if (!uuid) { 
uuid = '_' + (++counter); //避免chrome對(duì)hash重排序 
parent.setAttribute('data-find', uuid); 
} 
//增加計(jì)數(shù) 
if (hash[uuid]) { 
hash[uuid].count++; 
} 
else { 
hash[uuid] = {node: parent, count: 1}; 
} 
node = parent; 
} 
} 
//hash中只存有各節(jié)點(diǎn)向上遍歷經(jīng)過的父節(jié)點(diǎn)，不應(yīng)該很大 
//因此這個(gè)循環(huán)是比較快的 
for (i in hash) { 
if (hash[i].count == length) { 
return hash[i].node; 
} 
} 
}; 

點(diǎn)評(píng)
測(cè)試沒問題，但測(cè)試用例是否完善實(shí)在不好說，期待網(wǎng)友幫我找出問題來，對(duì)于邏輯型的實(shí)在是沒啥自信說100%沒問題。
對(duì)于取父元素，習(xí)慣性兼容IE寫成parentElement || parentNode，這是因?yàn)镮E的一個(gè)BUG，當(dāng)一個(gè)元素剛被創(chuàng)建出來但未進(jìn)入DOM時(shí)，parentNode是不存在的。不過本次函數(shù)保證節(jié)點(diǎn)在DOM樹中，其實(shí)parentElement就沒有必要了。所以有時(shí)候習(xí)慣性的兼容代碼也不見得就一定是好事，最適合當(dāng)前環(huán)境的代碼才是好代碼。
雖然說2重循環(huán)不可避免，但總隱隱感覺循環(huán)還是有辦法在特定情況下少做點(diǎn)事，比如向上遍歷的時(shí)候發(fā)現(xiàn)某個(gè)元素已經(jīng)不可能是所有元素的共有祖先了，那么就不要再去遞增count值了。
最后的for..in循環(huán)有沒有辦法省掉呢？在上面的2重循環(huán)中有沒有辦法實(shí)時(shí)地就通過一個(gè)變量始終保存最合適的節(jié)點(diǎn)呢？