Как найти корневой элемент?

Question

[Андрей Бойченко]

Есть массив:

$array = [
            0 => [
                "id" => 1,
                "parent" => 0
            ],
            1 => [
                "id" => 2,
                "parent" => 1
            ],
            2 => [
                "id" => 3,
                "parent" => 2
            ],
            3 => [
                "id" => 4,
                "parent" => 2
            ],
            4 =>[
                "id" => 5,
                "parent" => 2
            ],
            5 =>[
                "id" => 6,
                "parent" => 2
            ],
            6 =>[
                "id" => 7,
                "parent" => 1
            ],
            7 =>[
                "id" => 8,
                "parent" => 7
            ],
            8 =>[
                "id" => 9,
                "parent" => 7
            ],
            9 => [
                "id" => 10,
                "parent" => 7
            ],
            10 => [
                "id" => 11,
                "parent" => 7
            ],
            11 => [
                "id" => 12,
                "parent" => 0
            ]
        ];

Своего рода здесь, категория - подкатегория, но вложенность может быть неограниченной. Мне нужно найти корневой элемент для целой ветки. Например для элемента с индексом 3, корневым элементом будет элемент с индексом 0. По факту, передавая функции id абсолютно любой категории, хочу получить один единственный id корневой категории, для все ветки.
Прошу помочь мне с реализацией и объяснением происходящего. Из прочитанного мною, это можно решить как рекурсией так и с помощью while. Но, что вообще делать и как правильно подойди к этому, ума не приложу.

Если можно, опишите пожалуйста, решение этой задачи несколькими путями и попутно растолковав, что и где происходит, ну и какая из реализаций предпочтительнее. Хочу понять как оно работает и устроено.

Answer 1

[0xD34F]

function getRootItem($id, $array) {
  foreach ($array as $item) {
    if ($item['id'] === $id) {
      $parent = $item['parent'];
      return $parent === 0 ? $item : getRootItem($parent, $array);
    }
  }

  return null;
}

Comments

[Андрей Бойченко]

Ваше решение отдает null, какой бы id я не указал в качестве аргумента

[0xD34F]

Андрей Бойченко, брехня.

Раз всегда null, значит вы что-то неправильно делаете. Например, забыли сам массив в функцию передать. Или вы о чём-то умолчали. Например, что id могут быть строками (0 !== '0').

Думайте.

[Андрей Бойченко]

0xD34F, id не могут быть строками, я понимаю, что '0' !== 0, массив я передал, но тут дело вот в чем. Если изменить ваш пример

function getRootIndex($id, $array) {
            $parent = '';
            foreach ($array as $key => $item) {
                if ($item['id'] === $id) {
                    $parent = $item['parent'];
                    $parent === 0 ? $key : getRootIndex($parent, $array);
                }
            }
            return (int)$parent;
        }

getRootIndex(4, $cats);
Результатом будет 2, хотя должно быть 1. Поскольку для элемента с id 4, родителем будет элемент с id 2, а у него в свою очередь родитель имеет id 1.
Обьясните пожалуйста вот эту строку

$parent === 0 ? $key : getRootIndex($parent, $array);

Понятно,что это сокращенная запись if else. Если у нас $parent === 0, то $key. Но какую роль, здесь выполняет $key? Спасибо!

[0xD34F]

Андрей Бойченко,

Если изменить ваш пример...

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

[Андрей Бойченко]

0xD34F, до того, как поломал, я получал null

[0xD34F]

Андрей Бойченко, на слово поверить вам не могу, уж извините. Потрудитесь доказать свои слова. Давайте сюда полный пример того, как вы получали свой null.

Answer 2

[Андрей]

если у дерева одна вершина, я бы сделал реиндекс этого массива в массив вида
ид_элемента => ид_родителя.

в итоге, получаешь ид элемента, извлекаешь родителя, потом его родителя, потом его и так далее, пока не доберешься до элемента, у которого родителем будет 0. в процессе, записывая все ид в массив.

всё...

Comments

[Андрей Бойченко]

Вершин может быть несколько, элементов с значением 'parent' => 0, может быть сколь угодно много.

[Андрей]

Андрей Бойченко, ну, сути алгоритма это не меняет.

parent == 0 указывает лишь на то, что вершина дерева достигнута.