javascript - 扁平结构到树结构

Question

我已经浏览了有关该主题的答案，但无法获得所需的输出。因此，我再次提出这个问题。

var data = [

{ Title : "Report 1" , Parent : "root"} ,
{ Title : "Report 2" , Parent : "root"} ,
{ Title : "Report 3" , Parent : "root"} ,
{ Title : "View 1" , Parent : "Report 1"} ,
{ Title : "View 2" , Parent : "Report 1"} ,
{ Title : "Table 1" , Parent : "View 1"} ,
{ Title : "Table 2" , Parent : "View 1"} ,
{ Title : "Table 3" , Parent : "View 1"} ,
{ Title : "SLT" , Parent : "Table 1"} ,
{ Title : "SRS" , Parent : "Table 2"} ,
{ Title : "INFORMATICA" , Parent : "Table 3"} ,
{ Title : "Table 3" , Parent : "View 2"} ,
{ Title : "Table 4" , Parent : "View 2"} ,
{ Title : "Table 5" , Parent : "View 2"} ,
{ Title : "SLT" , Parent : "Table 4"} ,
{ Title : "SLT" , Parent : "Table 5"} ,
{ Title : "View 1" , Parent : "Report 2"} ,
{ Title : "View 3" , Parent : "Report 2"} ,
{ Title : "View 4" , Parent : "Report 2"} ,
{ Title : "Table 6" , Parent : "View 3"} ,
{ Title : "Table 7" , Parent : "View 3"} ,
{ Title : "Table 3" , Parent : "View 3"} ,
{ Title : "Table 8" , Parent : "View 4"} ,
{ Title : "Table 9" , Parent : "View 4"} ,
{ Title : "Table 10" , Parent : "View 4"} ,
{ Title : "SLT" , Parent : "Table 6"} ,
{ Title : "SRS" , Parent : "Table 7"} ,
{ Title : "INFORMATICA" , Parent : "Table 8"} ,
{ Title : "SLT" , Parent : "Table 9"} ,
{ Title : "SRS" , Parent : "Table 10"} ,
{ Title : "View 5" , Parent : "Report 3"} ,
{ Title : "View 6" , Parent : "Report 3"} ,
{ Title : "View 7" , Parent : "Report 3"} ,
{ Title : "View 8" , Parent : "Report 3"} ,
{ Title : "Table 11" , Parent : "View 5"} ,
{ Title : "Table 12" , Parent : "View 5"} ,
{ Title : "Table 13" , Parent : "View 5"} ,
{ Title : "Table 14" , Parent : "View 5"} ,
{ Title : "Table 15" , Parent : "View 6"} ,
{ Title : "Table 16" , Parent : "View 6"} ,
{ Title : "Table 17" , Parent : "View 6"} ,
{ Title : "Table 18" , Parent : "View 6"} ,
{ Title : "Table 19" , Parent : "View 7"} ,
{ Title : "Table 20" , Parent : "View 7"} ,
{ Title : "Table 21" , Parent : "View 8"} ,
{ Title : "Table 22" , Parent : "View 8"} ,
{ Title : "Table 23" , Parent : "View 8"} ,
{ Title : "SLT" , Parent : "Table 11"} ,
{ Title : "SRS" , Parent : "Table 12"} ,
{ Title : "INFORMATICA" , Parent : "Table 13"} ,
{ Title : "SLT" , Parent : "Table 14"} ,
{ Title : "SRS" , Parent : "Table 15"} ,
{ Title : "INFORMATICA" , Parent : "Table 16"} ,
{ Title : "SLT" , Parent : "Table 17"} ,
{ Title : "SRS" , Parent : "Table 18"} ,
{ Title : "INFORMATICA" , Parent : "Table 19"} ,
{ Title : "SLT" , Parent : "Table 20"} ,
{ Title : "SRS" , Parent : "Table 21"} ,
{ Title : "INFORMATICA" , Parent : "Table 22"} ,
{ Title : "INFORMATICA" , Parent : "Table 23"} ,
];

