在嵌套数据中查找父对象的简单递归函数找不到父对象？

Question

我有一个嵌套的数据结构，我想创建一个递归函数，给定一个对象的名称参数，将 return 父对象的名称参数。

有几个相关问题，但是，答案没有解释为什么我的函数 getParentName 不起作用。

为什么 getParentName 不起作用？

const nestedData = {
  name: "parent",
  children: [{ name: "child", children: [{ name: "grandchild" }] }],
};

function getParentName(nested, name) {
  if (nested.children && nested.children.map((d) => d.name).includes(name)) {
    return nested.name;
  } else if (nested.children) {
    nested.children.forEach((child) => {
      return getParentName(child, name);
    });
  }
  return undefined; //if not found
}

//The parent of "grandchild" is "child" - but the function returns undefined
const parentName = getParentName(nestedData, "grandchild");

为什么这个函数找不到父节点？

Answer 1

您的答案的问题是 .forEach 忽略了 return 值。您的 else if 分支没有 return。 .forEach 仅用于副作用。考虑使用生成器，它可以更轻松地表达您的解决方案 -

function* getParentName({ name, children = [] }, query) {
  for (const child of children)
    if (child.name === query)
      yield name
    else
      yield *getParentName(child, query)
}

const data = {
  name: "parent",
  children: [{ name: "child", children: [{ name: "grandchild" }] }],
}

const [result1] = getParentName(data, "grandchild")
const [result2] = getParentName(data, "foobar")
const [result3] = getParentName(data, "parent")

console.log("result1", result1)
console.log("result2", result2)
console.log("result3", result3)

如果未找到匹配节点或匹配节点没有父节点，答案将是 undefined -

result1 child
result2 undefined
result3 undefined

注意 [] 需要捕获单个结果。这是因为生成器可以 return 1 个或多个值。如果你不喜欢这种语法，你可以编写一个通用的 first 函数，它只从生成器中获取第一个值 -

function first(it) {
  for (const v of it)
    return v
}

const result1 = first(getParentName(data, "grandchild"))
const result2 = first(getParentName(data, "foobar"))
const result3 = first(getParentName(data, "parent"))

这种方法的优点很多。您的尝试使用了 .map 和 .includes，它们都完全遍历了 children。在另一个分支中，使用了 .forEach，它也详尽地遍历了所有 children。这种方法避免了不必要的 .map 和 .includes，而且在读取第一个值后立即停止。

Answer 2

@Mulan 回答了我的问题，指出函数失败是因为 .forEach() 中的 return 语句被忽略了。然后他们提供了一个生成器函数作为一个更好的选择。

为了比较清楚，这里是原始函数的最小改动形式。 forEach() 被替换为 (for x of array) 循环。此外，只有真值被 returned.


function getParentName(nested, name) {
  if (nested.children && nested.children.some((d) => d.name === id)) {
    return nested.name;
  } else if (nested.children) {
    for (const child of node.children) {
      const result = getParentName(child, id);
      if (result) return result;
    }
  }
  return undefined; //if not found
}

在嵌套数据中查找父对象的简单递归函数找不到父对象？

Simple recursive function to find parent object in nested data not finding parents?

javascript

recursion

nested