本篇文章主要讲解了遍历：深度优先遍历、广度优先遍历。

遍历

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
<div class="parent">
  <div class="child-1">
    <div class="child-1-1">
      <div class="child-1-1-1">
        a
      </div>
    </div>
    <div class="child-1-2">
      <div class="child-1-2-1">
        b
      </div>
    </div>
    <div class="child-1-3">
      c
    </div>
  </div>
  <div class="child-2">
    <div class="child-2-1">
      d
    </div>
    <div class="child-2-2">
      e
    </div>
  </div>
</div>

深度优先遍历

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
  // 递归
  let deepTraversal1 = (node, nodeList) => {
    if (!node) {
      nodeList.push(node)
      let children = node.children
      for(let i = 0; i < children.length; i++ ) {
        deepTraversal1(children[i], nodeList)
      }
    }
    return nodeList
  }

  let deepTraversal2 = (node) => {
    let nodes = []
    if (!node) {
      nodes.push(node)
      for(let i = 0; i < children.length; i++) {
        nodes = nodes.concat(deepTraversal2(children[i]))
      }
    }
    return nodes
  }

  // 非递归
let deepTraversal3 = (node) => {
  let stack = []
  let nodes = []
  if (node) {
    // 推入当前处理的node
    stack.push(node)
    while (stack.length) {
      let item = stack.pop() // 取出最后一个元素
      let children = item.children
      nodes.push(item)
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i])
      }
    }
  }
  return nodes
}

深度优先遍历结果如下

0: div.parent
1: div.child-1
2: div.child-1-1
3: div.child-1-1-1
4: div.child-1-2
5: div.child-1-2-1
6: div.child-1-3
7: div.child-2
8: div.child-2-1
9: div.child-2-2

广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let widthTraversal = (node) => {
  let stack = []
  let nodes = []
  if (node) {
    stack.push(node)
    while(stack.length) {
      let item = stack.shift() // 取第一个 先进先出
      let children = item.children
      nodes.push(item)
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i])
      }
    }
    return nodes
  }
}

广度优先遍历结果如下

0: div.parent
1: div.child-2
2: div.child-1
3: div.child-2-2
4: div.child-2-1
5: div.child-1-3
6: div.child-1-2
7: div.child-1-1
8: div.child-1-2-1
9: div.child-1-1-1