Получение списка детей из массива с родителями, без рекурсии в PHP

Question

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

У меня есть массив элементов с Parent_ID, и я бы хотел получить список всех их детей и дочерних элементов. Он не должен быть почти таким же сложным, как идти другим путем (из массива во вложенное дерево), который я получил без проблем, используя ссылки, но по какой-то причине я застыл в мозгу ...

Любая помощь приветствуется.

У меня есть данные в двух возможных форматах, потому что я уже манипулировал ими. Какой из них лучше для ввода может быть использован. это структура (print_r) двух массивов, которые у меня есть:

Array
(
    [202735] => Array
        (
            [ID] => 202735
            [text] => aaafdf
            [Parent] => 
        )

    [202737] => Array
        (
            [ID] => 202737
            [text] => Filho 2
            [Parent] => 202735
        )

    [202733] => Array
        (
            [ID] => 202733
            [text] => Neto 1
            [Parent] => 202731
        )

    [202739] => Array
        (
            [ID] => 202739
            [text] => Neto 2
            [Parent] => 202737
        )

)

или

Array
(
    [0] => Array
        (
            [ID] => 202735
            [text] => aaafdf
            [Parent] => 
            [children] => Array
                (
                    [0] => Array
                        (
                            [ID] => 202737
                            [text] => Filho 2
                            [Parent] => 202735
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [ID] => 202739
                                            [text] => Neto 2
                                            [Parent] => 202737
                                        )

                                )

                        )

                )

        )

    [1] => Array
        (
            [ID] => 202733
            [text] => Neto 1
            [Parent] => 202731
        )

)

Желаемый вывод в формате: (родитель первого уровня => все дети и внуки)

array(202731=>array(202735));
array(202735=>array(202737,202739));

или аналогичный ... В идеале я оберну это в функцию, подобную ListChildren ($ InitialParent), и верну все дочерние элементы из такого ... вызов ListChildren (0) или (null) выведет список всех элементов и всех дочерних элементов. ..

(дополнительные элементы массива могут игнорироваться для целей этого упражнения)

OBS: некоторые данные в массиве отсутствуют ... а именно, категория выше 202735, которая будет 202731, но это только потому, что я ограничил данные, которые я скопировал ... в основном, я могу иметь либо плоский массив с родительским идентификаторы или массив «tree» с вложенными дочерними элементами в качестве источника.

Answer 1

Я закончил с этим.Спасибо за помощь, в конце концов я вернулся к рекурсивному коду.Я буду следить за его производительностью, хотя я полагаю, что только на уровне PHP это не будет проблемой.У меня был плохой опыт, когда я занимался обслуживанием проекта, в котором обращения к БД выполнялись в рекурсивной функции ... По мере роста использования, использование функции рекурсивности росло в геометрической прогрессии, а количество обращений к БД доходило до сотен тысяч ...

в любом случае:

    function __GetChildrenRec($Lista, $Categoria){
        // Return false if $initialParent doesn't exist
        if ($Categoria == 0) $Categoria = "";
        if (!isset($Lista[$Categoria])) return FALSE;

        // Loop data and assign children by reference
        foreach ($Lista as $CategAtual) {
            if ($CategAtual[Parent] == $Categoria) {
                $Filhos[] = $CategAtual[ID];
                $Filhos = array_merge((array)$Filhos,(array)self::__GetChildrenRec($Lista, $CategAtual[ID]));
            }
        }

        // Return the data
        return is_array($Filhos) ? $Filhos : array();
    }

Answer 2

Нет никакой причины избегать рекурсии, если только она не вызывает у вас проблемы с производительностьюРекурсия - это то, как большинство разработчиков, рассматривающих проблемы такого рода, вероятно, попытаются решить их, а использование альтернативных подходов может повредить удобству сопровождения, потому что ваш код делает что-то, чего не ожидает тот, кому необходимо поддерживать ваш код на более позднем этапе.

Вообще говоря, развертывание рекурсии означает управление стеком.Рекурсия - это способ получить язык, который вы используете для управления стеком, для вас, если вы не используете рекурсию, тогда вам нужно будет самостоятельно управлять стеком внутри своей функции.Самый простой способ сделать это с помощью array_push и array_pop - функций, встроенных в PHP, которые позволяют использовать массив в качестве стека.

Подход, основанный на стеке, довольно сложен по сравнению с простым использованием рекурсии, хотя, и если рекурсия создает проблемы, то ручное обслуживание стека, безусловно, будет.Конечно, есть преимущества, но, честно говоря, я бы посоветовал вам попытаться определить рекурсию, поскольку с ней действительно легче иметь дело, и, хотя она не так эффективна, как управление стеком самостоятельно, потеря производительности, вероятно,не будет узким местом в вашем коде, поскольку узкие места в PHP-скриптах обычно бывают там, где PHP взаимодействует с внешним миром (базами данных, файлами, сетевыми подключениями и т. д.).

Answer 3

Использование первого формата массива:

function list_children ($array, $initialParent) {

  // Return false if $initialParent doesn't exist
  if (!isset($array[$initialParent])) return FALSE;

  // Loop data and assign children by reference
  foreach ($array as &$item) {
    if (isset($array[$item['parent']])) {
      if (!isset($array[$item['parent']]['children'])) $array[$item['parent']]['children'] = array();
      $array[$item['parent']]['children'][] = &$item;
    }
  }

  // Return the data
  return (isset($array[$initialParent]['children'])) ? $array[$initialParent]['children'] : array();

}

В основном это создает второй массив из первого, но он делает это по ссылке - так что первоначальный родительский элемент все еще может быть найден по его идентификатору и возвращен. Возвращает массив дочерних элементов, пустой array(), если дочерних элементов нет, или FALSE, если $initialParent не существует.