在 Javascript 的嵌套对象数组中查找目标对象的路径

Question

我目前正在解决一个问题，即我无法确定我需要在对象数组中的何处找到子节点。目标可以深入一层或多层。

问题是，一旦找到对象，我还需要将到达该对象的路径推送到生成的数据数组中。

目前我已经写过可以成功找到子节点的代码：

const buildFullTree = (tree, cat, data = []) => {
  let collection = [tree]

  while (collection.length) {
    let node = collection.shift()

    if (node.id === cat.id) {
      data.push(node)
    }

    collection.unshift(...node.children)
  }

  return data
}

但是，就获取到该对象的路径而言，这还不够。

我很确定我需要将其更改为递归深度优先搜索解决方案以实现我正在寻找的内容，但我不确定如何更改 while 循环来完成此操作。

Answer 1

如果我对你的问题理解正确，那么也许你可以像这样修改你的路径搜索功能来实现你的要求：

const buildFullTree = (departmentTree, category, data = []) => {

  const findPath = (node, category) => {

    //If current node matches search node, return tail of path result
    if (node.id === category.id) {
      return [node]

    } else {

      //If current node not search node match, examine children. For first 
      //child that returns an array (path), prepend current node to that 
      //path result
      for (const child of node.children) {
        const childPath = findPath(child, category)
        if (Array.isArray(childPath)) {
          childPath.unshift(child)
          return childPath
        }
      }
    }
  }

  const foundPath = findPath(departmentTree, category)

  // If search from root returns a path, prepend root node to path in
  // data result
  if (Array.isArray(foundPath)) {
    data.push(departmentTree)
    data.push(...foundPath)
  }

  return data
}

const departmentTree = {
  id: 5,
  title: 'department',
  level: 1,
  children: [{
    id: 1,
    parentId: 5,
    title: 'category',
    level: 2,
    children: [{
      id: 15,
      parentId: 1,
      title: 'subcategory',
      level: 3,
      children: []
    }, {
      id: 18,
      parentId: 1,
      level: 3,
      title: 'subcategory',
      children: []
    }, {
      id: 26,
      parentId: 1,
      level: 3,
      title: 'subcategory',
      children: [{
        id: 75,
        parentId: 26,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }, {
        id: 78,
        parentId: 26,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }]
    }]
  }, {
    id: 23823,
    title: 'category',
    level: 2,
    children: []
  }, {
    id: 9,
    parentId: 5,
    level: 2,
    title: 'category',
    children: [{
      id: 48414,
      parentId: 9,
      level: 3,
      title: 'subcategory',
      children: []
    }, {
      id: 2414,
      parentId: 9,
      level: 3,
      title: 'subcategory',
      children: []
    }, {
      id: 42414,
      parentId: 9,
      level: 3,
      title: 'subcategory',
      children: [{
        id: 2323213,
        parentId: 42414,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }, {
        id: 322332,
        parentId: 42414,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }]
    }]
  }]
};

console.log('Path to 2323213:',
  buildFullTree(departmentTree, {
    id: 2323213
  }).map(node => node.id).join(' -> '))

console.log('Path to 23823:',
  buildFullTree(departmentTree, {
    id: 23823
  }).map(node => node.id).join(' -> '))

console.log('Path to -1 (non existing node):',
  buildFullTree(departmentTree, {
    id: -1
  }).map(node => node.id).join(' -> '))

在 Javascript 的嵌套对象数组中查找目标对象的路径

Finding a path to target object in nested array of objects in Javascript

javascript

arrays

depth-first-search