深度优先和广度优先遍历DOM树

发表于 | 分类于 |

前言

最近在看一些关于算法的知识,顺便也用js写了写,好在以前马马虎虎看过算法导论之类之类的书。看到二叉树的遍历后又联想到DOM树,所以试着写了一些代码,权当笔记,供自己参考。

概念

DOM树的遍历可谓老生常谈了,自定义实现getElementById或者getElementByClassName等方法都需要遍历DOM,当然后来我知道了浏览器是用hash table存储id并映射到DOM的。深度优先、广度优先的概念维基百科上都有,不做解释了。
拿以下DOM树举例说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<body>
    <div class="wrapper">
        <section class="header">
            <div class="logo"></div>
        </section>
        <section class="main">
            <div class="sidebar">
                <ul class="menu">
                    <li>
                        <a href=""></a>
                    </li>
                    <li>
                        <a href=""></a>
                    </li>
                </ul>
            </div>
        </section>
        <section class="footer">
            <div class="copyright"></div>
        </section>
    </div>
</body>

1、如果按照广度优先遍历输出结果为:

1
2
3
4
5
6
7
8
9
10
11
12
13
<body>​…​</body>​
<div class=​"wrapper">​…​</div>​
<section class=​"header">​…​</section>​
<section class=​"main">​…​</section>​
<section class=​"footer">​…​</section>​
<div class=​"logo">​</div>​
<div class=​"sidebar">​…​</div>​
<div class=​"copyright">​</div>​
<ul class=​"menu">​…​</ul>​
<li>​…​</li>​
<li>​…​</li>​
<a href>​</a>​
<a href>​</a>​

2、如果按照深度优先遍历出结果为:

1
2
3
4
5
6
7
8
9
10
11
12
13
<body>​…​</body>​
<div class=​"wrapper">​…​</div>​
<section class=​"header">​…​</section>​
<div class=​"logo">​</div>​
<section class=​"main">​…​</section>​
<div class=​"sidebar">​…​</div>​
<ul class=​"menu">​…​</ul>​
<li>​…​</li>​
<a href>​</a>​
<li>​…​</li>​
<a href>​</a>​
<section class=​"footer">​…​</section>​
<div class=​"copyright">​</div>​

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 广度优先遍历
function traverseByBFS(domRoot){
    var queue = [domRoot];
    while(queue.length) {
		var node = queue.shift();
        console.log(node);
        if (!node.children.length) {
            continue;
        }
        Array.from(node.children).forEach(x => queue.push(x))
	}
}
traverseByBFS(document.body)  
// 深度优先遍历
function traverseByDFS(domRoot) {
    var child = domRoot.firstElementChild;
    while(child) {
        console.log(child);
		traverseByDFS(child);
        child = child.nextElementSibling;
    }
}
traverseByDFS(document.body)

延伸

计算给定DOM的最大深度

既然能够用两种方法遍历DOM,那么就应该应用到具体操作中去,比如获取一个dom节点的最大深度,用肉眼观察上面那段html代码可以得知算上body一共有7层。
废话不多说,上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 /**
 * 深度优先遍历计算给定DOM的最大深度,递归实现
 * 遍历children
 * @param domRoot
 * @returns {*}
 */
function getMaxDomTreeDepth_DFS(domRoot) {
    var childrenDepth = [],
        child = domRoot.firstElementChild;
    // 如果取不到第一个子节点,则返回1
    if (!child) return 1;
    while (child) {
        console.log(child)
        childrenDepth.push(getMaxDomTreeDepth_DFS(child));
        child = child.nextElementSibling;
    }
    return Math.max(...childrenDepth) + 1;
}
console.log(getMaxDomTreeDepth_DFS(document.body))
/**
 * 广度优先遍历计算给定DOM的最大深度,队列实现
 * 按层遍历
 * @param domRoot
 * @returns {number}
 */
function getMaxDomTreeDepth_BFS (domRoot){
    // 定义一个队列
    var queue = [domRoot];
    var domDepth = 0;
    while(queue.length) {
        ++domDepth;
        // 当前队列的长度
        var currentSize = queue.length;
        // 计数器
        var count = 0;
        while(count < currentSize) {
            ++count;
            // 出队第一个入队的element
            var node = queue.shift();
            if(!node.children.length){
                continue;
            }
            // 将子节点入队
            Array.from(node.children).forEach(x => queue.push(x))
        }
    }
    return domDepth;
}
console.log(getMaxDomTreeDepth_BFS(document.body))