javascript - 通过直接路径在树中查找路径

Question

我有类似的问题:JavaScript: Find all parents for element in tree recursive

但我不是通过名称找到路径，而是通过直接路径找到路径。

const path = ["name1", "name4", "name5"];

const data = [
    {
        'name': 'name1',
        'tree': [
            {'name': 'name2'},
            {'name': 'name3'},
            {
                'name': 'name4',
                'tree': [
                    {'name': 'name5'},
                    {'name': 'name6'}
                ]
            },
            {'name': 'name7'}
        ]
    },
    {
        'name': 'name8',
        'tree': [
            {'name': 'name9'}
        ]
    }
];

它返回所有可能的路径或什么都不返回。

当 path 太短时，它什么都不返回。

当 path 太长时，它什么都不返回。

感谢您的帮助!

所需输出的示例:

const path = ["name1", "name4", "name5"];
findAPath(data, path) 

返回:["name1", "name4", "name5"]

const path = ["name1", "name7", "name5"];
findAPath(data, path)

返回[]

const path = ["name1", "name4", "name5", "name5"];
findAPath(data, path) 

返回[]

我的尝试:

let index = 0;
function find(data, index) {
    let index = index;
    data.some((o) => {
        if(o.name == path[index]) {
            index++;
            find(o.tree, index);
        }
    });
    // I don't know what return here.
    // I need to probably return path where I am.
    return <>;
}

Answer 1

使用Array.prototype.flatMap

这是一个使用 mutual recursion 的功能性解决方案技术 -

const None =
  Symbol ()

const findPath = (tree = [], names = [], r = []) =>
  tree.length && names.length                              // base: and
    ? tree.flatMap(branch => findPath1(branch, names, r))
    : tree.length || names.length                          // inductive: xor
        ? []
        : [ r ]                                            // inductive: nor                                     // inductive: nor

const findPath1 = ({ name = "", tree = [] } = {}, [ q = None, ...more ] = [], r = []) =>
  name === "" && q === None                    // base: and
    ? [ r ]
    : name === "" || q === None || name !== q  // inductive: xor
        ? []
        : findPath(tree, more, [ ...r, q ])    // inductive: nor

findPath(data, ["name1", "name4", "name5"])
// => [ [ "name1", "name4", "name5" ] ]

注意如果您的数据包含多个输入值的路径，所有路径将被返回-

const data = [
  {
      'name': 'name1',                   // name1
      'tree': [
          {'name': 'name2'},
          {'name': 'name3'},
          {
              'name': 'name4',           // name1->name4
              'tree': [
                  {'name': 'name5'},     // name1->name4->name5
                  {'name': 'name6'}
              ]
          },
          {
            'name': 'name4',             // name1->name4
            'tree': [
                {'name': 'name5'},       // name1->name4->name5
                {'name': 'name6'}
              ]
          },
          {'name': 'name7'}
      ]
  },
  {
      'name': 'name8',
      'tree': [
          {'name': 'name9'}
      ]
  }
]

就像你问的那样，它返回所有可能的路径，或者什么都不返回 -

findPath(data, ["name1", "name4", "name5"])
// => [ [ "name1", "name4", "name5" ],
//      [ "name1", "name4", "name5" ] ]

findPath(data, [ "name1", "name7" ])
// => [ [ "name1", "name7" ] ]

findPath(data, [ "name1", "name9" ])
// => []

当路径太短或太长时，它什么都不会返回 -

findPath(data, [ "name1", "name4" ])
// => []

findPath(data, [ "name1", "name4", "name5", "name6" ])
// => []

展开下面的代码片段以在您自己的浏览器中验证结果 -

const None =
  Symbol ()

const findPath = (tree = [], names = [], r = []) =>
  tree.length && names.length
    ? tree.flatMap(branch => findPath1(branch, names, r))
    : tree.length || names.length
        ? []
        : [ r ]

const findPath1 = ({ name = "", tree = [] } = {}, [ q = None, ...more ] = [], r = []) =>
  name === "" && q === None
    ? [ r ]
    : name === "" || q === None || name !== q
        ? []
        : findPath(tree, more, [ ...r, q ])

