javascript - 递归 - 将 Javascript Map 转换为嵌套 JSON 对象

Question

提前感谢您的帮助!

我正在尝试将特定的 javascript 映射转换为嵌套的 JSON 对象。 map 示例如下所示:

["a", ["b", "c"]]
["b", ["e"]]
["c", ["f"]]
["e", []]
["f", []]

其中键代表父节点，数组中的值是其直接子节点。值的空数组表示该给定键没有子项。我想生成如下所示的输出:

{
    "name": “a”,
    "children": [{
        "name": “b”,
        "children": [{
            "name": “e”
            }]
        }, {
            "name": “c”,
            "children": [{
                "name": “f”,
            }]
        }]
}

(这可能不是一个格式良好的 json 对象，但希望能够说明 javascript 示例 map 所演示的层次关系)。此外，虽然很简单，但数组中的键和值都被假定为已排序。

最后，我知道这适合递归解决方案。任何帮助将不胜感激。再次感谢您抽出时间!

Answer 1

你想要学习解决这个问题的算法叫做 topological sorting ，它假设您上面描述的图没有循环，但是对于上面的情况，可以稍微修改算法以仅查找没有父节点作为根节点的节点。

可能的解决方案:

var hasParent = {};

function computeParentCount(data) {
  stack = [];
  for (key in data) {
    data[key].forEach(function (child) {
      hasParent[child] = true;
    });
  }
}

function appendAfterDfs(res, data, key) {
  var node = {
    name: key
  };
  if (data[key].length) {
    // only nodes with a children array with more than 0 elements
    // have children in the json
    node.children = [];
  }
  data[key].forEach(function (child) {
    appendAfterDfs(node.children, data, child);
  });
  res.push(node);
}

function main() {

  var data = {
    'a': ['b', 'c'],
    'b': ['e'],
    'c': ['f'],
    'e': [],
    'f': [],
  };

  computeParentCount(data);

  // build the json
  var res = [];
  for (key in data) {
    if (!hasParent[key]) {
      appendAfterDfs(res, data, key);
    }
  }
  document.write('<pre>' + JSON.stringify(res, null, '  ') + '</pre>');
}

main()

说明:

1. 首先找到没有父节点的键(并将它们称为根节点)
2. 对每个根节点通过 data 对象执行 dfs，直到节点没有任何子节点
3. 收集进程中的每个节点(将其保存在父级的子级数组中)