js算法的深度优先遍历和广度优先遍历_js 深度优先遍历

深度优先遍历实现方式1

//深度优先遍历方法
let tree =  {
    id: '1',
    title: '节点1',
    children: [
      {
        id: '1-1',
        title: '节点1-1'
      },
      {
        id: '1-2',
        title: '节点1-2',
        children: [{
          id: '2',
          title: '节点2',
          children: [
            {
              id: '2-1',
              title: '节点2-1'
            }
          ]
        }]
      }
    ]
  }
  //主要级就是当前节点遍历完，然后再去遍历兄弟节点这样的顺序
let deepTraversal1 = (node, nodeList = []) => {
    if (node !== null) {
      nodeList.push(node.id)
      if(node.children && node.children.length>0){
        let children = node.children
        for (let i = 0; i < children.length; i++) {
          deepTraversal1(children[i], nodeList)
        }
      }
    }
    return nodeList
}
console.log(deepTraversal1(tree))
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

深度优先遍历实现方式2

//深度优先遍历方法
let tree =  {
    id: '1',
    title: '节点1',
    children: [
      {
        id: '1-1',
        title: '节点1-1'
      },
      {
        id: '1-2',
        title: '节点1-2',
        children: [{
          id: '2',
          title: '节点2',
          children: [
            {
              id: '2-1',
              title: '节点2-1'
            }
          ]
        }]
      }
    ]
  }
  
  let deepTraversal2 = (node) => {
    let nodes = []
    if (node !== null) {
      nodes.push(node.id)
      if(node.children && node.children.length>0){
        let children = node.children
        for (let i = 0; i < children.length; i++) {
          nodes = nodes.concat(deepTraversal2(children[i]))
        }
      }
    }
    return nodes
  }

console.log(deepTraversal2(tree))
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

深度优先遍历实现方式3 ,非递归的方式

//深度优先遍历方法

let tree =  {
    id: '1',
    title: '节点1',
    children: [
      {
        id: '1-1',
        title: '节点1-1'
      },
      {
        id: '1-2',
        title: '节点1-2',
        children: [{
          id: '2',
          title: '节点2',
          children: [
            {
              id: '2-1',
              title: '节点2-1'
            }
          ]
        }]
      }
    ]
  }
  
  let widthTraversal3 = (node) => {
    let nodes = []
    let stack = []

    if(node){
      stack.push(node)
      while(stack.length){
        let item = stack.shift()
        let children = item.children
        nodes.push(item.id)
        if(children){
           for(var i=0;i<children.length;i++){
            stack.push(children[i])
           }
        }
      }
    }

    return nodes
  }

console.log(widthTraversal3(tree))
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

广度优先搜索

let tree = [
    {
      id: '1',
      title: '节点1',
      children: [
        {
          id: '1-1',
          title: '节点1-1'
        },
        {
          id: '1-2',
          title: '节点1-2'
        }
      ]
    },
    {
      id: '2',
      title: '节点2',
      children: [
        {
          id: '2-1',
          title: '节点2-1'
        }
      ]
    }
  ]


function treeForeach(tree,func){
  let node,list = [...tree]
  while(node = list.shift()){
    func(node)
    node.children && list.push(...node.children)
  }
}

treeForeach(tree,node => console.log(node.title))
console.log(tree);
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

几种使用方法主要是树结构的数据处理时候用。