JavaScript树遍历算法

Question

我可以帮助您以深度优先的方式遍历树结构，但我需要一个正确的算法来完成。

我的输入如下：

[
    ["A", "B", "C"],
    ["1", "2"],
    ["a", "b", "c", "d"]
]

输出应该采取以下形式：

[
    "A/1/a", "A/1/b", "A/1/c", "A/1/d",
    "A/2/a", "A/2/b", "A/2/c", "A/2/d",
    "B/1/a", "B/1/b", "B/1/c", "B/1/d",
    "B/2/a", "B/2/b", "B/2/c", "B/2/d",
    "C/1/a", "C/1/b", "C/1/c", "C/1/d",
    "C/2/a", "C/2/b", "C/2/c", "C/2/d"
]

- Adam

---

这是可以做到的，但有点棘手。你能否重新组织你的数据？你将会遇到协调A B C与1 2以及a b c d对应的困难；你期望的数据看起来遵循了一个相当奇怪的规则。不过，感谢提供期望数据，加一分。 - Bojangles

当然可以。我可以以任何方式操作输入。哪种形式更可取？ - Adam

我能想到的最简单的方法是使用子数组而不是兄弟数组。这样更容易像树形结构一样遍历。 - Bojangles

Answer 1

这个应该可以胜任任务：

function traverse(arr) {
  var first = arr[0];
  var ret = [];
  if (arr.length == 1) {
    for (var i = 0; i < first.length; i++) {
      ret.push(first[i]);
    }
  } else {
    for (var i = 0; i < first.length; i++) {
      var inn = traverse(arr.slice(1));
      for (var j = 0; j < inn.length; j++) {
        ret.push(first[i] + '/' + inn[j]);
      }
    }
  }
  return ret;
}

var inp = [
  ["A", "B", "C"],
  ["1", "2"],
  ["a", "b", "c", "d"]
];

var out = traverse(inp);

console.log(out);

- icyrock.com

Answer 2

你要找的是一个列表的笛卡尔积，这个问题之前已经提出过。从那个问题的被接受的答案中借鉴，你可以在Javascript 1.7中这样做：

function product() {
    return Array.prototype.reduce.call(arguments, function(as, bs) {
        return [a.concat(b) for each (a in as) for each (b in bs)];
    }, [[]]);
};

function convert(lst) {
  var solution = [];
  for (var i = 0; i < lst.length; i++) {
    solution.push(lst[i][0] + "/" + lst[i][1] + "/" + lst[i][2]);
  }
  return solution;
};

convert(product(["A", "B", "C"], ["1", "2"], ["a", "b", "c", "d"]));

> ["A/1/a", "A/1/b", "A/1/c", "A/1/d",
   "A/2/a", "A/2/b", "A/2/c", "A/2/d",
   "B/1/a", "B/1/b", "B/1/c", "B/1/d",
   "B/2/a", "B/2/b", "B/2/c", "B/2/d",
   "C/1/a", "C/1/b", "C/1/c", "C/1/d",
   "C/2/a", "C/2/b", "C/2/c", "C/2/d"]

- Óscar López

---

我认为你应该包含永久链接，因为理论上他们可以更改已接受的答案并发布100个答案（那样找到它会很困难）。 - ajax333221

@ajax333221 同意了，我已按你建议添加了永久链接。 - Óscar López

这更加优雅和通用，但它并没有解决特定的问题，并且当前版本存在错误。 - Adam

@Adam 我刚刚更新了我的回答，我让代码更加清晰，但是除此之外，我找不到你所说的错误，它是什么？ - Óscar López

我知道这是一个算法问题，但如果它在Chrome稳定版中无法工作，对我来说就没有什么用处了。 - Adam