Javascriptarraytotreetree遍历和过滤（任意层级）array 转 tree（⼴度优先）
function array2tree(array){
filter过滤对象数组
const newList =[]
for(let i =0; i < array.length; i++){
if(array[i][pid]===0){//获取最顶层元素，它的⽗节点ID=0
newList.push(array[i])
}else{
const parent = array.find(item => item[id]=== array[i][pid])// 获取当前节点的⽗节点
if(parent){
// 把当前节点加⼊到⽗节点中
if(parent.children){
parent.children.push(array[i])
}else{
parent.children =[array[i]]
}
}
}
}
return newList
}
树形结构数据
开发中经常要对数据做⼀些处理，⼤多情况下数据是固定层级和结构的，
但也有⼀些情况下数据的层级和结构是不固定的，⽐如⽂件⽬录、功能菜单、权限树等，
这种结构的数据的处理需要涉及到树的遍历算法。
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:''
},
{
name:''
}
]
},
{
name:'document2.doc'
}
]
}
]
}
树的遍历算法
树的遍历有深度优先和⼴度优先两种⽅式。
深度优先遍历的形式是递归：
优点是代码简洁直观，
缺点是层级过深的时候可能会栈溢出，只适⽤于层级较少的情况；⼴度优先遍历：
优点是不会栈溢出，适应任意层级深度，
但缺点是需要引⼊⼀个队列来存储待遍历的节点，空间复杂度较⾼。
深度优先（dfs）
//深度优先（递归）
// ope() ：是对每⼀个元素做附加操作的
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）
//⼴度优先（使⽤队列存储⼦节点）
// ope() ：是对每⼀个元素做附加操作的
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()
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）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。