通用树的递归循环

Question

几天来我一直在努力解决以下问题。假设递归函数遍历基本上是树的表示的字典。

输入如下所示：

var connections = {1:[2, 3, 4], 2:[5, 6, 7], 3:[8], 4:[9, 10]}

它代表的相应树如下所示：

中间目标是以深度优先搜索的方式打印出数字，即：

我对这个问题的解决方案是：

function dfs(connections, parent) {
    console.log(parent);
    if (!(parent in connections)) {
      return;
    }

    for (i = 0; i < connections[parent].length; i++) {
      dfs(connections, connections[parent][i]);
    }
    return;
}

但是，调用函数

dfs(connections, 1)

导致以下结果：

这意味着它不会返回到上一个函数并继续for循环。如果您有任何想法，我将不胜感激。

干杯

Answer 1

你的i是隐式全局的，所以在它遍历2（长度为3）之后，i是4，所以进一步测试i < connections[parent].length 失败。

您可以使用 let 来修复它 (for (let i = 0)，但使用 forEach 可能会更好：数组方法更简洁，更不容易出错，比 for 循环更实用：

var connections = {
  1: [2, 3, 4],
  2: [5, 6, 7],
  3: [8],
  4: [9, 10]
}

function dfs(connections, parent) {
  console.log(parent);
  if (!(parent in connections)) {
    return;
  }
  connections[parent].forEach(prop => dfs(connections, prop));
}
dfs(connections, 1)

通用树的递归循环

Recursive Loop for Generic Tree

javascript

recursion

depth-first-search