树的遍历

解决一个需求，前端做一个search功能

数据结构的话是树形数据，emmm，不只是单独的遍历，还需要找到搜索到节点的层次，并且进行拼接，拼接父级的name

大致的数据结构：

const arr=[ { name:'1',children:[{name:'2',children:null},{name:'3',children:[{name:'6',children:null}]}] }, {name:'4',children:[]}, {name:'5',children:[]} ] 

其实就是一个树的遍历 ， 不过有个问题需要去解决，就是拼接他的层级，

有两种解决方式，最先想到的自然是df，

我的解决思路是 额外的去维护一个栈，栈中缓存层级信息，不过递归的dfs在时间与空间上都不太行，放弃了这种做法

这里使用迭代的bfs，也就是广度优先遍历

export function preorderTraversal <T extends {[key: string]: any}>(
  tree: Array<T>,
  target: string,
  name: keyof T = 'title' as string,//对比的字段
  childrenName: keyof T = 'components' as string//子节点
): Array<T>{
  //bfs 在队列节点中记录下层级信息
  const stack: (T | string)[][] =[[...tree,'']]
  //返回的数据
  const res: Array<T> = []
  //队列为空则遍历完毕
  while (stack.length > 0)
  {
    const node = stack.shift() as T[]

    for(let i=0; i<node?.length-1; i++)
    {
      if(node[i]?.[name]?.includes?.(target))
        res.push({...node?.[i],level:node[node?.length-1]})

      if(!isNil(node[i]?.[childrenName]) && node[i]?.[childrenName].length > 0)
      {
        const parentLevel= node[node.length-1]
        const level =parentLevel ? `${parentLevel}/${node[i]?.[name]}` : node[i]?.[name]
        stack.push([...node[i]?.[childrenName],level])
      }
    }
  }
  return res
}