使用递归创建动态嵌套json对象(create dynamic nested json objects using recursive)
我有以下JSON。
[{ "ID": "Root_1", "Name": "Root_1", "ParentID": "", "Sequent": 1 }, { "ID": "Root_2", "Name": "Root_2", "ParentID": "", "Sequent": 2 }, { "ID": "Root_1_Sub_1_Child_1", "Name": "Root_1_Sub_1_Child_1", "ParentID": "Root_1_Sub_1", "Sequent": 1 }, { "ID": "Root_1_Sub_1_Child_2", "Name": "Root_1_Sub_1_Child_2", "ParentID": "Root_1_Sub_1", "Sequent": 2 }, { "ID": "Root_1_Sub_1", "Name": "Root_1_Sub_1", "ParentID": "Root_1", "Sequent": 1 }]我想将我的JSON更改为如下。
[{ "ID": "Root_1", "Name": "Root_1", "ParentID": "", "Sequent": 1, "Sub": [{ "ID": "Root_1_Sub_1", "Name": "Root_1_Sub_1", "ParentID": "Root_1", "Sequent": 1, "Sub": [{ "ID": "Root_1_Sub_1_Child_1", "Name": "Root_1_Sub_1_Child_1", "ParentID": "Root_1_Sub_1", "Sequent": 1 }, { "ID": "Root_1_Sub_1_Child_2", "Name": "Root_1_Sub_1_Child_2", "ParentID": "Root_1_Sub_1", "Sequent": 2 }] }] }, { "ID": "Root_2", "Name": "Root_2", "ParentID": "", "Sequent": 2 }]在我尝试下面的方式后，结果不是我想要的。
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <script src="./bower_components/angular/angular.min.js"></script> <script> angular.module('myApp', []) .controller('MyCtrl', function($scope, $http) { $scope.ProjectCategoryList_FlatStyle = [{ "ID": "Root_1", "Name": "Root_1", "ParentID": "", "Sequent": 1 }, { "ID": "Root_2", "Name": "Root_2", "ParentID": "", "Sequent": 2 }, { "ID": "Root_1_Sub_1_Child_1", "Name": "Root_1_Sub_1_Child_1", "ParentID": "Root_1_Sub_1", "Sequent": 1 }, { "ID": "Root_1_Sub_1_Child_2", "Name": "Root_1_Sub_1_Child_2", "ParentID": "Root_1_Sub_1", "Sequent": 2 }, { "ID": "Root_1_Sub_1", "Name": "Root_1_Sub_1", "ParentID": "Root_1", "Sequent": 1 }]; $scope.ProjectCategoryList_TreeStyle = []; $scope.ParentArray = []; $scope.ConvertFlatToTree = function(Value){ angular.forEach(Value, function(item){ // Create row. var _Object = new Object(); _Object.ID = item.ID; _Object.Name = item.Name; _Object.ParentID = item.ParentID; _Object.Sequent = item.Sequent; _Object.Sub = []; // Checking if it is root element. if(item.ParentID){ // It is for child node. // Get Parent Element. var ParentElement = $scope.ParentArray.filter(function (x) { return x.ID === item.ParentID; }); ParentElement[0].Sub.push(_Object); $scope.ParentArray.push(_Object); }else{ // It is for parent node. // Get child elements. var ChildElementArray = $scope.ProjectCategoryList_FlatStyle.filter(function (x) { return x.ParentID === item.ID; }); if(ChildElementArray.length != 0){ $scope.ParentArray.push(_Object); $scope.ProjectCategoryList_TreeStyle.push(_Object); $scope.ConvertFlatToTree(ChildElementArray); } } }) console.log("ProjectCategoryList_TreeStyle = ", JSON.stringify($scope.ProjectCategoryList_TreeStyle)); } $scope.ConvertFlatToTree($scope.ProjectCategoryList_FlatStyle); }); </script> </head> <body ng-app="myApp" ng-controller="MyCtrl"> </body> </html>以下是我的最终结果。
[{ "ID": "Root_1", "Name": "Root_1", "ParentID": "", "Sequent": 1, "Sub": [{ "ID": "Root_1_Sub_1", "Name": "Root_1_Sub_1", "ParentID": "Root_1", "Sequent": 1, "Sub": [{ "ID": "Root_1_Sub_1_Child_1", "Name": "Root_1_Sub_1_Child_1", "ParentID": "Root_1_Sub_1", "Sequent": 1, "Sub": [] }, { "ID": "Root_1_Sub_1_Child_2", "Name": "Root_1_Sub_1_Child_2", "ParentID": "Root_1_Sub_1", "Sequent": 2, "Sub": [] }] }, { "ID": "Root_1_Sub_1", "Name": "Root_1_Sub_1", "ParentID": "Root_1", "Sequent": 1, "Sub": [] }] }]Plunker
I have following JSON.
[{ "ID": "Root_1", "Name": "Root_1", "ParentID": "", "Sequent": 1 }, { "ID": "Root_2", "Name": "Root_2", "ParentID": "", "Sequent": 2 }, { "ID": "Root_1_Sub_1_Child_1", "Name": "Root_1_Sub_1_Child_1", "ParentID": "Root_1_Sub_1", "Sequent": 1 }, { "ID": "Root_1_Sub_1_Child_2", "Name": "Root_1_Sub_1_Child_2", "ParentID": "Root_1_Sub_1", "Sequent": 2 }, { "ID": "Root_1_Sub_1", "Name": "Root_1_Sub_1", "ParentID": "Root_1", "Sequent": 1 }]I want to change my JSON to as following.
[{ "ID": "Root_1", "Name": "Root_1", "ParentID": "", "Sequent": 1, "Sub": [{ "ID": "Root_1_Sub_1", "Name": "Root_1_Sub_1", "ParentID": "Root_1", "Sequent": 1, "Sub": [{ "ID": "Root_1_Sub_1_Child_1", "Name": "Root_1_Sub_1_Child_1", "ParentID": "Root_1_Sub_1", "Sequent": 1 }, { "ID": "Root_1_Sub_1_Child_2", "Name": "Root_1_Sub_1_Child_2", "ParentID": "Root_1_Sub_1", "Sequent": 2 }] }] }, { "ID": "Root_2", "Name": "Root_2", "ParentID": "", "Sequent": 2 }]After I trying following way, the result is not what I want.
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <script src="./bower_components/angular/angular.min.js"></script> <script> angular.module('myApp', []) .controller('MyCtrl', function($scope, $http) { $scope.ProjectCategoryList_FlatStyle = [{ "ID": "Root_1", "Name": "Root_1", "ParentID": "", "Sequent": 1 }, { "ID": "Root_2", "Name": "Root_2", "ParentID": "", "Sequent": 2 }, { "ID": "Root_1_Sub_1_Child_1", "Name": "Root_1_Sub_1_Child_1", "ParentID": "Root_1_Sub_1", "Sequent": 1 }, { "ID": "Root_1_Sub_1_Child_2", "Name": "Root_1_Sub_1_Child_2", "ParentID": "Root_1_Sub_1", "Sequent": 2 }, { "ID": "Root_1_Sub_1", "Name": "Root_1_Sub_1", "ParentID": "Root_1", "Sequent": 1 }]; $scope.ProjectCategoryList_TreeStyle = []; $scope.ParentArray = []; $scope.ConvertFlatToTree = function(Value){ angular.forEach(Value, function(item){ // Create row. var _Object = new Object(); _Object.ID = item.ID; _Object.Name = item.Name; _Object.ParentID = item.ParentID; _Object.Sequent = item.Sequent; _Object.Sub = []; // Checking if it is root element. if(item.ParentID){ // It is for child node. // Get Parent Element. var ParentElement = $scope.ParentArray.filter(function (x) { return x.ID === item.ParentID; }); ParentElement[0].Sub.push(_Object); $scope.ParentArray.push(_Object); }else{ // It is for parent node. // Get child elements. var ChildElementArray = $scope.ProjectCategoryList_FlatStyle.filter(function (x) { return x.ParentID === item.ID; }); if(ChildElementArray.length != 0){ $scope.ParentArray.push(_Object); $scope.ProjectCategoryList_TreeStyle.push(_Object); $scope.ConvertFlatToTree(ChildElementArray); } } }) console.log("ProjectCategoryList_TreeStyle = ", JSON.stringify($scope.ProjectCategoryList_TreeStyle)); } $scope.ConvertFlatToTree($scope.ProjectCategoryList_FlatStyle); }); </script> </head> <body ng-app="myApp" ng-controller="MyCtrl"> </body> </html>Below is my final result.
[{ "ID": "Root_1", "Name": "Root_1", "ParentID": "", "Sequent": 1, "Sub": [{ "ID": "Root_1_Sub_1", "Name": "Root_1_Sub_1", "ParentID": "Root_1", "Sequent": 1, "Sub": [{ "ID": "Root_1_Sub_1_Child_1", "Name": "Root_1_Sub_1_Child_1", "ParentID": "Root_1_Sub_1", "Sequent": 1, "Sub": [] }, { "ID": "Root_1_Sub_1_Child_2", "Name": "Root_1_Sub_1_Child_2", "ParentID": "Root_1_Sub_1", "Sequent": 2, "Sub": [] }] }, { "ID": "Root_1_Sub_1", "Name": "Root_1_Sub_1", "ParentID": "Root_1", "Sequent": 1, "Sub": [] }] }]Plunker
最满意答案
这是你的解决方案。 但是，如果您的ID和parentID命名约定更好，那可能会好得多。 我没有进行大量的递归运行，而是先对输入数据进行排序，然后按顺序完成作业。
var flat = [{
"ID": "Root_1",
"Name": "Root_1",
"ParentID": "",
"Sequent": 1
},
{
"ID": "Root_2",
"Name": "Root_2",
"ParentID": "",
"Sequent": 2
},
{
"ID": "Root_1_Sub_1_Child_1",
"Name": "Root_1_Sub_1_Child_1",
"ParentID": "Root_1_Sub_1",
"Sequent": 1
},
{
"ID": "Root_1_Sub_1_Child_2",
"Name": "Root_1_Sub_1_Child_2",
"ParentID": "Root_1_Sub_1",
"Sequent": 2
},
{
"ID": "Root_1_Sub_1",
"Name": "Root_1_Sub_1",
"ParentID": "Root_1",
"Sequent": 1
}];
function nested(f){
return f.sort((a,b) => a.ID.length < b.ID.length ? 1 : a.ID.length == b.ID.length ? a.ID < b.ID ? -1 : 1 :-1)
.reduce((p,c,i,a) => {var parent = !!c.ParentID && a.find(e => e.ID === c.ParentID);
!!parent ? !!parent.Sub && parent.Sub.push(c) || (parent.Sub=[c]) : p.push(c);
return p;},[]);
};
document.write("<pre>" + JSON.stringify(nested(flat),null,2) + "</pre>");
好的，根据你的评论我决定找到一个解决方案来嵌套一个平面阵列，除了父母关系之外绝对没有其他信息。 我的意思是数组项属性可以是两种类型。
[{id: AY998, pid: FT497}, {id: SS113, pid: MN857}, {id: MN857, pid: "root"}, {id: FT497...
其中id是元素的id， pid是父id，有些对象是root，没有其他信息，如level等。
因此，我们的想法是在父母的资历上对数组进行排序，这意味着在孩子之后不会列出任何父母。 因此，一旦完成排序，就可以通过反向迭代容易地完成嵌套。
好吧，让我们创建一个包含100种这种性质的混乱数组。 （我实际上必须创建这样的代码来生成具有唯一id和正确父母关系的项目的数据数组。让我们看看代码
var flat = [
{ id: 'KR807', pid: 'UT731' },
{ id: 'DW402', pid: 'root' },
{ id: 'ID042', pid: 'RR203' },
{ id: 'ZT645', pid: 'CP292' },
{ id: 'LD796', pid: 'WI018' },
{ id: 'KH280', pid: 'JO343' },
{ id: 'EC894', pid: 'DX943' },
{ id: 'CR293', pid: 'VT921' },
{ id: 'XI611', pid: 'RQ903' },
{ id: 'YG388', pid: 'VN945' },
{ id: 'ZL243', pid: 'AA689' },
{ id: 'VK295', pid: 'CM110' },
{ id: 'CD374', pid: 'VK295' },
{ id: 'XO588', pid: 'ZL243' },
{ id: 'OM916', pid: 'WI018' },
{ id: 'JQ797', pid: 'CM110' },
{ id: 'BF782', pid: 'root' },
{ id: 'EK012', pid: 'VK295' },
{ id: 'AD556', pid: 'PK567' },
{ id: 'LA463', pid: 'KJ237' },
{ id: 'EL156', pid: 'MT394' },
{ id: 'VE720', pid: 'YG388' },
{ id: 'MT364', pid: 'CD374' },
{ id: 'JO343', pid: 'RJ027' },
{ id: 'QQ957', pid: 'PY806' },
{ id: 'UT731', pid: 'MT394' },
{ id: 'NA571', pid: 'OM916' },
{ id: 'NK641', pid: 'VT921' },
{ id: 'YX336', pid: 'FN157' },
{ id: 'RO244', pid: 'VT921' },
{ id: 'BJ784', pid: 'NA571' },
{ id: 'RJ027', pid: 'NH992' },
{ id: 'ZZ311', pid: 'EE630' },
{ id: 'CK935', pid: 'DX943' },
{ id: 'GF710', pid: 'PY806' },
{ id: 'WZ371', pid: 'MU258' },
{ id: 'IM089', pid: 'GL915' },
{ id: 'GN046', pid: 'NH992' },
{ id: 'MT394', pid: 'root' },
{ id: 'OC487', pid: 'WI018' },
{ id: 'KQ384', pid: 'AD556' },
{ id: 'VZ391', pid: 'ZS119' },
{ id: 'VT921', pid: 'MT394' },
{ id: 'OP416', pid: 'HT085' },
{ id: 'QU319', pid: 'ID042' },
{ id: 'SG270', pid: 'CP292' },
{ id: 'BG562', pid: 'WJ207' },
{ id: 'DX943', pid: 'NK641' },
{ id: 'II920', pid: 'UT731' },
{ id: 'AX150', pid: 'JO343' },
{ id: 'TO181', pid: 'YG388' },
{ id: 'WI985', pid: 'VK295' },
{ id: 'DU020', pid: 'VK225' },
{ id: 'RQ903', pid: 'EL156' },
{ id: 'EP215', pid: 'PK567' },
{ id: 'CZ627', pid: 'PY783' },
{ id: 'MU258', pid: 'GL915' },
{ id: 'MC556', pid: 'XI611' },
{ id: 'XX495', pid: 'II920' },
{ id: 'KJ237', pid: 'YG388' },
{ id: 'CP292', pid: 'UT731' },
{ id: 'MH665', pid: 'EL156' },
{ id: 'VK225', pid: 'FN157' },
{ id: 'FU290', pid: 'AX150' },
{ id: 'EE630', pid: 'GL915' },
{ id: 'VN945', pid: 'root' },
{ id: 'PK567', pid: 'VT921' },
{ id: 'PY806', pid: 'NH992' },
{ id: 'FN157', pid: 'GL915' },
{ id: 'DB935', pid: 'root' },
{ id: 'WK936', pid: 'ZL243' },
{ id: 'PY783', pid: 'WJ207' },
{ id: 'WJ207', pid: 'RO244' },
{ id: 'UR082', pid: 'VT921' },
{ id: 'AR742', pid: 'CD374' },
{ id: 'LS455', pid: 'IM089' },
{ id: 'GH814', pid: 'EL156' },
{ id: 'DX929', pid: 'II920' },
{ id: 'YR376', pid: 'CD374' },
{ id: 'EJ895', pid: 'XO588' },
{ id: 'ND802', pid: 'FU290' },
{ id: 'ZS119', pid: 'GD350' },
{ id: 'GD350', pid: 'YG388' },
{ id: 'HT085', pid: 'GL915' },
{ id: 'RR203', pid: 'AA689' },
{ id: 'IC103', pid: 'KR807' },
{ id: 'XT553', pid: 'WZ371' },
{ id: 'JZ880', pid: 'EL156' },
{ id: 'AA689', pid: 'EP215' },
{ id: 'TJ550', pid: 'RJ027' },
{ id: 'GL915', pid: 'root' },
{ id: 'BI123', pid: 'GD350' },
{ id: 'LD710', pid: 'JZ880' },
{ id: 'MQ351', pid: 'AD556' },
{ id: 'WI018', pid: 'NH992' },
{ id: 'KC160', pid: 'AD556' },
{ id: 'CM110', pid: 'root' },
{ id: 'OK014', pid: 'GH814' },
{ id: 'FD929', pid: 'VK225' },
{ id: 'NH992', pid: 'PK567' }
];
function construct(ar){
var lut = {},
sorted = [];
function sort(a){
var len = a.length,
fix = -1;
for (var i = 0; i < len; i++ ){
while (!!~(fix = a.findIndex(e => a[i].pid == e.id)) && fix > i)
[a[i],a[fix]] = [a[fix],a[i]]; // ES6 swap
lut[a[i].id]=i;
}console.log(lut); //check LUT on the console.
return a;
}
sorted = sort(ar.slice(0)); // don't modify things that don't belong to you :)
for (var i = sorted.length-1; i >= 0; i--){
if (sorted[i].pid != "root") {
!!sorted[lut[sorted[i].pid]].children && sorted[lut[sorted[i].pid]].children.push(sorted.splice(i,1)[0])
|| (sorted[lut[sorted[i].pid]].children = [sorted.splice(i,1)[0]]);
}
}
return sorted;
}
document.write("<pre>" + JSON.stringify(construct(flat),null,2) + "</pre>");
所以它工作得很好而且快速。 关键是排序算法。 如前所述，它根据父母的资历对数组进行排序，没有孩子可以在父母之前来到。 这是唯一的条件。 但同时它准备了父id的索引的LUT（哈希列表），这样一旦我们开始反向迭代数组（从最后一项到第一项），它就避免了我们对父项进行昂贵的搜索。 相反，我们将从LUT（查找表）对象看它的索引，并插入它的子项（如果有的话）。 非常快..！
所以这里是你玩的repl.it。
Here is your solution. However it could have been much better if you had your ID and parentID naming conventions better. Instead of doing tons of recursive runs i just sorted the input data first then did the job sequentially.
var flat = [{
"ID": "Root_1",
"Name": "Root_1",
"ParentID": "",
"Sequent": 1
},
{
"ID": "Root_2",
"Name": "Root_2",
"ParentID": "",
"Sequent": 2
},
{
"ID": "Root_1_Sub_1_Child_1",
"Name": "Root_1_Sub_1_Child_1",
"ParentID": "Root_1_Sub_1",
"Sequent": 1
},
{
"ID": "Root_1_Sub_1_Child_2",
"Name": "Root_1_Sub_1_Child_2",
"ParentID": "Root_1_Sub_1",
"Sequent": 2
},
{
"ID": "Root_1_Sub_1",
"Name": "Root_1_Sub_1",
"ParentID": "Root_1",
"Sequent": 1
}];
function nested(f){
return f.sort((a,b) => a.ID.length < b.ID.length ? 1 : a.ID.length == b.ID.length ? a.ID < b.ID ? -1 : 1 :-1)
.reduce((p,c,i,a) => {var parent = !!c.ParentID && a.find(e => e.ID === c.ParentID);
!!parent ? !!parent.Sub && parent.Sub.push(c) || (parent.Sub=[c]) : p.push(c);
return p;},[]);
};
document.write("<pre>" + JSON.stringify(nested(flat),null,2) + "</pre>");
OK as per your comment i decided to find a solution to nest a flat array when there is absolutely no information other than parental relationship. I mean the array item properties can be of two type.
[{id: AY998, pid: FT497}, {id: SS113, pid: MN857}, {id: MN857, pid: "root"}, {id: FT497...
where id is the id of the element, pid is the parents id and some objects are root and there is no other information like level etc.
So the idea is to sort the array on parental seniority which means no parent will be listed after it's children. Accordingly once the sort is done a nesting can easily be done by a reverse iteration.
Ok lets create an shuffled array of 100 items of such a nature. (I actually had to create such a code to generate a data array of items with unique id's and proper parental relationship. Lets see the code
var flat = [
{ id: 'KR807', pid: 'UT731' },
{ id: 'DW402', pid: 'root' },
{ id: 'ID042', pid: 'RR203' },
{ id: 'ZT645', pid: 'CP292' },
{ id: 'LD796', pid: 'WI018' },
{ id: 'KH280', pid: 'JO343' },
{ id: 'EC894', pid: 'DX943' },
{ id: 'CR293', pid: 'VT921' },
{ id: 'XI611', pid: 'RQ903' },
{ id: 'YG388', pid: 'VN945' },
{ id: 'ZL243', pid: 'AA689' },
{ id: 'VK295', pid: 'CM110' },
{ id: 'CD374', pid: 'VK295' },
{ id: 'XO588', pid: 'ZL243' },
{ id: 'OM916', pid: 'WI018' },
{ id: 'JQ797', pid: 'CM110' },
{ id: 'BF782', pid: 'root' },
{ id: 'EK012', pid: 'VK295' },
{ id: 'AD556', pid: 'PK567' },
{ id: 'LA463', pid: 'KJ237' },
{ id: 'EL156', pid: 'MT394' },
{ id: 'VE720', pid: 'YG388' },
{ id: 'MT364', pid: 'CD374' },
{ id: 'JO343', pid: 'RJ027' },
{ id: 'QQ957', pid: 'PY806' },
{ id: 'UT731', pid: 'MT394' },
{ id: 'NA571', pid: 'OM916' },
{ id: 'NK641', pid: 'VT921' },
{ id: 'YX336', pid: 'FN157' },
{ id: 'RO244', pid: 'VT921' },
{ id: 'BJ784', pid: 'NA571' },
{ id: 'RJ027', pid: 'NH992' },
{ id: 'ZZ311', pid: 'EE630' },
{ id: 'CK935', pid: 'DX943' },
{ id: 'GF710', pid: 'PY806' },
{ id: 'WZ371', pid: 'MU258' },
{ id: 'IM089', pid: 'GL915' },
{ id: 'GN046', pid: 'NH992' },
{ id: 'MT394', pid: 'root' },
{ id: 'OC487', pid: 'WI018' },
{ id: 'KQ384', pid: 'AD556' },
{ id: 'VZ391', pid: 'ZS119' },
{ id: 'VT921', pid: 'MT394' },
{ id: 'OP416', pid: 'HT085' },
{ id: 'QU319', pid: 'ID042' },
{ id: 'SG270', pid: 'CP292' },
{ id: 'BG562', pid: 'WJ207' },
{ id: 'DX943', pid: 'NK641' },
{ id: 'II920', pid: 'UT731' },
{ id: 'AX150', pid: 'JO343' },
{ id: 'TO181', pid: 'YG388' },
{ id: 'WI985', pid: 'VK295' },
{ id: 'DU020', pid: 'VK225' },
{ id: 'RQ903', pid: 'EL156' },
{ id: 'EP215', pid: 'PK567' },
{ id: 'CZ627', pid: 'PY783' },
{ id: 'MU258', pid: 'GL915' },
{ id: 'MC556', pid: 'XI611' },
{ id: 'XX495', pid: 'II920' },
{ id: 'KJ237', pid: 'YG388' },
{ id: 'CP292', pid: 'UT731' },
{ id: 'MH665', pid: 'EL156' },
{ id: 'VK225', pid: 'FN157' },
{ id: 'FU290', pid: 'AX150' },
{ id: 'EE630', pid: 'GL915' },
{ id: 'VN945', pid: 'root' },
{ id: 'PK567', pid: 'VT921' },
{ id: 'PY806', pid: 'NH992' },
{ id: 'FN157', pid: 'GL915' },
{ id: 'DB935', pid: 'root' },
{ id: 'WK936', pid: 'ZL243' },
{ id: 'PY783', pid: 'WJ207' },
{ id: 'WJ207', pid: 'RO244' },
{ id: 'UR082', pid: 'VT921' },
{ id: 'AR742', pid: 'CD374' },
{ id: 'LS455', pid: 'IM089' },
{ id: 'GH814', pid: 'EL156' },
{ id: 'DX929', pid: 'II920' },
{ id: 'YR376', pid: 'CD374' },
{ id: 'EJ895', pid: 'XO588' },
{ id: 'ND802', pid: 'FU290' },
{ id: 'ZS119', pid: 'GD350' },
{ id: 'GD350', pid: 'YG388' },
{ id: 'HT085', pid: 'GL915' },
{ id: 'RR203', pid: 'AA689' },
{ id: 'IC103', pid: 'KR807' },
{ id: 'XT553', pid: 'WZ371' },
{ id: 'JZ880', pid: 'EL156' },
{ id: 'AA689', pid: 'EP215' },
{ id: 'TJ550', pid: 'RJ027' },
{ id: 'GL915', pid: 'root' },
{ id: 'BI123', pid: 'GD350' },
{ id: 'LD710', pid: 'JZ880' },
{ id: 'MQ351', pid: 'AD556' },
{ id: 'WI018', pid: 'NH992' },
{ id: 'KC160', pid: 'AD556' },
{ id: 'CM110', pid: 'root' },
{ id: 'OK014', pid: 'GH814' },
{ id: 'FD929', pid: 'VK225' },
{ id: 'NH992', pid: 'PK567' }
];
function construct(ar){
var lut = {},
sorted = [];
function sort(a){
var len = a.length,
fix = -1;
for (var i = 0; i < len; i++ ){
while (!!~(fix = a.findIndex(e => a[i].pid == e.id)) && fix > i)
[a[i],a[fix]] = [a[fix],a[i]]; // ES6 swap
lut[a[i].id]=i;
}console.log(lut); //check LUT on the console.
return a;
}
sorted = sort(ar.slice(0)); // don't modify things that don't belong to you :)
for (var i = sorted.length-1; i >= 0; i--){
if (sorted[i].pid != "root") {
!!sorted[lut[sorted[i].pid]].children && sorted[lut[sorted[i].pid]].children.push(sorted.splice(i,1)[0])
|| (sorted[lut[sorted[i].pid]].children = [sorted.splice(i,1)[0]]);
}
}
return sorted;
}
document.write("<pre>" + JSON.stringify(construct(flat),null,2) + "</pre>");
So it works nice and fast. The key is the sort algorithm. As mentioned before it sorts the array according to the parental seniority and no child can come before it's parent. This is the only condition. But at the same time it prepares a LUT (hash list) of the parent id's indexes so that once we start reverse iterating the array (from last item to first) it avoids us from doing expensive searches for the parent. Instead we will look it's index up from the LUT (look up table) object and inserts it's children if any. Very fast..!
So here is the repl.it for you to play.
更多推荐
发布评论