Javascript: 在树中深度查找对象，然后 return 对象及其通过树的路径

Question

我有一个看起来像这样的数据结构：

let tree = {
  id: 1,
  name: "Some Name",
  children: [
    {
      id: 2,
      name: "Child 1",
      children: [...more nested objects...]
    }
  ]
};

我已经编写了一个递归函数来查找该树中的给定对象，但我现在还需要 return 路径通过树到达对象那是 returned。我正在尝试弄清楚如何修改我的搜索功能来执行此操作。

搜索功能：

_findInTree = (id, tree) => {
    let result;
    if (tree.id === id) {
      result = tree;
    } else {
      for (let child of tree.children) {
        if (child.id === id) { result = child; }
        result = this._findInTree(id, child);
        if (result) { break; }
      }
    }
    return result;
  }

Answer 1

你需要数组索引，所以你可以在 for-of 之外跟踪它，然后在路径上使用它，或者使用 Array#some 代替（或使用无聊的旧 for).

这里是在 for-of 之外跟踪索引 — 我还添加了一个 else 我认为可能非常重要：:-)

_findInTree = (id, tree, path = "") => {
    let result;
    let index;
    let rv;
    if (tree.id === id) {
        result = tree;
    } else {
        index = 0;
        for (let child of tree.children) {
            if (child.id === id) {
                result = child;
                break;
            }
            rv = this._findInTree(id, child, path + "[" + index + "]");
            if (rv != null) {
                return rv;
            }
            ++index;
        }
    }
    return { result, path };
};

显然，根据需要调整 path 的格式。（不一定是字符串，例如，可以是数组。）

这是 some 解决方案：

_findInTree = (id, tree, path = "") => {
    let result;
    let rv = null;
    if (tree.id === id) {
        result = tree;
    } else {
        tree.children.some((child, index) => {
            if (child.id === id) {
                result = child;
                return true;
            }
            rv = this._findInTree(id, child, path + "[" + index + "]");
            if (rv) {
                return true;
            }
        });
    }
    return rv || { result, path };
};

Answer 2

所以T.J。 Crowders 的位置最终在记录路径时出现错误，我最终调整了解决方案以获得以下结果，效果非常好。

  _findInTree(id, tree) {
    if (tree.id === id) {
      let path = [tree.name];
      return {result: tree, path};
    } else {
      for (let child of tree.children) {
        let tmp = this._findInTree(id, child);
        if (!_.isEmpty(tmp)) {
          tmp.path.unshift(tree.name);
          return tmp;
        }
      }
      return {};
    }
  }

Answer 3

至于我，我需要将 Kevin Whitaker 代码更改为这个代码

_findInTree(id, tree) {
    if (tree.id === id) {
      let path = [tree.name];
      return {result: tree, path};
    } else if (tree.children) { //THIS IS THE CHANGES THAT I NEED
      for (let child of tree.children) {
        let tmp = this._findInTree(id, child);
        if (!_.isEmpty(tmp)) {
          tmp.path.unshift(tree.name);
          return tmp;
        }
      }
      return {};
    }
  }

Javascript: 在树中深度查找对象，然后 return 对象及其通过树的路径

Javascript: deep find object in tree, then return object and the path to it through the tree

javascript

tree