const data = [
  {
      'name': 'name1',
      'tree': [
          {'name': 'name2'},
          {'name': 'name3'},
          {
              'name': 'name4',
              'tree': [
                  {'name': 'name5'},
                  {'name': 'name6'}
              ]
          },
          {'name': 'name7'}
      ]
  },
  {
      'name': 'name8',
      'tree': [
          {'name': 'name9'}
      ]
  }
]

console.log(findPath(data, ["name1", "name4", "name5"]))
// [ [ "name1", "name4", "name5" ] ]

console.log(findPath(data, [ "name1", "name7" ]))
// [ [ "name1", "name7" ] ]

console.log(findPath(data, [ "name1", "name9" ]))
// []

---

使用生成器

这是使用生成器的替代实现 -

const None =
  Symbol ()

const findPath = function* (tree = [], names = [], r = [])
{ if (tree.length && names.length)        // base: and
    for (const branch of tree)
      yield* findPath1(branch, names, r)
  else if (tree.length || names.length)   // inductive: xor
    return
  else                                    // inductive: nor
    yield r
}

const findPath1 = function* ({ name = "", tree = [] } = {}, [ q = None, ...more ] = [], r = [])
{ if (name === "" && q === None)                     // base: and
    yield r
  else if (name === "" || q === None || name !== q)  // inductive: xor
    return
  else                                               // inductive: nor
    yield* findPath(tree, more, [ ...r, q ])
}

它与上面的输出完全相同，只是将可迭代生成器强制转换为数组，我们使用 Array.from -

Array.from(findPath(data, ["name1", "name4", "name5"]))
// => [ [ "name1", "name4", "name5" ] ]

Array.from(findPath(data, [ "name1", "name7" ]))
// => [ [ "name1", "name7" ] ]

Array.from(findPath(data, [ "name1", "name9" ]))
// => []

展开下面的代码片段以在您自己的浏览器中验证结果 -

const None =
  Symbol ()

const findPath = function* (tree = [], names = [], r = [])
{ if (tree.length && names.length)
    for (const branch of tree)
      yield* findPath1(branch, names, r)
  else if (tree.length || names.length)
    return
  else
    yield r
}

const findPath1 = function* ({ name = "", tree = [] } = {}, [ q = None, ...more ] = [], r = [])
{ if (name === "" && q === None)
    yield r
  else if (name === "" || q === None || name !== q)
    return
  else
    yield* findPath(tree, more, [ ...r, q ])
}

const data = [
  {
      'name': 'name1',
      'tree': [
          {'name': 'name2'},
          {'name': 'name3'},
          {
              'name': 'name4',
              'tree': [
                  {'name': 'name5'},
                  {'name': 'name6'}
              ]
          },
          {'name': 'name7'}
      ]
  },
  {
      'name': 'name8',
      'tree': [
          {'name': 'name9'}
      ]
  }
]

console.log(Array.from(findPath(data, ["name1", "name4", "name5"])))
// [ [ "name1", "name4", "name5" ] ]

console.log(Array.from(findPath(data, [ "name1", "name7" ])))
// [ [ "name1", "name7" ] ]

console.log(Array.from(findPath(data, [ "name1", "name9" ])))
// []

---

它们是如何相同的；他们怎么不

请注意两种实现之间的相似性以及结果的形成方式。两者都使用相互递归。函数式解决方案使用表达式，而生成器解决方案使用语句。生成器实现扩展了一个明显的优势，我们可以随时选择停止或继续迭代(“查找”)。

例如，想象一个输入，其中有十 (10) 个给定输入的唯一路径。也许我们只想返回第一个匹配项，

const findFirst = (tree = [], names = []) =>
{ for (const path of findPath(tree, names))
    return path
}

或者获取前三 (3) 个匹配项 -

const findFirst3 = (tree = [], names = []) =>
{ const r = []
  for (const path of findPath(tree, names))
    if (r.length < 3)
      r.push(path)
  return r
}

或者获取第一个N -

const findFirstN = (tree = [], names = [], n = 0) =>
{ const r = []
  for (const path of findPath(tree, names))
    if (r.length < n)
      r.push(path)
  return r
}

生成器就是这样灵活的。相比之下，flatMap 实现是急切的，总是返回所有结果。