树形结构操作合集

let tree = [
  {
    id: '1',
    title: '节点1',
    children: [
      { id: '1-1', title: '节点1-1' },
      { id: '1-2', title: '节点1-2' },
    ],
  },
  {
    id: '2',
    title: '节点2',
    children: [
      {
        id: '2-1',
        title: '节点2-1',
        children: [{ id: '2-1-1', title: '节点2-1-1', parentId: '2-1' }],
      },
    ],
  },
]
let list = [
  { id: '1', title: '节点1', parentId: '' },
  { id: '1-1', title: '节点1-1', parentId: '1' },
  { id: '1-2', title: '节点1-2', parentId: '1' },
  { id: '2', title: '节点2', parentId: '' },
  { id: '2-1', title: '节点2-1', parentId: '2' },
  { id: '2-1-1', title: '节点2-1-1', parentId: '2-1' },
]

一、遍历

1. 广度优先

/** 循环实现
 *	思路：维护一个队列，队列的初始值为树结构根节点组成的列表，重复执行以下步骤直到队列为空：
 *	取出队列中的第一个元素，进行访问相关操作，然后将其后代元素（如果有）全部追加到队列最后。
 */
const forEachTree = (tree, fn) => {
  let node,
    data = [...tree]
  while ((node = data.shift())) {
    fn(node)
    node.children && data.push(...node.children)
  }
}
var res = forEachTree(tree, (node) => console.log(node.id))
// 输出：
1
2
1 - 1
1 - 2
2 - 1
2 - 1 - 1

2. 深度优先

• 先序遍历

// 递归实现
const forEachTree = (tree, fn) => {
  tree.forEach((item) => {
    fn(item)
    item.children && forEachTree(item.children, fn)
  })
}

/**
 * 循环实现
 * 与广度优先类似，只是将自己unshift到数组前面。
 */
const forEachTree = (tree, fn) => {
  let node,
    data = [...tree]
  while ((node = data.shift())) {
    fn(node)
    node.children && data.unshift(...node.children)
  }
}

var res = forEachTree(tree, (node) => console.log(node.id))
// 输出：
1
1 - 1
1 - 2
2
2 - 1
2 - 1 - 1

• 后序遍历

// 递归实现
const forEachTree = (tree, fn) => {
  tree.forEach((item) => {
    item.children && forEachTree(item.children, fn)
    fn(item)
  })
}
var res = forEachTree(tree, (node) => console.log(node.id))
// 输出
1 - 1
1 - 2
1
2 - 1 - 1
2 - 1
2

3. 返回新树

const forEachTree = (tree, newTree = []) => {
  tree.map((k, v) => {
    let node = {
      ...k,
    }
    if (k?.children?.length) {
      node.children = []
      forEachTree(k.children, node.children)
    }
    newTree.push(node)
  })
  return newTree
}

二、树与列表转换

1. 树转表

// 循环实现 利用(广度||深度)优先遍历，为子级添加level以及parentId。
const treeTolist = tree => {
  let node, list = []
 	while(node = tree.shift()) {
    node.level = node.level || 0
    list.push(node)
    node.children && tree.push(...node.children.map(item => ({...item, parentId: node.id, level: node.level + 1})))
 }
 return list
}
// 循环实现2  思路与1并无二致，更加接地气罢了
const treeTolist = tree =>  {
  let  result = tree.map(node => (node.level = 0, node))
  for (let i = 0; i < result.length; i++) {
    if (!result[i].children) continue
    let list = result[i].children.map(node => (node.level = result[i].level + 1, node))
    result.splice(i+1, 0, ...list)
  }
  return result
}

// 递归实现
const treeTolist = (tree, result = [], level = 0) => {
  for (let node of tree) {
    node.level = level
    result.push(node)
    node.children && treeTolist(node.children.map(item => ({...item, parentId: node.id })), result, level + 1)
  }
  return result
}

var res = treeTolist(tree)
console.log(res, 'res')
// 输出
0: {id: "1", title: "节点1", children: Array(2), level: 0}
1: {id: "1-1", title: "节点1-1", parentId: "1", level: 1}
2: {id: "1-2", title: "节点1-2", parentId: "1", level: 1}
3: {id: "2", title: "节点2", children: Array(1), level: 0}
4: {id: "2-1", title: "节点2-1", children: Array(1), parentId: "2", level: 1}
5: {id: "2-1-1", title: "节点2-1-1", parentId: "2-1", level: 2}

2. 表转树

// 列表结构转为树结构，就是把所有非根节点放到对应父节点的chilren数组中，然后把根节点提取出来：
const listTotree = (list) => {
  const info = list.reduce((map, node) => ((map[node.id] = node), (node.children = []), map), {})
  return list.filter((node) => {
    node.parentId && info[node.parentId].children.push(node)
    return !node.parentId
  })
}

