Der einfachste Weg, einen Baum aus einer Liste von Vorfahren zu erstellen

Der erste Schlüssel besteht darin, die SQL-Ergebnisse nach der Anzahl der Vorfahren zu sortieren. Ich habe dies in PHP gemacht, da ich die Komplexität mehrstelliger Zahlen vermeide.

Dies liefert eine Liste von Knoten in einer Reihenfolge, in der sie gültig eingefügt werden können.

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
        )

)

An dieser Stelle interessieren mich die Schlüssel nicht, nur die Ahnenlisten. Der Pfad durch den Baum kann zwischen dem Schnittpunkt der verfügbaren Knoten und den verbleibenden Vorfahren gefunden werden.

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