Как массив элементов разделить на родительские и дочерние?

Question

[Андрей Хохлов]

Задачу эту придется решить на PHP, но в самом вопросе я хотел бы помощи гуру в том числе и в выборе правильного алгоритма, без привязки к языку. Для удобства пример в json.

Есть некий массив элементов - меню например:

[
  {
    "id": 1,
    "parent": 0
  },
  {
    "id": 2,
    "parent": 0
  },
  {
    "id": 3,
    "parent": 1
  },
]

Каждый элемент содержит уникальный id, какие-то ещё данные (ссылка, название и т.д.) и id родительского элемента.
Код в примере изображает меню из двух пунктов на первом уровне и 1 на втором. Это может быть к примеру выпадающее меню.

Условная разметка для этого меню

<ul class="parent">
        <li> id1
            <ul class="child">
                <li>id3</li>
            </ul>
        </li>
        <li>id2</li>
    </ul>

Соответственно данные нужно либо подготовить перед передачей в шаблон, либо как-то обработать в самом шаблоне.
Мне видится хорошим вариантом превратить массив в такой:

[
  {
    "id": 1,
    "childs": [
      {
        "id": 3
      }
    ]
  },
  {
    "id": 2
  }
]

Тогда вывести будет просто:
элемент > если есть дочерние - создаем обертку для них > дочерний элемент.... и т.д.

Как правильнее преобразовать массив 1 в массив 2?

Я пробовал такой вариант как обход элементов и создание нового массива:
Например, если элемент родительский, то создаем $arrNew[%id_родительского%]. Если элемент дочерний, то соответственно $arrNew[%id_родительского%]['childs'][%id_дочернего%].

Может быть есть более правильное решение?

Comments

[copal]

Нужно сразу создавать "правильный json", который потом с помощью рекурсии обходить и собирать меню.

[Сергей Сергей]

copal: так тут и проблема создания правильного json-а.

[Максим Тимофеев]

А почему не на php? В пхп c массивами проще работать.

[copal]

Сергей Сергей: в чем проблема? Рук у автора нет и он носом по клавиатуре тыкает?

[Сергей Сергей]

copal: проблема в эстетике алгоритма.

[copal]

Сергей Сергей: какого алгоритма, Вы о чем? Для Вас написать руками json это алгоритм?
Объясните подробнее, а то мне теперь кажется что я не понимаю чего-то...

[Сергей Сергей]

copal: Задача сделать из линейного массива элементов дерево меню из этих элементов. Писать такое руками можно, если там не более 10 пунктов. Но, задачи у программистов, как всегда, разрастаются, желания постоянно перепечатывать одно и тоже не возникает. Поэтому требуется программочка, которая избавит от сего монотонного действа.
Но ведь если есть программа, то её можно улучшить — вот где проблема.

Для меня писать руками json — проблема, которую можно решить алгоритмом.

[Андрей Хохлов]

Максим Тимофеев, copal
Я json привел как пример, на мой взгляд, более простой для восприятия, чем то что отдает PHP:

array(2) {
[0]=>
object {
["ID"]=>int(1643)
["title"]=>string(26) "1 родительское"
["url"]=>string(18) "example.com"
}
[1]=>
object {
["ID"]=>int(1644)
["menu_item_parent"]=>string(4) "1643"
["title"]=>string(18) "2 дочернее"
["url"]=>string(18) "example.com"
}
}
*тут на самом деле портянка на порядок длиннее*
Это результат обращения к API, который и нужно переформатировать в удобный формат.
Да, решать буду на PHP, но я ищу понимание лучшего алгоритма для решения этой задачи, не важно на каком языке.

[Максим Тимофеев]

Рекурсивные функции для построения дерева смотрите. Есть даже куча готовых решений.

Answer 1

[Сергей Сергей]

Поэлементный обход — это решение "в лоб". С ним будут проблемы при неупорядоченности в массиве, когда дочерние элементы будут встречены раньше своих родительских.

var list = [/*исходный массив*/];
var menu = list
.map( function(a) {
  //сначала строим список дочерних
  a.children = list.filter( function(b) {
    return b.parent === a.id;
  });
  return a;
})
.filter( function(a) {
  //потом убираем некорневые элементы
  return a.parent === 0;
})

Элементы, которые приписаны к несуществующим родительским, будут отфильтрованы.
_{"сто раз так делал"}

Comments

[Андрей Хохлов]

Спасибо за ответ
+/- тоже решение что и пробовал

Впринципе, вроде бы есть возможность задать порядок сортировки изначального массива по принципу того, как меню создано в админке.
Т.е.
-Родитель 1
-- Дети 1
-Родитель 2
-- Дети 2

В таком случае должно работать без сюрпризов. Посмотрим может что ещё интересное предложат)