var root = {};
var parentCache = {};
// for each element definition in the data array
for (var i = 0; i < data.length; i++) {
    var element = data[i];
    var Title = element.Title;
   

    // create a new object and initialize
    var newObj = {"Title" : Title};
        newObj["children"] = [];

    // put this object into its parent
    if (element.Parent === "root") {
        root[Title] = newObj;
    } else {
        // XXX - if the parent isn't defined first this will fail      
        var parent = parentCache[element.Parent];      
        parent.children.push(newObj); 
      //need to run a loop on 'root' to push at different nodes, how?
    }
    // store this object in case it is a parent
    parentCache[Title] = newObj;
}

document.write('<pre>' + JSON.stringify(root, 0, 4) + '</pre>');
// console.log(JSON.stringify(root));

JSBIN link for code

我无法将表 1 推送到报告 2 --> View 1 下，并且所有其他节点(如果有任何 View 1 对象)将出现在根对象中。怎么解决这个问题？

Answer 1

理解这一点的最简单方法可能是将每个数据对象转换为带有附加 children: [] 数组的树节点。然后将每个节点添加为任何声称其 Title 与子节点所说的 Parent 匹配的 Title 的子节点。当然，这可能会将子级添加到树中的多个位置(父级不是唯一的)，但我相信这就是您想要的。我将在不进行算法优化的情况下执行此操作，只是为了保持简单以便您了解修复方法。

认识到父级不是唯一的事实应该会引导您远离构建 parentCache 的方法。可能有多个节点有资格成为任何给定节点的父节点。事实上，任何具有正确标题的对象都将是这样的父对象。

var data = [

{ Title : "Report 1" , Parent : "root"} ,
{ Title : "Report 2" , Parent : "root"} ,
{ Title : "Report 3" , Parent : "root"} ,
{ Title : "View 1" , Parent : "Report 1"} ,
{ Title : "View 2" , Parent : "Report 1"} ,
{ Title : "Table 1" , Parent : "View 1"} ,
{ Title : "Table 2" , Parent : "View 1"} ,
{ Title : "Table 3" , Parent : "View 1"} ,
{ Title : "SLT" , Parent : "Table 1"} ,
{ Title : "SRS" , Parent : "Table 2"} ,
{ Title : "INFORMATICA" , Parent : "Table 3"} ,
{ Title : "Table 3" , Parent : "View 2"} ,
{ Title : "Table 4" , Parent : "View 2"} ,
{ Title : "Table 5" , Parent : "View 2"} ,
{ Title : "SLT" , Parent : "Table 4"} ,
{ Title : "SLT" , Parent : "Table 5"} ,
{ Title : "View 1" , Parent : "Report 2"} ,
{ Title : "View 3" , Parent : "Report 2"} ,
{ Title : "View 4" , Parent : "Report 2"} ,
{ Title : "Table 6" , Parent : "View 3"} ,
{ Title : "Table 7" , Parent : "View 3"} ,
{ Title : "Table 3" , Parent : "View 3"} ,
{ Title : "Table 8" , Parent : "View 4"} ,
{ Title : "Table 9" , Parent : "View 4"} ,
{ Title : "Table 10" , Parent : "View 4"} ,
{ Title : "SLT" , Parent : "Table 6"} ,
{ Title : "SRS" , Parent : "Table 7"} ,
{ Title : "INFORMATICA" , Parent : "Table 8"} ,
{ Title : "SLT" , Parent : "Table 9"} ,
{ Title : "SRS" , Parent : "Table 10"} ,
{ Title : "View 5" , Parent : "Report 3"} ,
{ Title : "View 6" , Parent : "Report 3"} ,
{ Title : "View 7" , Parent : "Report 3"} ,
{ Title : "View 8" , Parent : "Report 3"} ,
{ Title : "Table 11" , Parent : "View 5"} ,
{ Title : "Table 12" , Parent : "View 5"} ,
{ Title : "Table 13" , Parent : "View 5"} ,
{ Title : "Table 14" , Parent : "View 5"} ,
{ Title : "Table 15" , Parent : "View 6"} ,
{ Title : "Table 16" , Parent : "View 6"} ,
{ Title : "Table 17" , Parent : "View 6"} ,
{ Title : "Table 18" , Parent : "View 6"} ,
{ Title : "Table 19" , Parent : "View 7"} ,
{ Title : "Table 20" , Parent : "View 7"} ,
{ Title : "Table 21" , Parent : "View 8"} ,
{ Title : "Table 22" , Parent : "View 8"} ,
{ Title : "Table 23" , Parent : "View 8"} ,
{ Title : "SLT" , Parent : "Table 11"} ,
{ Title : "SRS" , Parent : "Table 12"} ,
{ Title : "INFORMATICA" , Parent : "Table 13"} ,
{ Title : "SLT" , Parent : "Table 14"} ,
{ Title : "SRS" , Parent : "Table 15"} ,
{ Title : "INFORMATICA" , Parent : "Table 16"} ,
{ Title : "SLT" , Parent : "Table 17"} ,
{ Title : "SRS" , Parent : "Table 18"} ,
{ Title : "INFORMATICA" , Parent : "Table 19"} ,
{ Title : "SLT" , Parent : "Table 20"} ,
{ Title : "SRS" , Parent : "Table 21"} ,
{ Title : "INFORMATICA" , Parent : "Table 22"} ,
{ Title : "INFORMATICA" , Parent : "Table 23"} ,
];

