树型结构数据
开发中经常要对数据做一些处理，大多情况下数据是固定层级和结构的，但也有一些情况下数据的层级和结构是不固定的，比如文件目录、功能菜单、权限树等，这种结构的数据的处理需要涉及到树的遍历算法。
const data = { name: 'all', children: [ { name: '图片', children: [ { name: 'image1.jpg' }, { name: '风景', children: [ { name: 'guilin.jpg' }, { name: 'hainan.jpg' } ] }, { name: 'image2.jpg' } ], }, { name: '视频', children: [ { name: 'video1.mp4' }, { name: 'video2.mp4' } ] }, { name: '文档', children: [ { name: 'document1.doc' }, { name: '小说', children: [ { name: 'novel.txt' }, { name: 'novel2.txt' } ] }, { name: 'document2.doc' } ] } ]}复制代码 树的遍历算法
树的遍历有深度优先和广度优先两种方式。深度优先遍历的形式是递归，优点是代码简洁直观，缺点是层级过深的时候可能会栈溢出，只适用于层级较少的情况，广度优先遍历的优点是不会栈溢出，适应任意层级深度，但缺点是需要引入一个队列来存储待遍历的节点，空间复杂度较高。
深度优先（dfs）
const dfs = (tree, ope) => { const walk = (tree, depth = 1) => { ope(tree.name, depth) if(tree.children) { tree.children.forEach((node) => { walk(node, depth + 1) }) } } walk(tree)}复制代码 测试：
dfs(data, (name, depth) => { let pre = ''; for(let i =0; i < depth; i++) { pre += '--' } console.log(pre + name)})复制代码 广度优先（bfs）
const bfs = (tree, ope) => { const walk = (tree, depth = 1) => { const queue = [] ope(tree.name, depth) if(tree.children){ queue.push({ nodes: tree.children, depth: depth + 1 }) } while(queue.length) { const item = queue.pop() item.nodes && item.nodes.forEach(node => { ope(node.name, item.depth) if(node.children) { queue.push({ nodes: node.children, depth: item.depth + 1 }) } }) } } walk(tree)}复制代码 测试：
bfs(data,(name, depth) => { let pre = ''; for(let i =0; i < depth; i++) { pre += '--' } console.log(pre + name)})复制代码 树型数据的过滤
很多情况下，我们不只需要遍历这棵树，可能还需要对这棵树进行一些过滤，返回过滤以后的数据，比如权限树的过滤、文件目录结构的过滤、功能菜单的过滤。大多数情况下过滤后的数据依然要保留树型结构。
其实，对树形结构的各种操作都是建立在遍历的基础之上，实现过滤的功能只需要在遍历的时候加一个判断，并且把符合条件的节点按照层级关系复制一份。
代码如下：
dfs-filter
const dfs = (tree, ope, filter) => { const walkAndCopy = (tree, depth = 1) => { if(filter(tree.name)) { const copy = {} ope(tree.name, depth) copy.name = tree.name if(tree.children) { copy.children = [] tree.children.forEach((node) => { const subTree = walkAndCopy(node, depth + 1) subTree && copy.children.push(subTree) }) } return copy } } return walkAndCopy(tree)}复制代码 测试代码（过滤掉所有名字中含有1的文件和目录）：
const copy = dfs(data,(name, depth) => {}, (name) => { return name.indexOf('1') === -1})console.log(copy)复制代码 bfs-filter
const bfs = (tree, ope, filter) => { const walkAndCopy = (tree, depth = 1) => { const queue = [] if (filter(tree.name)) { const copy = {} ope(tree.name, depth) copy.name = tree.name if(tree.children){ copy.children = [] queue.push({ nodes: tree.children, depth: depth + 1, copyNodes: copy.children }) } while(queue.length) { const item = queue.pop() item.nodes && item.nodes.forEach(node => { if(filter(node.name)) { const copyNode = {} ope(node.name, item.depth) copyNode.name = node.name if(node.children) { copyNode.children = [] queue.push({ nodes: node.children, depth: item.depth + 1, copyNodes: copyNode.children }) } item.copyNodes.push(copyNode) } }) } return copy } } return walkAndCopy(tree)}复制代码 测试代码（过滤掉所有名字中含有1的文件和目录）：
const copy = bfs(data,(name, depth) => {}, (name) => { return name.indexOf('1') === -1})console.log(copy)复制代码 总结
开发中偶尔会有一些层级和结构不固定的树型数据，需要对这些数据进行处理，对树型数据的处理建立在遍历的基础之上，遍历分为深度优先和广度优先两种，深度优先基于递归，代码直观但可能爆栈，只适用于层级较少的情况，广度优先需要结合一个队列，适应任意层级，但空间复杂度略高。对树型数据的过滤只需要在遍历的时候复制过滤后的数据，按照原有结构组合即可。