javascript中采用深度优先和广度优先遍历DOM树算法_js 深度便利

何为深度优先遍历(DFS)和广度优先遍历(BFS)

深度优先遍历: 深度优先遍历就是找准一条路不停深入的搜索方法，当发现这条路走不通的时候就会回退到上一个探索的节点，如果上一个节点存在没有探索的分支，便继续探索若没有则继续回退。
广度优先遍历: 广度优先遍历（BFS），又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，将离根节点最近的节点先遍历出来，在继续深挖下去。

首先定义一个访问函数

		// 定义一个访问函数，输出访问到的节点
        function visitNode(node) {
            // 注释
            if (node instanceof Comment) {
                console.log("注释节点->", node.textContent);
            }
            // 文本
            if (node instanceof Text) {
                // 由于有的元素中没有文本节点也包含空串，并且空格也算上，因此这里做一下处理
                if (node.textContent.trim()) {
                    console.log("文本节点->", node.textContent.trim());
                }

            }
            // 元素节点
            if (node instanceof HTMLElement) {
                console.log("HTML元素节点->", `<${node.tagName.toLowerCase()}>`);
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

深度优先遍历（递归实现）

		// 定义深度优先遍历DOM树的方法 - 递归实现
        function dfs(root) {
            visitNode(root)
            // 获取所有的子节点
            // root.childNode获取所有子节点(包括注释节点，文本节点，HTML元素节点)
            // root.children获取所有HTML元素节点
            let childNodes = root.childNodes
            // 对每一个子节点都进行深度优先遍历
            if (childNodes.length) {
                childNodes.forEach((item) => {
                    dfs(item)
                })
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

深度优先遍历（非递归实现）

		// 定义深度优先遍历DOM树的方法 - 非递归实现(采用栈结构实现，递归本身就是栈结构实现的)
        function dfs1(root) {
            // 首先准备一个栈
            const stack = []
            // 根元素首先压栈
            stack.push(root)
            // 如果栈结构不为空，那就进入到while循环中
            while (stack.length) {
                // 首先弹栈，取出当前元素
                let curNode = stack.pop()
                // 判断弹出的元素为空吗，如果为空，那就终止一切吧
                if (curNode == null) break;
                visitNode(curNode)
                // 不为空，那就获取当前节点的所有子节点
                let childNodes = curNode.childNodes;
                // 遍历所有的子节点，压栈
                if (childNodes.length) {
                    Array.from(childNodes).reverse().forEach((item) => {
                        stack.push(item)
                    })
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

广度优先遍历

		//实现广度优先遍历
		function bfs(root) {
            // 准备一个队列(用数组模仿)
            const queue = []
            // 让根元素进队列吧
            queue.push(root)
            // 当队列不为空时
            while (queue.length) {
                // 取出队列头
                let curNode = queue.shift()
                // 判断取出的节点是否为空，若为空，跳出循环
                if (curNode == null) break;
                // 访问此节点
                visitNode(curNode)
                // 遍历当前结点的所有孩子节点,把所有的孩子节点都入队
                let childNodes = curNode.childNodes
                if (childNodes.length) {
                    childNodes.forEach((item) => {
                        queue.push(item)
                    })
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

检测dfs算法的正确性

这是html结构:

	<div class="box">
        <!-- 这是box内部 -->
        <div>
            <ul>
                <!-- 这是ul内部 -->
                <li>1-1</li>
                <li>1-2</li>
                <li>1-3</li>
            </ul>
        </div>
        <div>2</div>
        <div>3</div>
    </div>
1
2
3
4
5
6
7
8
9
10
11
12
13

这是js代码:

	dfs(document.querySelector(".box"))
1

这是输出结果:

检测bfs算法的正确性

这是html结构:

	<div class="box">
        <!-- 这是box内部 -->
        <div>
            <ul>
                <!-- 这是ul内部 -->
                <li>1-1</li>
                <li>1-2</li>
                <li>1-3</li>
            </ul>
        </div>
        <div>2</div>
        <div>3</div>
    </div>
1
2
3
4
5
6
7
8
9
10
11
12
13

这是js代码:

	bfs(document.querySelector(".box"))
1

这是输出结果:

Have a nice day!