JS树结构操作:查找、遍历、筛选、树结构和列表结构相互转换

[jiaoguanwen]

JS树结构操作:查找、遍历、筛选、树结构和列表结构相互转换

js树结构(为了更通用，根节点放在数组中)

const tree = [
  {
    v: '1',
    children: [
      { v: '1-1' },
      { v: '1-2' },
      { v: '1-3', children: [{ v: '1-3-1' }] },
    ],
  },
]

js树结构相关内容：1、遍历，2、树<->列表，3、筛选、查找

[jiaoguanwen]

遍历

遍历：深度（前序、后序，中序只在二叉树讨论）、广度 实现：深度（循环、递归）、广度（循环）

广度 广度循环

function treeForeach(tree, func) {
  let node, list = [...tree]
  while((node = list.shift())) {
    func(node)
    node.children && list.push(...node.children)
  }
}

深度 深度循环前序

function treeForeach(tree, func) {
  let node,
    list = [...tree]
  while ((node = list.shift())) {
    func(node)
    node.children && list.unshift(...node.children)
  }
}

深度循环后序

function treeForeach(tree, func) {
  let node,
    list = [...tree],
    i = 0
  while ((node = list[i])) {
    let childCount = node.children ? node.children.length : 0
    if (!childCount || node.children[childCount - 1] === list[i - 1]) {
      func(node)
      i++
    } else {
      list.splice(i, 0, ...node.children)
    }
  }
}

深度递归前序

function treeForeach(tree, func) {
  tree.forEach(node => {
    func(node)
    node.children && treeForeach(node.children, func)
  })
}

深度递归后序

function treeForeach(tree, func) {
  tree.forEach(node => {
    node.children && treeForeach(node.children, func)
    func(node)
  })
}

[jiaoguanwen]

转换

列表数据

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'
  }
]

列表 转 树

function listToTree(list) {
  let info = list.reduce(
    (map, node) => ((map[node.id] = node), (node.children = []), map),
    {}
  )
  return list.filter(node => {
    info[node.parentId] && info[node.parentId].children.push(node)
    return !node.parentId
  })
}

树 转 列表 递归

function treeToList(tree, result = [], level = 0) {
  tree.forEach(node => {
    result.push(node)
    node.level = level + 1
    node.children && treeToList(node.children, result, level + 1)
  })
  return result
}

循环

function treeToList(tree) {
  let result = tree.map(node => ((node.level = 1), node))
  for (let i = 0; i < result.length; i++) {
    console.log(result.length)
    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
}

[jiaoguanwen]

查找

筛选

function treeFilter(tree, func) {
  return tree
    .map(node => ({ ...node }))
    .filter(node => {
      node.children = node.children && treeFilter(node.children, func)
      return func(node) || (node.children && node.children.length)
    })
}

查找

function treeFind(tree, func) {
  for (const data of tree) {
    if (func(data)) return data
    if (data.children) {
      const res = treeFind(data.children, func)
      if (res) return res
    }
  }
  return null
}

查找节点路径

function treeFindPath(tree, func, path = []) {
  if (!tree) return []
  for (const data of tree) {
    path.push(data.id)
    if (func(data)) return path
    if (data.children) {
      const findChild = treeFindPath(data.children, func, path)
      if (findChild.length) return findChild
    }
    path.pop()
  }
  return []
}

查找多条节点路径

function treeFindPath(tree, func, path = [], result = []) {
  for (const data of tree) {
    path.push(data.id)
    func(data) && result.push([...path])
    data.children && treeFindPath(data.children, func, path, result)
    path.pop()
  }
  return result
}