將平面結構轉換爲分層結構

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);