javascript - 如何计算树中子节点的路径？

Question

我有一棵这样的树:

var tree = [
  {
    type: "folder",
    children: [
      {
        type: "folder",
        children: [
          {
            type: "document",
            id: 1,
            children: []
          }
        ]
      }
    ]
  },
  {
    type: "folder",
    children: []
  }
];

这棵树的叶子总是有一个空的children数组。

我需要构造一个函数，它将返回满足给定条件的节点的索引路径。该函数将这样调用:

getPathToNode(tree, function (node) {
  return node.type === "document" && node.id === 1;
})

并会返回以下内容:

[0, 0, 0]

描述了该节点的路径:

tree[0].children[0].children[0]

这个递归函数是我到目前为止得到的:

function getPathToNode(tree, fn) {
  return tree.reduce(function (path, node, i) {
    if (fn(node)) {
      return path.concat(i);
    }
    if (node.children.length > 0) {
      const pathToNode = getPathToNode(node.children, fn);
      return pathToNode.length > 0 ? path.concat(i, pathToNode) : [];
    }
    return [];
  }, []);
}

我认为该函数需要在遍历时构建一条路径，然后，如果它到达叶子而没有找到节点，则仅删除该路径中属于未找到节点的分支的部分，然后继续其他分支机构。

Answer 1

此提案使用 Array#some ，因为迭代可能会提前退出。

然后您可以使用一个变量来表示级别和所需的索引。

function getPathToNode(node, fn) {
    var path = [];
    return node.some(function iter(level) {
        return function (a, i) {
            path.length = level;
            path[level] = i;
            return fn(a) || a.children.some(iter(level + 1));
        };
    }(0)) && path;
}

var tree = [{ type: "folder", children: [{ type: "folder", children: [{ type: "document", id: 1, children: [] }] }] }, { type: "folder", children: [] }],
    result = getPathToNode(tree, function (node) {
        return node.type === "document" && node.id === 1;
    });

console.log(result);

使用临时数组而不是关卡的不同版本。

function getPathToNode(node, fn) {
    var path = [];
    return node.some(function iter(p) {
        return function (a, i) {
            if (fn(a)) {
                path = p.concat(i);
                return true;
            }
            return a.children.some(iter(p.concat(i)));
        };
    }([])) && path;
}

var tree = [{ type: "folder", children: [{ type: "folder", children: [{ type: "document", id: 1, children: [] }] }] }, { type: "folder", children: [] }],
    result = getPathToNode(tree, function (node) {
        return node.type === "document" && node.id === 1;
    });

console.log(result);