打印从根到具有多个子节点的树中给定节点的路径

Question

我正在尝试打印从根到包含值 2 的给定节点的路径。每个节点可以有包含多个节点的子节点。 Here is a visual reference

我有这样的航班数据：

const flightsTree = {
  departureAirportId: 1,
  flights: [
    {
      departureAirportId: 16,
      flights: [
        { departureAirportId: 8 },
        { departureAirportId: 17 },
        { departureAirportId: 2 },
        { departureAirportId: 11 },
        {
          departureAirportId: 10,
          flights: [
            {
              departureAirportId: 17,
              flights: [{ departureAirportId: 99 }, { departureAirportId: 2 }],
            },
            { departureAirportId: 2 },
          ],
        },
        { departureAirportId: 2 },
        { departureAirportId: 6 },
        { departureAirportId: 3 },
      ],
    },
  ],
};

这是我到目前为止写的代码：

const hasPath = (data, path, from) => {
  if (!data) {
    return false;
  }
  path.push(data.departureAirportId);
  if (data.departureAirportId === from) {
    return true;
  }
  if (data.flights) {
    data.flights.forEach((pRule) => {
      hasPath(pRule, path, from);
      return true;
    });
  } else {
    path.pop();
    return false;
  }
  return path;
};

console.log(hasPath(flightsTree, [], 2));

到目前为止我得到：

[1, 16, 2, 10, 17, 2, 2, 2]

它似乎能够找到包含该值的节点，但除了第一个发现之外不打印根路径。

非常感谢您的帮助。

Answer 1

此版本首先计算所有条路线，然后过滤那些以给定位置结尾的路线。第二部分是微不足道的。第一个是简单的递归；当路线没有航班时，我们只需 return 一个由包含出发机场的数组组成的数组。当它有航班时，我们会重复这些和每个结果，我们会在我们当前的出发机场之前添加：

const routes = ({departureAirportId, flights = []}) => 
  flights.length == 0
    ? [[departureAirportId]]
    : flights .flatMap (routes) .map (r => [departureAirportId, ...r])

const endingAt = (loc, flights) => 
  routes (flights) .filter (r => r [r.length - 1] == loc)

const flightsTree = {departureAirportId: 1, flights: [{departureAirportId: 16, flights: [{departureAirportId: 8}, {departureAirportId: 17}, {departureAirportId: 2}, {departureAirportId: 11}, {departureAirportId: 10, flights: [{departureAirportId: 17, flights: [{departureAirportId: 99}, {departureAirportId: 2}]}, {departureAirportId: 2}]}, {departureAirportId: 2}, {departureAirportId: 6}, {departureAirportId: 3}]}]}

console .log (endingAt (2, flightsTree))

.as-console-wrapper {max-height: 100% !important; top: 0}

这里有两个假设。首先是您只需要目标机场 end 的那些。如果您想要通过机场 2 的所有路径，您可以将 endingAt 替换为过滤路由测试的函数，如果有任何 contain目标。

第二个是结果的顺序并不那么重要。这种深度优先遍历比较简单，但是如果你图片中的结果顺序很重要，我们当然可以写一个广度优先遍历的版本。

Answer 2

斯科特的回答很漂亮。我将分享一种使用生成器的方法，因为像这样的问题通常只涉及找到一个或一些已知数量的解决方案。生成器允许我们提前停止计算，而不是计算 all 路由。注意生成器方法的结构与 Scott 的程序之间的相似性 -

function* routes ({departureAirportId, flights = []}, r = [])
{ if (flights.length === 0)
    yield [...r, departureAirportId]
  else
    for (const q of flights) 
      yield* routes(q, [...r, departureAirportId])
}

function* endingAt (t, loc)
{ for (const r of routes(t))
    if(r[r.length - 1] == loc)
      yield r
}

const flightsTree = {departureAirportId: 1, flights: [{departureAirportId: 16, flights: [{departureAirportId: 8}, {departureAirportId: 17}, {departureAirportId: 2}, {departureAirportId: 11}, {departureAirportId: 10, flights: [{departureAirportId: 17, flights: [{departureAirportId: 99}, {departureAirportId: 2}]}, {departureAirportId: 2}]}, {departureAirportId: 2}, {departureAirportId: 6}, {departureAirportId: 3}]}]}

console.log(Array.from(endingAt(flightsTree, 2)))

上述方法是合理的，因为它将问题分解为两个独立的部分，routes 和 endingAt。但是，如果您愿意，可以将这两个功能合并为一个 -

function* endingAt (t, loc, r = [])
{ if (t.flights)
    for (const q of t.flights) 
      yield* endingAt(q, loc, [...r, t.departureAirportId])
  else if (t.departureAirportId == loc)
    yield [...r, t.departureAirportId]
}

const flightsTree = {departureAirportId: 1, flights: [{departureAirportId: 16, flights: [{departureAirportId: 8}, {departureAirportId: 17}, {departureAirportId: 2}, {departureAirportId: 11}, {departureAirportId: 10, flights: [{departureAirportId: 17, flights: [{departureAirportId: 99}, {departureAirportId: 2}]}, {departureAirportId: 2}]}, {departureAirportId: 2}, {departureAirportId: 6}, {departureAirportId: 3}]}]}

console.log(Array.from(endingAt(flightsTree, 2)))

打印从根到具有多个子节点的树中给定节点的路径

Print path from root to a given node in a tree with multiple children

javascript

tree

recursion

traversal