A primeira chave é classificar os resultados SQL pelo número de ancestrais. Eu fiz isso em PHP, pois evito as complexidades dos números de vários dígitos.
Isso fornece uma lista de nós em uma ordem na qual eles podem ser inseridos de forma válida.
Array
(
[1] => Array
(
[0] => 1
)
[4] => Array
(
[0] => 4
[1] => 1
)
[2] => Array
(
[0] => 2
[1] => 1
)
[3] => Array
(
[0] => 3
[1] => 1
[2] => 2
)
)
Neste ponto, não me importo com as chaves, apenas com as listas de ancestrais. O caminho através da árvore pode ser encontrado entre a interseção dos nós disponíveis e os ancestrais restantes.
function add_node($ancestors, &$tree) {
if (count($ancestors) == 1) {
$tree[array_pop($ancestors)] = array();
return;
}
$next_node = array_intersect($ancestors, array_keys($tree));
$this->add_node(
array_diff($ancestors, $next_node) ,
$tree[array_pop($next_node)]
);
}
