JS实现树的几种遍历方式

树结构在前端中是很常见的，比如 Dom 树， JS原型链

当利用选择器 document.getElementById()，document.getElementsByName()去查找节点时，就涉及到了树的遍历查找问题

假设我们代码里 dom 结构如下

<div id="root">
  <ul>
    <li>
      <a href="">
        <img src="" alt="" />
      </a>
    </li>
    <li>
      <span></span>
    </li>
    <li></li>
  </ul>
  <p></p>
  <button></button>
</div>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这个 dom 结构转化成树后

现在我们的需求是需要找出 img 标签

通过实现这个需求，让我们看一下树的遍历

# 抽象 dom 树

节点对象

为了简化，这里忽略 src alt 等属性

为了便于追踪遍历顺序我们添加 id 属性

const node = {
  tag: 'div',
  id: 'root',
  children: []
}

1
2
3
4
5

抽象后树转换为了

const tree = {
  tag: 'div',
  id: 'root',
  children: [
    {
      tag: 'ul',
      id: 'ul',
      children: [
        {
          tag: 'li',
          id: 'li-1',
          children: [
            {
              tag: 'a',
              id: 'a',
              children: [
                {
                  tag: 'img',
                  id: 'img-1',
                  children: []
                }
              ]
            }
          ]
        },
        {
          tag: 'li',
          id: 'li-2',
          children: [
            {
              tag: 'span',
              id: 'span',
              children: [
                {
                  tag: 'img',
                  id: 'img-2',
                  children: []
                }
              ]
            }
          ]
        },
        {
          tag: 'li',
          id: 'li-3',
          children: []
        }
      ]
    },
    {
      tag: 'p',
      id: 'p',
      children: []
    },
    {
      tag: 'button',
      id: 'button',
      children: []
    }
  ]
}

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

现在树已经转换为了 ‘虚拟 dom’ 了，我们来找 img 标签吧

# 广度优先遍历（breadth-first traverse）

广度优先遍历是以横向的维度对 dom 树进行遍历，从该节点的第一个子节点开始，遍历其所有的兄弟节点，再遍历第一个节点的子节点，完成该遍历之后，暂时不深入，开始遍历其兄弟节点的子节点。

function breadthFirstSearch(nodes, target, result = []) {
  nodes.forEach((n) => {
    console.log(n.id)
    if (n.tag === target) {
      result.push(n)
    }
  })
  nodes.forEach((n) => {
    if (n.children && n.children.length) {
      breadthFirstSearch(n.children, target, result)
    }
  })
  return result
}
breadthFirstSearch([tree])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

执行后控制台打印

可以看出遍历顺序是一层一层进行的

# 深度优先遍历（Depth-First Search）

深度优先遍历是以纵向的维度对 dom 树进行遍历，从一个 dom 节点开始，一直遍历其子节点，直到它的所有子节点都被遍历完毕之后在遍历它的兄弟节点。

function depthFirstSearch(node, target, result = []) {
  console.log(node.id)
  if (node.tag === target) {
    result.push(node)
  }
  if (node.children && node.children.length) {
    node.children.forEach((n) => {
      depthFirstSearch(n, target, result)
    })
  }
  return result
}

1
2
3
4
5
6
7
8
9
10
11
12

控制台输出

这里可以观察到遍历顺序是先父节点再到子节点从左到右依次遍历

这种深度遍历方式也称为 中序遍历

还有一种常用的方式为 先序遍历，对上面的代码稍做修改

function depthFirstSearch(node, target, result = []) {
  if (node.children && node.children.length) {
    node.children.forEach((n) => {
      depthFirstSearch(n, target, result)
    })
  }
  console.log(node.id)
  if (node.tag === target) {
    result.push(node)
  }
  return result
}
depthFirstSearch(tree)

1
2
3
4
5
6
7
8
9
10
11
12
13

控制台输出

可以看到先访问了最深层的 img-1 标签，然后再依次往上遍历

也就是先序遍历最先访问最深层的最左侧的节点

#算法

上次更新: 2023/04/05, 09:41:10

← JS实现队列二叉树相关→