JavaScript - 如何在节点搜索中返回树的分支？

Question

我的数据结构如下所示:

var tree = [
    {
        id: 1,
        children: []
    }, {
        id: 2,
        children: [
            {
                id: 3,
                children: []
            }
        ]
    }
];

一个分支上可以有任意数量的节点或子节点。

我的目标是从顶部(根)节点开始，搜索给定节点并返回它所在的分支。

所以在 Plunker 的例子中:https://plnkr.co/edit/PyR3H7mM0vrFyno1l7R5?p=catalogue

我想搜索节点 ID # 31，因此算法将返回 31 所属的数组(分支)。

我已经启动了算法，但如果我递归地执行它，我不知道如何再次回溯。

function traverse(branch) {

  for (var i = 0; i < branch.length; i++) {
    if (branch[i].id == node.id) {
      return branch;
    }
  }

  for (var j = 0; j < branch.length; j++) {
    if (branch[j].children.length > 0) {
      return traverse(branch[j].children);
    }
  }

}

console.log(traverse(tree));

例如，如果我查看最后一个子节点但没有找到匹配项，那么我需要回溯到父分支以尝试下一组选项。

如何修改我的算法以再次回溯？

Answer 1

您的算法非常接近，您只需要添加一个if 语句，以便它仅在找到匹配项时返回traverse 的递归结果:

function traverse(branch) {

  for (var i = 0; i < branch.length; i++) {
    if (branch[i].id == node.id) {
      return branch;
    }
  }

  for (var j = 0; j < branch.length; j++) {
    var result = traverse(branch[j].children);
    if (result !== undefined) {
      return result;
    }
  }

  return undefined; // no match found

}

console.log(traverse(tree));