用生命谱写代码的赞歌

0%

深度优先遍历与广度优先遍历

Posted on Edited on In
如果要对 DOM 树或者其他树形结构的数据进行遍历，通常有两种方式。一种是深度优先遍历，另一种是广度优先遍历。

DOM 树结构

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>DOM 树结构遍历</title>
</head>

<body>
  <div id="parent">
    <div class="child-1">
      <div class="child-1-1">
        <div class="child-1-1-1">111</div>
      </div>
      <div class="child-1-2">
        <div class="child-1-2-1">
          <div class="child-1-2-1-1">1211</div>
          <div class="child-1-2-1-2">1212</div>
        </div>
      </div>
    </div>
    <div class="child-2">
      <div class="child-2-1">21</div>
    </div>
    <div class="child-3">
      <div class="child-3-1">31</div>
      <div class="child-3-2">
        <div class="child-3-2-1">321</div>
        <div class="child-3-2-2">322</div>
      </div>
    </div>
  </div>
  <div id="father"></div>
  <script>
    // 深度优先遍历
    let deepTraversal = (node, nodeList = []) => {
      if (node) {
        nodeList.push(node)
        let children = node.children
        for (let i = 0; i < children.length; i++) {
          deepTraversal(children[i], nodeList)
        }
      }
      return nodeList
    }

    console.log(deepTraversal(document.getElementById('parent')))

    // 广度优先遍历
    let widthTraversal = (node, nodeList = [], stack = []) => {
      if (node) {
        stack.push(node)
        while (stack.length) {
          const item = stack.shift()
          nodeList.push(item)
          const children = item.children
          for (let i = 0; i < children.length; i++) {
            stack.push(children[i])
          }
        }
      }
      return nodeList
    }

    console.log(widthTraversal(document.getElementById('parent')))
  </script>
</body>

</html>

深度优先遍历

即纵向遍历，遍历完父节点之后，开始遍历第一个子节点，然后遍历第一个子节点下面的所有子节点，再遍历第二个子节点，然后遍历第二个子节点下面的所有子节点，以此类推，先纵向遍历，再横向遍历。

广度优先遍历

即横向遍历，遍历完父节点之后，开始遍历第一个子节点，第二个子节点，第三个子节点……直到把父元素下面的子节点都遍历完成之后，再开始遍历第一个元素下面的子节点，第二个元素下面的子节点，第三个元素下面的子节点，以此类推，直到遍历完所有元素。

总结

  1. 深度优先遍历实现原理

    1. 将当前 node 节点 push 到数组
    2. 轮询当前节点的子节点，将每一个子节点作为当前节点重复步骤1(递归进行)

  2. 广度优先遍历实现原理

    1. 将父元素(rootNode) push 到栈(stack)之后
    2. 只要栈中还有数据，删除栈中第一个元素(rootNode)，同时 push 到累计数组 nodeList 中
    3. 获取删除元素的子元素(rootNode.children)也 push 到栈中
    4. 重复步骤2、3