var root = { Title: "root", children: [] };
var parentCache = {};

// Put a root node into the tree
var nodes = data.map((e) => {
 return { Title: e.Title, Parent: e.Parent, children: [] };
 });
nodes.push(root);

// Brute force: add each node as a child of its parent.
for (var iChild = 0; iChild < nodes.length; ++iChild) {
  for (var iParent = 0; iParent < nodes.length; ++iParent) {
    if (nodes[iParent].Title == nodes[iChild].Parent) {
       nodes[iParent].children.push(nodes[iChild]);
    }
  }
}

document.write('<pre>' + JSON.stringify(root, 0, 4) + '</pre>');
// console.log(JSON.stringify(root));

如果您想对此进行优化，您仍然可以构造一个父缓存，但缓存中的每个条目都将是具有匹配标题字符串的所有元素的列表。然后，您将迭代每个元素并将其添加为所有父元素的子元素。这会将父级的搜索时间从 O(N) 降至 O(1)。但我发布的示例将使用 O(N^2) 方法，因为它更容易理解您原来的问题是什么。

编辑:索引解决方案

根据@alQemist的要求，我添加了一个版本的解决方案，它使用索引来允许在恒定时间内定位父节点。

var data = [

{ Title : "Report 1" , Parent : "root"} ,
{ Title : "Report 2" , Parent : "root"} ,
{ Title : "Report 3" , Parent : "root"} ,
{ Title : "View 1" , Parent : "Report 1"} ,
{ Title : "View 2" , Parent : "Report 1"} ,
{ Title : "Table 1" , Parent : "View 1"} ,
{ Title : "Table 2" , Parent : "View 1"} ,
{ Title : "Table 3" , Parent : "View 1"} ,
{ Title : "SLT" , Parent : "Table 1"} ,
{ Title : "SRS" , Parent : "Table 2"} ,
{ Title : "INFORMATICA" , Parent : "Table 3"} ,
{ Title : "Table 3" , Parent : "View 2"} ,
{ Title : "Table 4" , Parent : "View 2"} ,
{ Title : "Table 5" , Parent : "View 2"} ,
{ Title : "SLT" , Parent : "Table 4"} ,
{ Title : "SLT" , Parent : "Table 5"} ,
{ Title : "View 1" , Parent : "Report 2"} ,
{ Title : "View 3" , Parent : "Report 2"} ,
{ Title : "View 4" , Parent : "Report 2"} ,
{ Title : "Table 6" , Parent : "View 3"} ,
{ Title : "Table 7" , Parent : "View 3"} ,
{ Title : "Table 3" , Parent : "View 3"} ,
{ Title : "Table 8" , Parent : "View 4"} ,
{ Title : "Table 9" , Parent : "View 4"} ,
{ Title : "Table 10" , Parent : "View 4"} ,
{ Title : "SLT" , Parent : "Table 6"} ,
{ Title : "SRS" , Parent : "Table 7"} ,
{ Title : "INFORMATICA" , Parent : "Table 8"} ,
{ Title : "SLT" , Parent : "Table 9"} ,
{ Title : "SRS" , Parent : "Table 10"} ,
{ Title : "View 5" , Parent : "Report 3"} ,
{ Title : "View 6" , Parent : "Report 3"} ,
{ Title : "View 7" , Parent : "Report 3"} ,
{ Title : "View 8" , Parent : "Report 3"} ,
{ Title : "Table 11" , Parent : "View 5"} ,
{ Title : "Table 12" , Parent : "View 5"} ,
{ Title : "Table 13" , Parent : "View 5"} ,
{ Title : "Table 14" , Parent : "View 5"} ,
{ Title : "Table 15" , Parent : "View 6"} ,
{ Title : "Table 16" , Parent : "View 6"} ,
{ Title : "Table 17" , Parent : "View 6"} ,
{ Title : "Table 18" , Parent : "View 6"} ,
{ Title : "Table 19" , Parent : "View 7"} ,
{ Title : "Table 20" , Parent : "View 7"} ,
{ Title : "Table 21" , Parent : "View 8"} ,
{ Title : "Table 22" , Parent : "View 8"} ,
{ Title : "Table 23" , Parent : "View 8"} ,
{ Title : "SLT" , Parent : "Table 11"} ,
{ Title : "SRS" , Parent : "Table 12"} ,
{ Title : "INFORMATICA" , Parent : "Table 13"} ,
{ Title : "SLT" , Parent : "Table 14"} ,
{ Title : "SRS" , Parent : "Table 15"} ,
{ Title : "INFORMATICA" , Parent : "Table 16"} ,
{ Title : "SLT" , Parent : "Table 17"} ,
{ Title : "SRS" , Parent : "Table 18"} ,
{ Title : "INFORMATICA" , Parent : "Table 19"} ,
{ Title : "SLT" , Parent : "Table 20"} ,
{ Title : "SRS" , Parent : "Table 21"} ,
{ Title : "INFORMATICA" , Parent : "Table 22"} ,
{ Title : "INFORMATICA" , Parent : "Table 23"} ,
];

var root = { Title: "root", parents: [], children: [] };

// Put a root node into the tree
var nodes = data.map((e) => {
 return { Title: e.Title, Parent: e.Parent, parents: [], children: [] };
 });
nodes.push(root);

// construct a title index
let titleIndex = {};
nodes.forEach(n => {
  titleIndex[n.Title] = n;
});

document.write('<h1>The Index</h1><pre>' + JSON.stringify(titleIndex, 0, 4) + '</pre>');

// Each node will have a list of its parents.  Locate each parent with the index.
nodes.forEach(n => {
  if (n.Parent)
    n.parents.push(titleIndex[n.Parent]);
});

// Push each node as a child of all its parents.  Delete the parents list to avoid circular JSON.
nodes.forEach(n => {
  n.parents.forEach(p => {
    p.children.push(n);
  });
  delete n.parents;
});

document.write('<h1>The Tree</h1><pre>' + JSON.stringify(root, 0, 4) + '</pre>');