使用递归创建动态嵌套 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": []
}]
}]
这是您的解决方案。但是,如果您的 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>");
好的,根据您的评论,我决定找到一个解决方案,当除了 parental 关系之外绝对没有其他信息时,嵌套平面数组。我的意思是数组项属性可以有两种类型。
[{id: AY998, pid: FT497}, {id: SS113, pid: MN857}, {id: MN857, pid: "root"}, {id: FT497...
其中 id
是元素的 id,pid
是 parents id,一些 objects 是根,没有其他信息,如级别等等
所以想法是根据 parental seniority 对数组进行排序,这意味着 parent 不会在 children 之后列出。因此,一旦完成排序,就可以通过反向迭代轻松完成嵌套。
好的,让我们创建一个由 100 个此类性质的项目组成的随机数组。 (我实际上必须创建这样的代码来生成具有唯一 ID 和正确 parental 关系的项目的数据数组。让我们看看代码
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>");
所以它工作起来又快又好。关键是排序算法。如前所述,它根据 parental 资历对数组进行排序,child 不能排在 parent 之前。这是唯一的条件。但与此同时,它准备了一个 parent id 索引的 LUT(哈希列表),这样一旦我们开始反向迭代数组(从最后一项到第一项),它就会避免我们对 [=44 进行昂贵的搜索=].相反,我们将从 LUT 中查找它的索引(查找 table)object 并插入它的 children(如果有)。非常快..!
所以这是 repl.it 给你玩的。
我关注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": []
}]
}]
这是您的解决方案。但是,如果您的 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>");
好的,根据您的评论,我决定找到一个解决方案,当除了 parental 关系之外绝对没有其他信息时,嵌套平面数组。我的意思是数组项属性可以有两种类型。
[{id: AY998, pid: FT497}, {id: SS113, pid: MN857}, {id: MN857, pid: "root"}, {id: FT497...
其中 id
是元素的 id,pid
是 parents id,一些 objects 是根,没有其他信息,如级别等等
所以想法是根据 parental seniority 对数组进行排序,这意味着 parent 不会在 children 之后列出。因此,一旦完成排序,就可以通过反向迭代轻松完成嵌套。
好的,让我们创建一个由 100 个此类性质的项目组成的随机数组。 (我实际上必须创建这样的代码来生成具有唯一 ID 和正确 parental 关系的项目的数据数组。让我们看看代码
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>");
所以它工作起来又快又好。关键是排序算法。如前所述,它根据 parental 资历对数组进行排序,child 不能排在 parent 之前。这是唯一的条件。但与此同时,它准备了一个 parent id 索引的 LUT(哈希列表),这样一旦我们开始反向迭代数组(从最后一项到第一项),它就会避免我们对 [=44 进行昂贵的搜索=].相反,我们将从 LUT 中查找它的索引(查找 table)object 并插入它的 children(如果有)。非常快..!
所以这是 repl.it 给你玩的。