将平面结构转换为分层结构

Question

我需要创建能够将平面对象转换为递归对象的功能。这是我的例子： 我有平面数组：

var flatArray = [ 
    { 
     Description: "G", 
     guid: "c8e63b35", 
     parent: null, 
    }, 
    { 
     Description: "Z", 
     guid: "b1113b35", 
     parent: "c8e63b35", 
    }, 
    { 
     Description: "F", 
     guid: "d2cc2233", 
     parent: "b1113b35", 
    }, 
    { 
     Description: "L", 
     guid: "a24a3b1a", 
     parent: null, 
    }, 
    { 
     Description: "K", 
     guid: "cd3b11caa", 
     parent: "a24a3b1a", 
    },  
] 

的结果应该是：

recursiveArray = [ 
    { 
     Description: "G", 
     guid: "c8e63b35", 
     parent: null, 
     Children: [ 
      { 
       Description: "Z", 
       guid: "b1113b35", 
       parent: "c8e63b35", 
       Children: [ 
        { 
         Description: "F", 
         guid: "d2cc2233", 
         parent: "b1113b35", 
        } 
       ] 
      }, 
     ] 
    }, 
    { 
     Description: "L", 
     guid: "a24a3b1a", 
     parent: null, 
     Children: [ 
     { 
      Description: "K", 
      guid: "cd3b11caa", 
      parent: "a24a3b1a", 
     } 
    } 
] 

请帮我看看这样做的方式。一个有效的算法将不胜感激，因为我有理解如何正确地做到这一点的问题。在每种情况下，我需要为递归结构中的checked元素查找特定位置，并将其推送到finded元素children数组中。我认为这很愚蠢和低效。有什么办法可以做到这一点快速和高效？

编辑：递归数组格式错误。现在应该没问题。 我的数组没有以任何方式排序。

Answer 1

这一个工作很好，易于阅读：

function flatToHierarchy (flat) { 

    var roots = [] // things without parent 

    // make them accessible by guid on this map 
    var all = {} 

    flat.forEach(function(item) { 
     all[item.guid] = item 
    }) 

    // connect childrens to its parent, and split roots apart 
    Object.keys(all).forEach(function (guid) { 
     var item = all[guid] 
     if (item.parent === null) { 
      roots.push(item) 
     } else if (item.parent in all) { 
      var p = all[item.parent] 
      if (!('Children' in p)) { 
       p.Children = [] 
      } 
      p.Children.push(item) 
     } 
    }) 

    // done! 
    return roots 
} 

Answer 2

我试图用伪代码写出算法，最后得到了几乎可行的JS代码（可能需要一些额外的验证/检查），但是显示了问题的一般方法。

//Lets separate children (nodes with a parent) from roots (nodes without a parent) 
var children = flatArray.filter(function(object){ 
    return object.parent !== null; 
}); 

var roots = flatArray.filter(function(object){ 
    return object.parent === null; 
}); 

//And add each child to the nodes tree 
children.foreach(function(child){ 
    recursiveAdd(roots, child); 
}); 

//To add a children node, node tree is searched recursively for a parent 
function recursiveAdd(nodes, child){ 
    nodes.foreach(function(parent){ 
     if(parent.guid === child.parent){ 
      parent.Children = parent.Children | []; 
      parent.Children.add(child); 
     } else if(parent.Children) { 
      recursiveAdd(parent.Children, child); 
     } 
    }); 
} 

//Temporary children array can be garbage collected 
children = null; 
//Resulting node tree 
var recursiveArray = roots; 

Answer 3

这个递归函数可能对你不错：

var flatArray = [{ 
 
    Description: "G", 
 
    guid: "c8e63b35", 
 
    parent: null, 
 
    Children: [] 
 
}, { 
 
    Description: "Z", 
 
    guid: "b1113b35", 
 
    parent: "c8e63b35", 
 
    Children: [] 
 
}, { 
 
    Description: "F", 
 
    guid: "d2cc2233", 
 
    parent: "b1113b35", 
 
    Children: [] 
 
}, { 
 
    Description: "L", 
 
    guid: "a24a3b1a", 
 
    parent: null, 
 
    Children: [] 
 
}, { 
 
    Description: "K", 
 
    guid: "cd3b11caa", 
 
    parent: "a24a3b1a", 
 
    Children: [] 
 
}, ]; 
 

 

 

 

 
for (var i = 0; i < flatArray.length; i++) { 
 
    recursive(flatArray[i]); 
 
} 
 

 

 
function recursive(a) { 
 
    for (var i = 0; i < flatArray.length; i++) { 
 
    if (flatArray[i].parent == a.guid) { 
 
     var b = flatArray[i]; 
 
     recursive(b); 
 
     a.Children.push(b); 
 
    } 
 
    } 
 
} 
 

 

 
console.log(flatArray)

Answer 4

这是我会怎么做：

var flatArray = [{ 
 
    Description: "G", 
 
    guid: "c8e63b35", 
 
    parent: null, 
 
}, { 
 
    Description: "Z", 
 
    guid: "b1113b35", 
 
    parent: "c8e63b35", 
 
}, { 
 
    Description: "F", 
 
    guid: "d2cc2233", 
 
    parent: "b1113b35", 
 
}, { 
 
    Description: "L", 
 
    guid: "a24a3b1a", 
 
    parent: null, 
 
}, { 
 
    Description: "K", 
 
    guid: "cd3b11caa", 
 
    parent: "a24a3b1a", 
 
}]; 
 

 
var recursiveArray = unflatten(flatArray); 
 

 
alert(JSON.stringify(recursiveArray, null, 4));

<script> 
 
function unflatten(items) { 
 
    return items.reduce(insert, { 
 
     res: [], 
 
     map: {} 
 
    }).res; 
 
} 
 

 
function insert(obj, item) { 
 
    var parent  = item.parent; 
 
    var map  = obj.map; 
 
    map[item.guid] = item; 
 

 
    if (parent === null) obj.res.push(item); 
 
    else { 
 
     var parentItem = map[parent]; 
 

 
     if (parentItem.hasOwnProperty("Children")) 
 
      parentItem.Children.push(item); 
 
     else parentItem.Children = [item]; 
 
    } 
 

 
    return obj; 
 
} 
 
</script>

当然，这只适用于您的flatArray具有每个父母都出现在其子女面前的属性。

希望有所帮助。

Answer 5

var flatArray = [ 
 
    { 
 
     Description: "G", 
 
     guid: "c8e63b35", 
 
     parent: null, 
 
    }, 
 
    { 
 
     Description: "Z", 
 
     guid: "b1113b35", 
 
     parent: "c8e63b35", 
 
    }, 
 
    { 
 
     Description: "F", 
 
     guid: "d2cc2233", 
 
     parent: "b1113b35", 
 
    }, 
 
    { 
 
     Description: "L", 
 
     guid: "a24a3b1a", 
 
     parent: null, 
 
    }, 
 
    { 
 
     Description: "K", 
 
     guid: "cd3b11caa", 
 
     parent: "a24a3b1a", 
 
    },  
 
]; 
 

 
//for printing 
 
function htmlPrint(obj) { 
 
    document.write('<pre>'+JSON.stringify(obj,null,2)+'</pre>'); 
 
}; 
 

 
var guids = {}; 
 
var roots = []; 
 

 
flatArray.forEach(function(node){ 
 
    guids[node.guid] = node;  //save into a hash 
 
    node.Children = [];   //make sure it has a children array 
 
    //save it as root if it is a root 
 
    if(node.parent === null){ roots.push(node);} 
 
}); 
 
flatArray.forEach(function(node){ 
 
    //if it has a parent, add self to parent's children 
 
    var parent = guids[node.parent]; 
 
    if(parent) parent.Children.push(node); 
 
}); 
 
htmlPrint(roots);