非递归遍历 DOM 结构

上次在Google+ 上说 实现了非递归遍历 DOM 结构， 有朋友想让分享，我当然很高兴，但是很遗憾这本身没有什么值得分享的，大致如下， 给大家随便看一下：

常见的递归方式遍历方式，下面是 Douglas Crockford 写的递归实现：

function walkTheDOM (node, func) {
    func(node);
    node = node.firstChild;
    while (node) {
        walkTheDOM(node, func);
        node = node.nextSibling;
    }
}
1
2
3
4
5
6
7
8

然后有人自称写出了更快的遍历 DOM 方式。

var elems = document.getElementsByTagName("*");
for(var i=0,l=elems.length; i<l; i++){
    handler(elems[i]);
}
1
2
3
4

最初找到有详细对照的文章地址没有找到，这个是 类似的一篇， 而且也是非递归式的。

确实是很快的，但只是快还是不够的，这个实现有很多弊端：

  1. 注释等元素未必会被遍历。
  2. 树形数据结构被整理成了平板结构，无法实现遍历过程的 in/out 处理。

然后今天的主角隆重登场：

function walk(node, enter, leave){
    var tmp, n=node;
    label:
    do{
        enter(n);
        if(tmp = firstNode(node)){ // firstChild(HTMLElement)
            n = tmp;
        }else if(tmp = nextNode(n)){ // nextSibling(HTMLElement)
            n = tmp;
        }else if(n.parentNode){
            do{
                n = n.parentNode;
                leave(n);
                if(n == node){break label;}
                if(tmp = nextNode(n)){
                    n = tmp;
                    continue label;
                }
            }while(node);
        }else{
            break;
        }
    }while(n && n!=node);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上面只是一个精简版，实际过程中还需要考虑节点类型的问题，一般会过滤 1:HTMLElement, 8:Comment, 9:Document Type, 10:DocType 之外的节点。

其实也不过如此嘛，飘过~~

See Also

Help
[count]gg 跳转到第 [count] 行，默认第 1 行。
[count]G 跳转到第 [count] 行，默认最后一行。
[count]j 向下跳转 [count] 行，默认跳转一行。
[count]k 向上跳转 [count] 行，默认跳转一行。
/ 开始搜索。按 <Esc> 退出。
gh 跳转到首页。
gb 跳转到博客首页。
gw 跳转到 Wiki 首页。
gt 跳转到我的 Twitter Profile 页。
gp 跳转到我的 Github Profile 页。
? 打开帮助。按 <Esc> 退出。