Chuyển cấu trúc phẳng sang phân cấp

Question

Tôi cần tạo hàm để có thể chuyển đổi đối tượng phẳng thành đối tượng đệ quy. Dưới đây là ví dụ của tôi: Tôi có mảng phẳng:

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", 
    },  
] 

kết quả nên là:

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", 
     } 
    } 
] 

Xin hãy giúp tôi tìm ra cách để làm điều đó. Một thuật toán làm việc sẽ được đánh giá cao, bởi vì tôi có vấn đề với hiểu làm thế nào để làm điều này một cách chính xác. Trong mỗi trường hợp, tôi cần phải tìm một vị trí cụ thể cho phần tử được kiểm tra trong cấu trúc đệ quy và đẩy nó vào mảng phần tử con tìm thấy. Tôi nghĩ rằng điều này là ngu ngốc và không hiệu quả. Có cách nào để làm điều này nhanh chóng và hiệu quả không?

Chỉnh sửa: Mảng đệ quy có định dạng sai. Bây giờ nó sẽ ổn thôi. Mảng của tôi không sắp xếp theo bất kỳ cách nào.

Answer 1

Cái này hoạt động độc đáo và rất dễ dàng để đọc:

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

Tôi đã cố gắng viết thuật toán trong mã giả, kết thúc bằng mã JS mà hầu như hoạt động (có thể cần một số xác thực/kiểm tra bổ sung) nhưng cho thấy cách tiếp cận chung cho vấn đề.

//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

hàm đệ quy này có thể tốt cho bạn:

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

Đây là cách tôi sẽ làm điều đó:

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>

Tất nhiên, điều này chỉ hoạt động nếu flatArray của bạn có thuộc tính mà mọi phụ huynh xuất hiện trước con cái của nó.

Hy vọng điều đó sẽ hữu ích.

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