создавать динамические вложенные объекты json, используя рекурсивные

У меня есть следующий 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": []
    }]
}]

Планкер


person Frank Myat Thu    schedule 13.05.2016    source источник
comment
Вы можете попробовать реализовать мой предыдущий ответ на очень похожий вопрос. stackoverflow.com/a/36942348/4543207 Позже я попытаюсь ответить и на этот вопрос.   -  person Redu    schedule 13.05.2016


Ответы (1)


Вот ваше решение. Однако было бы намного лучше, если бы у вас были лучшие соглашения об именах идентификатора и идентификатора родителя. Вместо того, чтобы выполнять множество рекурсивных прогонов, я просто сначала отсортировал входные данные, а затем выполнил работу последовательно.

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 — идентификатор элемента, pid — идентификатор родителей, а некоторые объекты являются корневыми, и нет другой информации, такой как уровень и т. д.

Таким образом, идея состоит в том, чтобы отсортировать массив по старшинству родителей, что означает, что ни один из родителей не будет указан после его детей. Соответственно, как только сортировка выполнена, вложение можно легко выполнить с помощью обратной итерации.

Хорошо, давайте создадим перетасованный массив из 100 элементов такого рода. (На самом деле мне пришлось создать такой код для создания массива данных элементов с уникальными идентификаторами и правильными родительскими отношениями. Давайте посмотрим код

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

Так что работает красиво и быстро. Суть в алгоритме сортировки. Как упоминалось ранее, он сортирует массив в соответствии со старшинством родителей, и ни один дочерний элемент не может предшествовать родителю. Это единственное условие. Но в то же время он подготавливает LUT (хеш-список) индексов родительского идентификатора, так что, как только мы начнем обратную итерацию массива (от последнего элемента к первому), это избавит нас от дорогостоящего поиска родителя. Вместо этого мы будем искать его индекс из объекта LUT (таблица поиска) и вставлять его дочерние элементы, если они есть. Очень быстро..!

Итак, вот вам repl.it.

person Redu    schedule 13.05.2016
comment
Я проголосовал за ваше полезное предложение. Я ценю это. Но мне жаль говорить, что ID и ParentID - это 36-значный идентификатор GUID. Я не хочу, чтобы кто-то был сбит с толку, увидев GUID. Поэтому я изменил его как читаемый пользователем формат. Извини за это. - person Frank Myat Thu; 13.05.2016
comment
@Frank Myat Thu: Не беспокойтесь, все в порядке. При построении вложенной структуры из плоской структуры чрезвычайно полезно иметь возможность сортировать элементы в соответствии с их старшинством предков (или уровнем глубины). Тогда, как вы видите, это просто Array.prototype.reduce() работа. В противном случае... может потребоваться рекурсивная работа, но что-то более умное, чем обход дерева, поскольку в больших структурах простые обходы дерева могут привести к длительным перерывам на кофе. Я подумаю об этом. - person Redu; 13.05.2016
comment
@Frank Myat Thu: Хорошо, я изменил код для эмуляции вашей структуры данных. Пожалуйста, смотрите редактирование моего ответа для деталей. Я надеюсь, что это поможет вам. - person Redu; 16.05.2016