树型结构数据
开发中经常要对数据做一些处理，大多情况下数据是固定层级和结构的，但也有一些情况下数据的层级和结构是不固定的，比如文件目录、功能菜单、权限树等，这种结构的数据的处理需要涉及到树的遍历算法。
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)
总结
开发中偶尔会有一些层级和结构不固定的树型数据，需要对这些数据进行处理，对树型数据的处理建立在遍历的基础之上，遍历分为深度优先和广度优先两种，深度优先基于递归，代码直观但可能爆栈，只适用于层级较少的情况，广度优先需要结合一个队列，适应任意层级，但空间复杂度略高。对树型数据的过滤只需要在遍历的时候复制过滤后的数据，按照原有结构组合即可。
网友评论