getByElementId的实现

DOM树。 由于DOM是一棵树，而树的定义本身就是用的递归定义，所以用递归的方法处理树，会非常地简单自然。例如用递归实现一个查DOM的功能document.getElementById。

function getElementById(node, id){
    if(!node) return null;
    if(node.id === id) return node;
    for(var i = 0; i < node.childNodes.length; i++){
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}
getElementById(document, "d-cal");

document是DOM树的根结点，一般从document开始往下找。在for循环里面先找document的所有子结点，对所有子结点递归查找他们的子结点，一层一层地往下查找。如果已经到了叶子结点了还没有找到，则在第二行代码的判断里面返回null，返回之后for循环的i加1，继续下一个子结点。如果当前结点的id符合查找条件，则一层层地返回。所以这是一个深度优先的遍历，每次都先从根结点一直往下直到叶子结点，再从下往上返回。 最后在控制台验证一下，使用递归的优点是代码简单易懂，缺点是效率比不上非递归的实现。Chrome浏览器的查DOM是使用非递归实现。非递归要怎么实现呢？ 如下代码：

function getByElementId(node, id){
    //遍历所有的Node
    while(node){
        if(node.id === id) return node;
        node = nextElement(node);
    }
    return null;
}

还是依次遍历所有的DOM结点，只是这一次改成一个while循环，函数nextElement负责找到下一个结点。所以关键在于这个nextElement如何非递归实现，如下代码所示：

function nextElement(node){
    if(node.children.length) {
        return node.children[0];
    }
    if(node.nextElementSibling){
        return node.nextElementSibling;
    }
    while(node.parentNode){
        if(node.parentNode.nextElementSibling) {
            return node.parentNode.nextElementSibling;
        }
        node = node.parentNode;
    }
    return null;
}

还是用深度遍历，先找当前结点的子结点，如果它有子结点，则下一个元素就是它的第一个子结点，否则判断它是否有相邻元素，如果有则返回它的下一个相邻元素。如果它既没有子结点，也没有下一个相邻元素，则要往上返回它的父结点的下一个相邻元素，相当于上面递归实现里面的for循环的i加1. 在控制台里面运行这段代码，同样也可以正确地输出结果。不管是非递归还是递归，它们都是深度优先遍历.

实际上getElementById浏览器是用的一个哈希map存储的，根据id直接映射到DOM结点，而getElementsByClassName就是用的这样的非递归查找。