砥砺前行

要遍历的树结构如下：

const data = [{
    label: 'parent',
    children: [
        {
            label: '一级 1',
            children: [{
              label: '二级 1-1',
              children: [{
                label: '三级 1-1-1'
              }]
            }]
          }, {
            label: '一级 2',
            children: [{
              label: '二级 2-1',
              children: [{
                label: '三级 2-1-1'
              }]
            }, {
              label: '二级 2-2',
              children: [{
                label: '三级 2-2-1'
              }]
            }]
          }, {
            label: '一级 3',
            children: [{
              label: '二级 3-1',
              children: [{
                label: '三级 3-1-1'
              }]
            }, {
              label: '二级 3-2',
              children: [{
                label: '三级 3-2-1'
              }]
            }]
        }
    ]
}];
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

实现基本原理：递归。

递归实现

// 递归实现
const deepTraversal = ((node, nodeList = []) => {
    if (node.length) {
        for (let i = 0; i < node.length; i++) {
            const {label, children} = node[i];
            nodeList.push(label);
            if (children && children.length) {
                deepTraversal(children, nodeList);
            }
        }
    }
    return nodeList;
});
const result = deepTraversal(data);
console.log(result);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

输出结果如下：

[ 'parent',
  '一级 1',
  '二级 1-1',
  '三级 1-1-1',
  '一级 2',
  '二级 2-1',
  '三级 2-1-1',
  '二级 2-2',
  '三级 2-2-1',
  '一级 3',
  '二级 3-1',
  '三级 3-1-1',
  '二级 3-2',
  '三级 3-2-1' ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

基于栈实现

const deepTraversal = ((node, nodeList = []) => {
    const stack = [];
    if (node.length) {
        stack.push(node[0]);
        while (stack.length) {
            const item = stack.pop();
            nodeList.push(item.label);
            console.log(item);
            if (item.children) {
                const children = item.children;
                for (let i = children.length - 1; i >= 0; i--) {
                    stack.push(children[i]);
                }
            }
        }
    }
    return nodeList;
});
const result = deepTraversal(data);
console.log(result);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

实现原理：队列。

const bfsTraversal = ((node, nodeList = []) => {
    const queue = []; // 基于队列的先进先出
    if (node.length) {
        queue.push(node[0]);
        while (queue.length) {
            const item = queue.shift();
            nodeList.push(item.label);
            if (item.children) {
                const children = item.children;
                for (let j = 0; j < children.length; j++) {
                    queue.push(children[j]);
                }
            }
        }
    }
    return nodeList;
});
const result = bfsTraversal(data);
console.log(result);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

输出结果如下：

[ 'parent',
  '一级 1',
  '一级 2',
  '一级 3',
  '二级 1-1',
  '二级 2-1',
  '二级 2-2',
  '二级 3-1',
  '二级 3-2',
  '三级 1-1-1',
  '三级 2-1-1',
  '三级 2-2-1',
  '三级 3-1-1',
  '三级 3-2-1' ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

深度优先搜索

深度优先搜索（depth first search），从图中也可以看出来，是从根节点开始，沿树的深度进行搜索，尽可能深的搜索分支。当节点所在的边都已经搜多过，则回溯到上一个节点，再搜索其余的边。

深度优先搜索采用栈结构，后进先出。 该算法先将当前结点的孩子全部遍历结束，再遍历同一级的节点。

递归实现

<body>
    <div id='root'>
        <span>123
            <a href="#">
                sdsd
            </a>
            <div>sdsd<a>这是一个a标签</a></div>
        </span>
        <span>456
            <p>
                这是一个p标签
                <span>123</span>
            </p>
        </span>
    </div>
</body>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function deepTraversal(node, nodeList) {
    if (node) {
            nodeList.push(node);
            var children = node.children;
            for (var i = 0; i < children.length; i++) {
                // 每次递归的时候将需要遍历的节点和存储节点的数组传下去
                deepTraversal(children[i], nodeList);
            }
        }
    return nodeList;
}
const root = document.getElementById('root');
console.log(deepTraversal(root, nodeList=[]));
1
2
3
4
5
6
7
8
9
10
11
12
13

非递归实现

function deepTraversal(node) {
    var nodeList = [];
    if (node) {
        var stack = [];
        stack.push(node);
        while (stack.length != 0) {
            var childrenItem = stack.pop();
            nodeList.push(childrenItem);
            var childrenList = childrenItem.children;
            for (var i = childrenList.length - 1; i >= 0; i--)
                stack.push(childrenList[i]);
        }
    }
    return nodeList;
}
var root = document.getElementById('root')
console.log(deepTraversal(root))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

广度优先

当使用广度优先遍历的时候，先依次遍历兄弟节点，然后遍历兄弟节点下的子节点。 广度优先遍历二叉树，也就是按层次的去遍历。依次遍历根节点，然后是左孩子和右孩子。所以要遍历完当前节点的所有孩子。根据左右孩子的顺序来输出，所以就是先进先出的原则，那么我们当然就想到了队列这个数据结构：

非递归实现

function wideTraversal(node) {
    var nodes = [];
    if (node != null) {
        var queue = [];
        queue.unshift(node);
        while (queue.length != 0) {
            var item = queue.shift();
            nodes.push(item);
            var children = item.children;
            for (var i = 0; i < children.length; i++)
                queue.push(children[i]);
        }
    }
    return nodes;
}
const root = document.getElementById('root');
console.log(wideTraversal(root));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

参考文档

  1. 广度/深度优先搜索
  2. 介绍下深度优先遍历和广度优先遍历，如何实现？

← 3. 排序二叉树→