提高使用JSON数据生成树的递归性能

Question

我需要从JSON中表示的数据构建树形结构作为对象和父级关系。我已经在下面的代码中实现了成功完成这项工作的代码，但我不确定它是否提供了最佳性能（我的意思是尽可能少地进行迭代）。

请注意，树的根表示为parent与object相同。例如{"object":"A", "parent":"A"}

关于任何其他具有更好性能的实现的建议将有所帮助！

var jsonInput = 
 
[ 
 
{"object":"A", "parent":"A"}, 
 
{"object":"B", "parent":"A"}, 
 
{"object":"C", "parent":"A"}, 
 
{"object":"D", "parent":"B"}, 
 
{"object":"E", "parent":"B"}, 
 
{"object":"F", "parent":"D"}, 
 
{"object":"G", "parent":"D"}, 
 
{"object":"H", "parent":"E"}, 
 
{"object":"I", "parent":"E"}, 
 
{"object":"J", "parent":"C"}, 
 
{"object":"K", "parent":"C"}, 
 
{"object":"L", "parent":"J"}, 
 
{"object":"M", "parent":"J"}, 
 
{"object":"N", "parent":"K"}, 
 
{"object":"O", "parent":"K"}, 
 
{"object":"P", "parent":"N"}, 
 
{"object":"Q", "parent":"N"}, 
 
{"object":"R", "parent":"O"}, 
 
{"object":"S", "parent":"O"} 
 
]; 
 

 
var root = getRoot(); 
 
root.childs = findChildrens(root); 
 

 
console.log("The tree hierarchy is:") 
 
console.log(root); 
 

 
function getRoot() { 
 
var root; 
 
for (var counter = 0; counter < jsonInput.length; counter++){ 
 
\t var item = jsonInput[counter]; 
 
\t if(item.object === item.parent) { 
 
\t \t root = item; 
 
\t \t break; 
 
\t } 
 
} 
 

 
var returnValue = JSON.parse(JSON.stringify(root)); 
 
root.visited = true; 
 
return returnValue; 
 
} 
 

 
function findChildrens(parentObject) { 
 
var childs = []; 
 
for (var counter = 0; counter < jsonInput.length; counter++){ 
 
\t var item = jsonInput[counter]; 
 
\t if(item.parent === parentObject.object && !item.visited) { 
 
\t \t var child = JSON.parse(JSON.stringify(item)); 
 
\t \t item.visited = true; 
 
\t \t child.childs = findChildrens(child); 
 
\t \t childs.push(child); 
 
\t } 
 
} 
 
return childs; 
 
}

Answer 1

具有线性运行时更简单的解决方案。

var data = [ 
 
    {"object":"A", "parent":"A"}, 
 
    {"object":"B", "parent":"A"}, 
 
    {"object":"C", "parent":"A"}, 
 
    {"object":"D", "parent":"B"}, 
 
    {"object":"E", "parent":"B"}, 
 
    {"object":"F", "parent":"D"}, 
 
    {"object":"G", "parent":"D"}, 
 
    {"object":"H", "parent":"E"}, 
 
    {"object":"I", "parent":"E"}, 
 
    {"object":"J", "parent":"C"}, 
 
    {"object":"K", "parent":"C"}, 
 
    {"object":"L", "parent":"J"}, 
 
    {"object":"M", "parent":"J"}, 
 
    {"object":"N", "parent":"K"}, 
 
    {"object":"O", "parent":"K"}, 
 
    {"object":"P", "parent":"N"}, 
 
    {"object":"Q", "parent":"N"}, 
 
    {"object":"R", "parent":"O"}, 
 
    {"object":"S", "parent":"O"} 
 
]; 
 

 
var rootNodes = data.filter(function(node) { 
 
    if (node.object in this) 
 
    throw new Error("duplicate object " + node.object); 
 

 
    this[node.object] = node; 
 
    node.children = []; 
 

 
    if (node.parent === node.object) return true; 
 
    var parent = this[node.parent]; 
 

 
    if (!parent) 
 
    throw new Error("invalid parent " + node.parent); 
 

 
    parent.children.push(node); 
 
}, Object.create(null)); 
 

 

 
console.log(rootNodes);

.as-console-wrapper { 
 
    top: 0; 
 
    max-height: 100%!important 
 
}