Вычислить левое и правое значения вложенного множества, начиная с плоского списка смежности в PHP?
Я пытаюсь преобразовать список смежности с вложенным деревом только с использованием PHP. Мне просто нужно вычислить левое и правое значения: level, parent_id а также root_id доступны:
$adj = array(
0 => array(
'id' => 100,
'name' => 'ELECTRONICS',
'level' => 0,
'parent_id' => null,
'root_id' => 100,
),
1 => array(
'id' => 101,
'name' => 'SPARE PARTS',
'level' => 1,
'parent_id' => 100,
'root_id' => 100,
),
2 => array(
'id' => 102,
'name' => 'FANS',
'level' => 2,
'parent_id' => 101,
'root_id' => 100,
),
3 => array(
'id' => 103,
'name' => 'KEYS',
'level' => 2,
'parent_id' => 101,
'root_id' => 100,
),
4 => array (
'id' => 200,
'name' => 'CONSUMER ELECTRONICS',
'level' => 0,
'parent_id' => null,
'root_id' => 200,
),
5 => array(
'id' => 201,
'name' => 'KITCHEN',
'level' => 1,
'parent_id' => 200,
'root_id' => 200,
),
6 => array(
'id' => 202,
'name' => 'FRIDGE',
'level' => 2,
'parent_id' => 201,
'root_id' => 200,
),
);
Я много искал, и должен признать, что я не силен в рекурсии, и, возможно, я испортил в этом справочную информацию.
Мое не рабочее испытание: только корни получают левые и правые значения (кажется, что они вычислены нормально):
$build = function (&$node, $left) use (&$build, $adj) {
$right = $left + 1;
foreach ($adj as &$child) {
if ($child['parent_id'] === $node['id']) {
$right = $build($child, $right);
}
}
$node['left'] = $left;
$node['right'] = $right;
return $right + 1;
};
foreach ($adj as &$n) {
if ($n['id'] === $n['root_id']) { // roots
$build($n, 1);
}
}
Решение
Лучше всего сначала построить вложенную структуру из плоского массива, а затем назначать правильные узлы (влево / вправо). Также с точки зрения производительности …
Для быстрого поиска из плоского массива я сначала преобразовал ваш $adj список в массив с $id => $val, И только в самом конце удалите тех, у кого есть родители, из корневых листьев, чтобы вы могли получить к ним линейный доступ в начале, так же, как это необходимо.
$mapped["leafs"] = [];
foreach ($adj as $val) {
$mapped["leafs"][$val["id"]] = $val;
}
foreach ($mapped["leafs"] as $id => &$n) {
if ($n["parent_id"] !== null) {
$mapped["leafs"][$n["parent_id"]]["leafs"][$id] = &$n;
}
}
$cleanup = function (&$n) use (&$cleanup) {
if (!isset($n["leafs"])) {
return;
}
ksort($n["leafs"]);
/* now, if you assume to always have maximum two nodes... if you want more, just use leafs and remove that below... */
$n["left"] = reset($n["leafs"]);
if (count($n["leafs"]) > 1) {
$n["right"] = end($n["leafs"]);
}
unset($n["leafs"]);
};
foreach ($mapped["leafs"] as $id => &$n) {
if ($n["parent_id"] !== null) {
unset($mapped["leafs"][$id]);
}
$cleanup($n);
}
$cleanup($mapped);
(p.s .: Я предполагал, что parent_id является нулем, также является допустимой проверкой для root, тем более что они в любом случае не должны быть нулевыми для поиска в массиве.)
Другие решения
Других решений пока нет …