Блог

У меня есть информация о соединении узлов дерева в виде связанного списка и идентификатора корневого узла. Мне нужно пронумеровать эти узлы в таком порядке, чтобы любой узел более низкого уровня в результате имел большее число, чем любой узел более высокого уровня. Нумерация начинается со значения ID корневого узла и увеличивается на 1 для каждого другого узла. Порядок узлов на одном уровне не важен. Какие алгоритмы и структуры данных я могу использовать для решения этой проблемы, прежде чем я начну изобретать велосипед, и чтобы избежать ошибок? Язык, который будет использоваться, — это чистый PHP, а данные поступают из базы данных MySQL, но приветствуется любое решение, такое как псевдокод или просто простые объяснения.

Редактировать:
до сих пор я дошел до этого (спасибо бета-версии за помощь):

 <?php

$data = array(
    array(551285, 551286),
    array(551286, 551290),
    array(551286, 551297),
    array(551288, 551432),
    array(551289, 552149),
    array(551290, 551292),
    array(551292, 551294),
    array(551296, 551355),
    array(551296, 552245),
    array(551297, 551299),
    array(551299, 551301),
    array(551299, 551304),
    array(551304, 551306),
    array(551306, 551307),
    array(551307, 551308),
    array(551308, 551309),
    array(551309, 551312),
    array(551311, 551328),
    array(551312, 551313),
    array(551313, 551315),
    array(551315, 551316),
    array(551316, 551317),
    array(551286, 551288),
    array(551286, 551289),
    array(551286, 551320),
    array(551290, 551322),
    array(551292, 551324),
    array(551294, 551296),
    array(551294, 551326),
    array(551297, 551342),
    array(551299, 551344),
    array(551301, 551303),
    array(551304, 551346),
    array(551307, 551349),
    array(551309, 551311),
    array(551309, 551353),
    array(551313, 551357),
    array(551317, 552094),
    array(551286, 551287),
    array(551290, 551291),
    array(551292, 551293),
    array(551294, 551295),
    array(551297, 551298),
    array(551299, 551300),
    array(551301, 551302),
    array(551304, 551305),
    array(551309, 551310),
    array(551313, 551314)
);

var_dump(numerateTreeNodes($data, 551285));

function numerateTreeNodes($linked_nodes, $root_node)
{
    $numbered_nodes = array();
    $queue = new SplQueue();
    $queue->enqueue($root_node);
    $counter = $root_node;
    $children_grouped = groupDirectChildren($linked_nodes);

    while ($queue->count()) {
        $t = $queue->dequeue();
        $numbered_nodes[$counter  ] = $t;
        if (isset($children_grouped[$t])) {
            foreach ($children_grouped[$t] as $t_child) {
                $queue->enqueue($t_child);
            }
        }
    }
    return $numbered_nodes;
}

function groupDirectChildren($nodes)
{
    $grouped = array();
    foreach ($nodes as $n) {
        $grouped[$n[0]][] = $n[1];
    }
    return $grouped;
}
  

Есть предложения / исправления?