Transformieren Sie das flache Array mit einer einmaligen Schleife in einen Baum

Question

SO,

Das Problem

Angenommen, wir haben ein flaches Array mit folgender Struktur:

$array = [
  ['level'=>1, 'name' => 'Root #1'],
  ['level'=>1, 'name' => 'Root #2'],
  ['level'=>2, 'name' => 'subroot 2-1'],
  ['level'=>3, 'name' => '__subroot 2-1/1'],
  ['level'=>2, 'name' => 'subroot 2-2'],
  ['level'=>1, 'name' => 'Root #3']
];

Das Problem besteht darin, dieses Array so zu transformieren, dass daraus ein Baum wird. Die Unterordnung wird nur durch die Reihenfolge der Elemente und das Feld level bestimmt. Nennen wir children als Bezeichnung für die Dimension zur Speicherung von Kindknoten. Für das obige Array wäre das:

  array (
    array (
      'level' => 1,
      'name' => 'Root #1',
    ),
    array (
      'level' => 1,
      'name' => 'Root #2',
      'children' => 
      array (
        array (
          'level' => 2,
          'name' => 'subroot 2-1',
          'children' => 
          array (
            array (
              'level' => 3,
              'name' => '\_\_subroot 2-1/1',
            ),
          ),
        ),
        array (
          'level' => 2,
          'name' => 'subroot 2-2',
        ),
      ),
    ),
    array (
      'level' => 1,
      'name' => 'Root #3',
    ),
  )

Weitere Klarstellungen, falls nicht offensichtlich ist, wer Elternteil von wem ist: Der folgende Code könnte die Idee leicht visualisieren:

function visualize($array)
{
   foreach($array as $item)
   {
      echo(str_repeat('-', $item['level']).'['.$item['name'].']'.PHP_EOL);
   }
}
visualize($array);

-für das obige Array lautet das:

\-\[Root #1\]
-\[Root #2\]
--\[subroot 2-1\]
---\[\_\_subroot 2-1/1\]
--\[subroot 2-2\]
-\[Root #3\]

Spezifika

Es gibt einige Einschränkungen sowohl für die gewünschte Lösung als auch für das Eingabearray:

• Das Eingabearray ist immer gültig: Das bedeutet, seine Struktur kann immer in eine Baumstruktur umgewandelt werden. Es gibt keine seltsamen Dinge wie negative/nicht numerische Ebenen, keine ungültige Struktur der Ebenen, usw.
• Das Eingabearray kann riesig sein und derzeit ist die maximale Ebene nicht eingeschränkt
• Die Lösung muss das Problem mit einer einzigen Schleife lösen, sodass wir das Array nicht in Stücke aufteilen, Rekursion anwenden oder auf irgendeine Weise im Array hin- und herspringen können. Einfach nur foreach (oder eine andere Schleife - das spielt keine Rolle), jeweils einmal, jedes Element nacheinander behandelt werden.

Mein Ansatz

Derzeit habe ich eine Lösung mit einem Stack. Ich arbeite mit Referenzen und erhalte das aktuelle Element des Stacks, an dem der Schreibvorgang in diesem Schritt erfolgen wird. Das sieht folgendermaßen aus:

function getTree(&$array)
{
   $level = 0;
   $tree  = [];
   $stack = [&$tree];
   foreach($array as $item)
   {
      if($item['level']>$level) //Stack für neue Elemente erweitern
      {
         //Wenn es Kindelemente gibt, das letzte dem Stack hinzufügen:
         $top = key($stack);
         if(count($stack[$top]))
         {
            end($stack[$top]);
            $stack[] = &$stack[$top][key($stack[$top])];
         }
         //Dimension ['children'] zum obersten Stack-Element hinzufügen
         end($stack);
         $top = key($stack);
         $stack[$top]['children'] = [];
         $stack[] = &$stack[$top]['children'];
      }
      while($item['level']<$level--) //Bis zu einer bestimmten Ebene zurückgehen
      {
         //Zweimal: einmal für den letzten Zeiger, einmal für die Dimension ['children']
         array_pop($stack);
         array_pop($stack);
      }
      //Element zum obersten Stack hinzufügen:
      end($stack);
      $stack[key($stack)][] = $item;
      $level = $item['level'];
   }
   return $tree;
}

-da dies lang genug ist, habe ich ein Beispiel zur Verwendung & Ausgabe erstellt.

Die Frage

Wie Sie sehen können, ist meine Lösung ziemlich lang und sie beruht auf Referenzen & der Behandlung des internen Zeigers von Arrays (Dinge wie end()), daher lautet die Frage:

Gibt es vielleicht andere - kürzere und klarere Wege, dieses Problem zu lösen? Es scheint eine übliche Frage zu sein, aber ich habe keine entsprechende Lösung gefunden (es gibt eine ähnliche Frage - aber dort hat der Fragesteller eine genaue Unterordnung mit parent_id, während ich das nicht habe)

Answer 1

Das Gute an Ihrem Problem ist, dass Ihre Eingabe immer ordnungsgemäß formatiert ist, sodass sich Ihr tatsächliches Problem darauf beschränkt, Kinder für jeden Knoten zu finden, falls sie existieren, oder Eltern für jeden Knoten zu finden, falls diese vorhanden sind. Letzteres ist hier geeigneter, weil wir wissen, dass ein Knoten einen Elternknoten hat, wenn sein Level größer als eins ist und es sich um den nächsten Knoten darüber im ursprünglichen flachen Array mit einem Level handelt, der dem Level des aktuellen Knotens minus eins entspricht. Danach können wir einfach diejenigen Knoten verfolgen, an denen wir interessiert sind. Genauer gesagt, immer wenn wir zwei Knoten mit demselben Level finden, kann der zuerst gefundene Knoten keine weiteren Kinder haben.

Die Implementierung wird wie folgt aussehen:

function buildTree(array &$nodes) {
    $activeNodes = [];

    foreach ($nodes as $index => &$node) {
        // entfernen, wenn Sie keine leere ['children']-Dimension für Knoten ohne Kinder möchten
        $node['children'] = [];
        $level = $node['level'];
        $activeNodes[$level] = &$node;

        if ($level > 1) {
            $activeNodes[$level - 1]['children'][] = &$node;
            unset($nodes[$index]);
        }
    }
}

Demo

Answer 2

Die Implementierung mit der Verwendung von Rekursion:

 function buildTreeHelper(&$array, $currentLevel = 1)
 {
     $result = array();
     $lastIndex = 0;
     while($pair = each($array)) {
         list(, $row) = $pair;
         $level = $row['level'];
         if ($level > $currentLevel) {
             $result[$lastIndex]['children'] = buildTreeHelper($array, $level);
         } else if ($level == $currentLevel) {
             $result[++$lastIndex] = $row;
         } else {
             prev($array); // zurückgehen
             break;
         }
     }
     return $result;
 }

 function buildTree($array)
 {
     reset($array);
     return buildTreeHelper($array);
 }

 $array = [
  ['level'=>1, 'name' => 'Root #1'],
  ['level'=>1, 'name' => 'Root #2'],
  ['level'=>2, 'name' => 'Unterwurzel 2-1'],
  ['level'=>3, 'name' => '__Unterwurzel 2-1/1'],
  ['level'=>2, 'name' => 'Unterwurzel 2-2'],
  ['level'=>1, 'name' => 'Root #3']
];

 print_r(buildTree($array));