时间戳

首页 > 解决方案 > 扁平结构到树形结构

javascript - 扁平结构到树形结构

问题描述

我已经阅读了已经给出的关于这个主题的答案，但我无法获得所需的输出。因此，我再次提出这个问题。

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 链接

我无法在 Report 2 --> View 1和所有其他节点下推送 Table 1，如果根对象中将存在任何 View 1 对象。如何解决这个问题？

标签： javascript

解决方案

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

认识到父母不是唯一的这一事实应该使您远离构建parentCache. 可能有多个节点有资格成为任何给定节点的父节点。事实上，任何具有正确 Title 的对象都会是这样的父对象。

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(1) 而不是 O(N)。但是我发布的示例将使用 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>');

推荐阅读