var res = listTotree(list)

//方法2 双重循环
const listTotree = (list) => {
  const newList = list.slice(0)
  newList.forEach((item) => {
    const parentId = item.parentId
    parentId &&
      newList.forEach((key) => {
        if (key.id === parentId) {
          key.children = key.children || []
          key.children.push(item)
        }
      })
  })
  return newList.filter((item) => !item.parentId)
}

三、树结构查找

节点查找

• 单节点

// 循环实现
const nodeSeek = (tree, fn) => {
  let node, data = [...tree]
  while(node = data.shift()){
  	if (fn(node)) return node
    node.children && data.unshift(...node.children)
  }
  return null
}

// 递归实现
const nodeSeek = (tree, fn) => {
  for (let node of tree){
  	if (fn(node)) return node
    if (node.children) {
    	const res = nodeSeek(node.children, fn)
      if (res) return res
    }
  }
  return null
}

// 递归实现2 借助扁平化
 const nodeSeek = (tree, fn) => {
   const flatten = arr => {
     //  eslint-disable-next-line
     return arr.reduce((res, next) => (res = res.concat(Array.isArray(next.children) ? flatten(next.children) : next), res), [])

     // return arr.reduce((res, next) => {
     //   return res.concat(Array.isArray(next.children) ? flatten(next.children) : next)
     // }, [])
   }
   return flatten(tree).find(fn)
 }

var res = nodeSeek(tree, (node) => node.id === '2-1')
console.log(res, 'res')

// 输出
{
  children: [{…}],
  id: "2-1",
  title: "节点2-1",
}

• 多节点

const nodeSeek = (tree, fn, result = []) => {
  let node,
    data = [...tree]
  while ((node = data.shift())) {
    if (fn(node)) result.push(node)
    node.children && data.unshift(...node.children)
  }
  return result
}

var res = nodeSeek(tree, (node) => node.id === '2-1' || node.id === '1-1')
console.log(res, 'res')[
  // 输出：
  ({ id: '1-1', title: '节点1-1' }, { id: '2-1', title: '节点2-1', children: Array(1) })
]

单路径查找

const treePath = (tree, fn, path = []) => {
  for (let data of tree) {
    path.push(data.id)
    if (fn(data)) return path
    if (data.children) {
      const res = treePath(data.children, fn, path)
      if (res) return res
    }
    path.pop()
  }
  return null
}

let result = treePath(tree, (node) => node.id === '2-1-1')
console.log(result) // ["2", "2-1", "2-1-1"]

多路径查找

const treePath = (tree, fn, path = [], result = []) => {
  for (let node of tree) {
    path.push(node.id)
    fn(node) && result.push([...path])
    node.children && treePath(node.children, fn, path, result)
    path.pop()
  }
  return result
}
console.log(treePath(tree, (node) => node.id === '2-1-1' || node.id === '2-1'))[
  // 输出
  (['2', '2-1'], ['2', '2-1', '2-1-1'])
]

四、树结构裁剪

树结构过滤即保留某些符合条件的节点，剪裁掉其它节点。一个节点是否保留在过滤后的树结构中，取决于它以及后代节点中是否有符合条件的节点。可以传入一个函数描述符合条件的节点:

const treeFilter = (tree, func) =>{
  return tree.filter(node => {
    node.children = node.children && treeFilter(node.children, func)
    return func(node) || (node.children && node.children.length)
  })
}
var res = treeFilter(tree, (node) => node.id === '2-1')
console.log(res, 'res')
// 输出
[{
  id: "2"
  title: "节点2",
  children: [{
    id: "2-1"
    title: "节点2-1"
  }]
}]

五、关键字过滤

const filterTree = (val, tree, newArr = []) => {
  if (!(tree.length && val)) {
    // 如果搜索关键字为空直接返回源数据
    return tree
  }
  for (let item of tree) {
    if (item.title.indexOf(val) > -1) {
      // 匹配到关键字的逻辑
      newArr.push(item) // 如果匹配到就在数值中添加记录
      continue // 匹配到了就退出循环了此时如果有子集也会一并带着
    }
    if (item.children && item.children.length) {
      // 如果父级节点没有匹配到就看看是否有子集，然后做递归
      let subArr = filterTree(val, item.children) // 缓存递归后的子集数组
      if (subArr && subArr.length) {
        // 如果子集数据有匹配到的节点
        let node = { ...item, children: subArr } // 关键逻辑，缓存父节点同时将递归后的子节点作为新值
        newArr.push(node) // 添加进数组
      }
    }
  }
  return newArr
}

// https://www.jianshu.com/p/023e5212f53a