Eenvoudigste manier om een ​​boom te bouwen uit een lijst met voorouders

De eerste sleutel is om de SQL-resultaten te sorteren op het aantal voorouders. Ik deed dit in PHP omdat ik de complexiteit van meercijferige getallen vermijd.

Dit geeft een lijst met knooppunten in een volgorde waarin ze geldig kunnen worden ingevoegd.

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
        )

)

Op dit moment geef ik niet om de sleutels, alleen de lijsten met voorouders. Het pad door de boom is te vinden tussen de kruising van beschikbare knooppunten en de resterende voorouders.

  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)]
        );  
  }