heinetz: Verständisfrage Rekursion

Hallo Forum,

mein PHP-Skript liefert mir zwar das Ergebnis, das ich erwarte. Dennoch fühle ich mich damit unwohl, weil ich nicht genau weiss, was passiert ;(

function flatten_array (&array){  
 global $my_new_array;  
 foreach ($array as $key => &$value){  
  $my_new_array[$key] = $value['something'];  
  if ($value['children']) {  
   flatten_array($value['children']);  
  }  
 }  
 return $my_new_array;  
}  
  
function test (){  
 global $my_old_array;  
 return flatten_array($my_old_array);  
}

Wie läuft das ab? 'Wartet' die Funktion test(), bis die Funktion flatten_array() irgendwann irendwas zurückgibt? Oder ist das hier grundlegend falsch?

beste gruesse,
heinetz

  1. 'Wartet' die Funktion test(), bis die Funktion flatten_array() irgendwann irendwas zurückgibt?

    Ja, bei einem Funktionsaufruf wird gewartet. Sonst könnte ja das Ergebnis der Funktion nicht weiterverarbeitet werden.

  2. Hallo,

    mein PHP-Skript liefert mir zwar das Ergebnis, das ich erwarte.

    sehr schön für Dich.
    Bei welchen Ausgangsdaten liefert es Dir welches Ergebnis?

    Dennoch fühle ich mich damit unwohl, weil ich nicht genau weiss, was passiert ;(

    Ich fühlte mich bei Deinem Code extrem unwohl, weil er nicht die Spur eines Kommentars enthält, weil er globale Variablen enthält und weil ich keine Vorstellung habe, auf welcher konkreten Datenstruktur Deine Funktion operiert.

    function flatten_array (&array){

    Welchen Grund gibt es für die globale Deklaration hier?

    global $my_new_array;

    Vermutlich möchtest Du Quell- und Zielarray übergeben,

    wobei nur beim Ziel eine Referenz erforderlich ist.

    foreach ($array as $key => &$value){
      $my_new_array[$key] = $value['something'];

    Möchtest Du nicht eher überprüfen, ob es sich bei $value['children'] um

    ein Array handelt?

    "something" ist ein extrem schlechter Index. Warum verwendest Du sowas?

    Was machst Du mit all den anderen Werten? Wirfst Du diese einfach weg?

    if ($value['children']) {
       flatten_array($value['children']);
      }
    }
    return $my_new_array;
    }

    function test (){

    und warum um alles in der Welt ist hier eine globale Variable?

    Ist es zu schwer, diese einfach als Parameter zu übergeben.

    global $my_old_array;
    return flatten_array($my_old_array);
    }

      
    
    > Wie läuft das ab? 'Wartet' die Funktion test(), bis die Funktion flatten\_array() irgendwann irendwas zurückgibt?  
      
    ja sicher. Das ist völlig normal - wie bei jedem Funktionsaufruf. test() weiß nichts von den Interna von flatten\_array() und gibt selbst einfach den Rückgabewert dieser Funktion zurück.  
      
    Ich würde den Code nicht so stehen lassen ...  
      
      
    Freundliche Grüße  
      
    Vinzenz
    
    1. Moin!

      Dennoch fühle ich mich damit unwohl, weil ich nicht genau weiss, was passiert ;(

      Ich fühlte mich bei Deinem Code extrem unwohl, weil er nicht die Spur eines Kommentars enthält, weil er globale Variablen enthält und weil ich keine Vorstellung habe, auf welcher konkreten Datenstruktur Deine Funktion operiert.

      Die globalen Variablen sind noch nicht mal so sehr das Problem. Viel schlimmer finde ich die als Referenz übergebenen Parameter sowie die Referenz in foreach. Damit holt man sich richtig üble Probleme ins Haus, wenn man es nicht richtig macht, und der Code wird auf diese Weise extrem unübersichtlich zu lesen.

      - Sven Rautenberg

      1. Hi,

        ich habe versucht, den Code für das Beispiel hier auf das Wesentliche zu reduzieren, damit er für sich spricht und damit ohne Kommentare auskommt. Da ich möglicherweise nicht weiss, was das Wesentliche ist, ist es mir möglicherweise nicht ganz gelungen. Ich hoffe, es ist trotzdem klar geworden, was ich mit dem Code bezwecken will. Dass ich damit nicht zufrieden bin, hatte ich als allererstes geschrieben. Wenn ich in der Lage gewesen wäre, das zu meiner eigenen Zufriedenheit zu lösen, hätte ich das getan.

        Ich versuche es anders herum:

        Wie lässt sich die Aufgabe besser lösen?

        Es gibt ein multidimensionales Array, dass eine Baumstruktur abbildet und dessen Tiefe variabel ist und ich benötige ein eindimesionales Array, das eine Information enthält, die irgendwie den, ich nenne es mal 'Pfad' abbildet. In dem folgenden Beispiel wird nicht der Pfad, sondern nur die "Tiefe" eines Elements, die es in dem Ausgangsarray hatte, abgebildet.

        vorher:
        -------

        Array  
        (  
            [1] => Array  
                (  
                    [children] => Array  
                        (  
                            [137] => Array  
                                (  
                                    [children] => Array  
                                        (  
                                            [149] => Array  
                                                (  
                                                    [site_id] => 149  
                                                    [parent_id] => 137  
                                                    [link_title] => Newsletter  
                                                    [site_type] => 1  
                                                )  
          
                                    [site_id] => 137  
                                    [parent_id] => 1  
                                    [link_title] => freie Seiten  
                                    [site_type] => 1  
                                )  
                            [2503] => Array  
                                (  
                                    [children] => Array  
                                        (  
                                            [138] => Array  
                                                (  
                                                    [site_id] => 138  
                                                    [parent_id] => 2503  
                                                    [link_title] => Impressum  
                                                    [site_type] => 1  
                                                )  
          
                                            [139] => Array  
                                                (  
                                                    [site_id] => 139  
                                                    [parent_id] => 2503  
                                                    [link_title] => Datenschutz  
                                                    [site_type] => 1  
                                                )  
          
                                        )  
          
                                    [site_id] => 2503  
                                    [parent_id] => 1  
                                    [link_title] => Footer  
                                    [site_type] => 2  
                                )  
                    [site_id] => 1  
                    [parent_id] => 0  
                    [link_title] => Home  
                    [site_type] => 5  
                )  
            [2700] => Array  
                (  
                    [site_id] => 2700  
                    [parent_id] => 0  
                    [link_title] => Aufgaben  
                    [site_type] => 7  
                )  
          
        )
        

        nachher:
        --------

        Array  
        (  
            [1] => Array  
                (  
                    [value] => 1  
                    [text] => Home  
                    [site_type] => 5  
                )  
          
            [137] => Array  
                (  
                    [value] => 137  
                    [text] =>    freie Seiten  
                    [site_type] => 1  
                )  
          
            [149] => Array  
                (  
                    [value] => 149  
                    [text] =>       Newsletter  
                    [site_type] => 1  
                )  
          
            [2503] => Array  
                (  
                    [value] => 2503  
                    [text] =>    Footer  
                    [site_type] => 2  
                )  
          
            [138] => Array  
                (  
                    [value] => 138  
                    [text] =>       Impressum  
                    [site_type] => 1  
                )  
          
            [139] => Array  
                (  
                    [value] => 139  
                    [text] =>       Datenschutz  
                    [site_type] => 1  
                )  
          
            [2700] => Array  
                (  
                    [value] => 2700  
                    [text] => Aufgaben  
                    [site_type] => 7  
                )  
          
        )  
        
        

        Wie löst man das optimalerweise. Im, in meinen Augen besten Fall sogar ohne des rekursiven Aufruf einer Funktion? Das ganze ist prozedural programmiert.

        danke für Tipps und

        beste gruesse,
        heinetz

        1. Hallo,

          ich habe versucht, den Code für das Beispiel hier auf das Wesentliche zu reduzieren, damit er für sich spricht und damit ohne Kommentare auskommt.

          es ist eine weitverbreitete Illusion, dass irgendwelcher Code, der über die Trivialität von "Hello world!" hinausgeht, ohne Kommentare auskommt.

          Array

          (
              [1] => Array
                  (
                      [value] => 1
                      [text] => Home
                      [site_type] => 5
                  )

          [137] => Array
                  (
                      [value] => 137
                      [text] =>    freie Seiten

          Sieht nach je drei "Leerzeichen" je Ebene aus. Ermittle die Tiefe

          [...]

            
          
          > Wie löst man das optimalerweise. Im, in meinen Augen besten Fall sogar ohne des rekursiven Aufruf einer Funktion? Das ganze ist prozedural programmiert.  
            
          [Tree-traversal in preorder](http://en.wikipedia.org/wiki/Tree_traversal#Depth-first_Traversal). Variation zum binären Baum ist die, dass solange "Kindbäume" eines Knoten vorhanden sind, der nächste Geschwisterteilbaum abgearbeitet werden muss.  
            
          [Iterative Lösungen](http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal) gibts selbstverständlich auch.  
            
            
          Freundliche Grüße  
            
          Vinzenz
          
        2. Hallo,

          Wie lässt sich die Aufgabe besser lösen?

          Es gibt ein multidimensionales Array, dass eine Baumstruktur abbildet und dessen Tiefe variabel ist und ich benötige ein eindimesionales Array, das eine Information enthält, die irgendwie den, ich nenne es mal 'Pfad' abbildet. In dem folgenden Beispiel wird nicht der Pfad, sondern nur die "Tiefe" eines Elements, die es in dem Ausgangsarray hatte, abgebildet.

          und zwar durch Deine drei Leerzeichen :-)

          vorher:

          Array

          (
              [1] => Array
                  (
                      [children] => Array
                          (
                              [137] => Array
                                  (
                                      [children] => Array
                                          (
                                              [149] => Array
                                                  (
                                                      [site_id] => 149
                                                      [parent_id] => 137
                                                      [link_title] => Newsletter
                                                      [site_type] => 1
                                                  )

          [site_id] => 137
                                      [parent_id] => 1
                                      [link_title] => freie Seiten
                                      [site_type] => 1
                                  )
                              [2503] => Array
                                  (
                                      [children] => Array
                                          (
                                              [138] => Array
                                                  (
                                                      [site_id] => 138
                                                      [parent_id] => 2503
                                                      [link_title] => Impressum
                                                      [site_type] => 1
                                                  )

          [139] => Array
                                                  (
                                                      [site_id] => 139
                                                      [parent_id] => 2503
                                                      [link_title] => Datenschutz
                                                      [site_type] => 1
                                                  )

          )

          [site_id] => 2503
                                      [parent_id] => 1
                                      [link_title] => Footer
                                      [site_type] => 2
                                  )
                      [site_id] => 1
                      [parent_id] => 0
                      [link_title] => Home
                      [site_type] => 5
                  )
              [2700] => Array
                  (
                      [site_id] => 2700
                      [parent_id] => 0
                      [link_title] => Aufgaben
                      [site_type] => 7
                  )

          )

          
          >   
          > nachher:  
          > --------  
          > ~~~php
          
          Array  
          
          > (  
          >     [1] => Array  
          >         (  
          >             [value] => 1  
          >             [text] => Home  
          >             [site_type] => 5  
          >         )  
          >   
          >     [137] => Array  
          >         (  
          >             [value] => 137  
          >             [text] =>    freie Seiten  
          >             [site_type] => 1  
          >         )  
          >   
          >     [149] => Array  
          >         (  
          >             [value] => 149  
          >             [text] =>       Newsletter  
          >             [site_type] => 1  
          >         )  
          >   
          >     [2503] => Array  
          >         (  
          >             [value] => 2503  
          >             [text] =>    Footer  
          >             [site_type] => 2  
          >         )  
          >   
          >     [138] => Array  
          >         (  
          >             [value] => 138  
          >             [text] =>       Impressum  
          >             [site_type] => 1  
          >         )  
          >   
          >     [139] => Array  
          >         (  
          >             [value] => 139  
          >             [text] =>       Datenschutz  
          >             [site_type] => 1  
          >         )  
          >   
          >     [2700] => Array  
          >         (  
          >             [value] => 2700  
          >             [text] => Aufgaben  
          >             [site_type] => 7  
          >         )  
          >   
          > )  
          > 
          
          

          ich werd' statt Deiner Leerzeichen die Tiefe mit ausgeben.

          Wie löst man das optimalerweise.

          Rekursiv :-)

          OK, werden wir konkret:

          a) Du hast nicht etwa einen Baum vor Dir, sondern ein Array von Bäumen.
             Ein Baum hat [1] als Wurzel, der zweite [2700]. Das kann ein übler
             Fallstrick sein und ist mir auch erst bei der intensiveren Beschäftigung
             mit Deinen Daten aufgegangen.

          b) Dies erkennt man daran, dass sich diese Elemente nicht in einem Array mit
             dem Index 'children' befinden. Sie sind somit nicht Kind einer gemeinsamen
             Wurzel.

          c) Die Kindbäume befinden sich im Arrayelement mit dem Schlüssel 'children'.
             Gibt es keine Kinder, so ist dieses Element nicht vorhanden. Das Element
             enthält als Wert ein Array.

          d) Für die Umsetzung ist es positiv, dass sich der Arrayindex im Arrayeintrag
             mit dem Index 'site_id' wiederfindet. Andernfalls müsste man diesen beim
             Funktionsaufruf mit übergeben.

          e) Durchlaufen eines Baumes, dessen Knoten mehrere Kinder haben können erfolgt
             in Preorder mit:

          i)  Besuche den Wurzelknoten
              ii) Besuche alle Kindbäume

          ist also noch einfacher formuliert als das Durchlaufen eines binären Baumes.

          1. Schritt: einfaches Durchlaufen eines Baumes
             Zur Überprüfung geben wir einfach die jeweilige 'site_id' des aktuell
             besuchten Knotens aus:

          # Einfaches Durchlaufen eines Baumes  
          # Übergabe: Wurzelknoten des Baumes  
          # Ausgabe:  id des besuchten Knotens  
          function tree_traversal_simple($root) {  
              # besuche aktuellen Knoten. Jeder Knoten ist ein Array.  
              # im Beispiel: gebe das site_id-Element des Knotens aus  
              echo htmlspecialchars($root['site_id']), "<br>\n";  
            
              # Besuche die Kinder (wenn vorhanden)  
              if (isset($root['children']) && is_array($root['children'])) {  
                  # Kinder sind die Array-Elemente des children-Elementes  
                  # des aktuellen Knotens.  
                  foreach($root['children'] as $subtree => $value) {  
                      tree_traversal_simple($value);  
                  }  
              }		  
          }
          

          Aufruf

          # Achtung: die Datenstruktur ist kein Baum, sondern ein Array von Bäumen!  
          # Dieses sei in der Variablen $mydata enthalten.  
          foreach($mydata as $root => $value) {  
              tree_traversal_simple($value);  
          };
          

          Ausgabe:

          1
          137
          149
          2503
          138
          139
          2700

          2. Schritt: Tiefe zusätzlich ermitteln und ausgeben

          function tree_traversal_with_depth($root, $depth) {  
              # besuche Wurzel  
              # "Wert" der Wurzel  
              echo "Knoten: ", htmlspecialchars($root['site_id']), "<br>\n";  
              # aktuelle "Tiefe"  
              echo "Tiefe: ", htmlspecialchars($depth), "<br>\n";  
            
              # besuche Kinder  
              # ganz analog zur ersten Funktion  
              # die Kinder sind eine Ebene tiefer angesiedelt  
              if (isset($root['children']) && is_array($root['children'])) {  
                  foreach($root['children'] as $subtree => $value) {  
                      # wir gehen eine Etage tiefer  
                      tree_traversal_with_depth($value, $depth + 1);  
                  }  
              }		  
          }
          

          Aufruf

            
          foreach($mydata as $root => $value) {  
              # wir starten in der nullten Ebene  
              tree_traversal_with_depth($value, 0);  
          };
          

          Ausgabe:

          Knoten: 1
          Tiefe: 0
          Knoten: 137
          Tiefe: 1
          Knoten: 149
          Tiefe: 2
          Knoten: 2503
          Tiefe: 1
          Knoten: 138
          Tiefe: 2
          Knoten: 139
          Tiefe: 2
          Knoten: 2700
          Tiefe: 0

          Nun möchtest Du jedoch statt einer Ausgabe ein recht flaches Array als Ergebnis haben. Daraus folgt: Die Funktion muss ein Array zurückgeben. Im Gegensatz zu C können viele Programmiersprachen, darunter auch PHP, problemlos ein Array zurückgeben.

          function tree_traversal($root, $depth) {  
              # Ergebnis soll ein Array sein: also geben wir ein Array zurück  
              $result = array();  
            
              # wir nutzen aus, dass der gewünschte Arrayschlüssel im Knotenelement  
              # mit dem Schlüssel "site_id" steht.  
              $result[$root['site_id']] = array(  
                                  'value' => $root['site_id'],  
                                  'text'  => $root['link_title'],  
                                  'tiefe' => $depth,  
                                  'site_type' => $root['site_id']  
                          );  
              # Die weiteren Schlüssel habe ich Deiner vorgabe entnommen.  
              # Statt der führenden Leerzeichen führe ich die erreichte Tiefe  
              # in einem zusätzlichen Element mit.  
            
              # besuche die Kinder auf bekannte Weise  
              if (isset($root['children']) && is_array($root['children'])) {  
                  foreach($root['children'] as $subtree => $value) {  
                      # Wir hängen bei jedem Schritt das vom Durchlaufen des  
                      # Kindbaumes zurückgegebene Array an unser eigenes Array an.  
                      # Damit unsere numerischen Schlüssel erhalten bleiben, nutzen wir  
                      # nicht [link:http://www.php.net/manual/en/function.array-merge.php@title=array_merge()] sondern den [link:http://www.php.net/manual/en/language.operators.array.php@title=Array-Operator] +.  
                      # Dabei kommt uns zugute, dass die Schlüssel in der gesamten  
                      # Datenstruktur eindeutig sind.  
                      $result = $result + tree_traversal($value, $depth + 1);  
                  }  
              }  
              # Nicht vergessen: das Array zurückzugeben.  
              [link:http://de.php.net/manual/en/function.return.php@title=return] $result;  
          }
          

          Aufruf:

            
          # Wir bauen das Ergebnisarray in der Variablen $new_array zusammen  
          $new_array = array();  
          foreach($mydata as $root => $value) {  
              # Wir starten in jedem Wurzelknoten mit einem leeren Pfad  
              $new_array = $new_array + tree_traversal_with_path($value, '');  
          };  
          echo "<pre>\n";  
          print_r($new_array);  
          echo "</pre>";  
          
          

          Ausgabe

          entspricht Deiner Vorgabe.

          Statt einfach nur die Tiefe zu ermitteln, im jeweiligen Element 'text' den Pfad zusammenzubauen, solltest Du jetzt selbst hinbekommen. Das Beseitigen der Rekursion überlasse ich Dir ebenfalls gern zur Übung ...

          Freundliche Grüße

          Vinzenz

          1. Hallo Gunnar™,

            Schlamperei, sowas! Das muss natürlich wie folgt lauten:

            Aufruf:

              
            # Wir bauen das Ergebnisarray in der Variablen $new_array zusammen  
            $new_array = array();  
            foreach($mydata as $root => $value) {  
                # Wir starten in jedem Wurzelknoten mit einem leeren Pfad  
                $new_array = $new_array + tree_traversal_with_path($value, '');  
            };  
            echo "<pre>\n";  
            # Bitte Kontextwechsel beachten!  
            echo htmlspecialchars([link:http://de2.php.net/manual/en/function.print-r.php@title=print_r]($new_array), true);  
            echo "</pre>";  
            
            

            Ach ja: ich setze hier gnadenlos voraus, dass Deine Datenstruktur keine Fehler enthält ...

            Freundliche Grüße

            Vinzenz

          2. Hallo,

            zuerst mal vielen Dank für diese ausführliche Beschreibung!

            Im Vertrauen darauf, dass das sicher sauberer gelöst ist, als meine Variante ... schon der Kommentare wegen ;) ... werde ich das zur Übung umsetzen. Allerdings muss ich gestehen, dass ich drei Dinge, die mir nicht klar sind:

            die beiden Elemente [1] und [2700] haben faktisch eine Wurzel [0] und ich könnte daher auch ein Array (0=>array(1=>..., 2700=>...)) an die Funktion übergeben. Inwiefern würde das die Sache vereinfachen?

            Mein Array 'vorher' ist aus einem flacheren 'nochdavon' entstanden, dass in etwa so aussah:

            Array
            (
                [0] => Array
                    (
                        [site_id] => 1
                        [parent_id] => 0
                        [link_title] => Home
                    )

            [1] => Array
                    (
                        [site_id] => 137
                        [parent_id] => 1
                        [link_title] => <freie Seiten>
                    )

            [2] => Array
                    (
                        [site_id] => 149
                        [parent_id] => 137
                        [link_title] => Newsletter
                    )

            [3] => Array
                    (
                        [site_id] => 2503
                        [parent_id] => 1
                        [link_title] => Footer
                    )

            [4] => Array
                    (
                        [site_id] => 138
                        [parent_id] => 2503
                        [link_title] => Impressum
                    )

            [5] => Array
                    (
                        [site_id] => 139
                        [parent_id] => 2503
                        [link_title] => Datenschutz
                    )

            [6] => Array
                    (
                        [site_id] => 2700
                        [parent_id] => 0
                        [link_title] => Aufgaben
                    )
            )

            ... und im ersten Schritt in das Array 'vorher' umgewandendelt wurde, um daraus ein Array 'nachher', dass Informationen über die Struktur enthält, machen zu können. Diese Informationen sind zum Einen die Reihenfolge der Elemente und zum Anderen die Tiefe, die ich mit 3 Leezeichen darstelle. Jetzt benötige ich nicht mehr nur die Tiefe, sondern den ganzen Pfad bis zur Wurzel als Element. Kommt man dann wohl immernoch ohne global definiertes array aus?

            Beseitigen der Rekursion überlasse ich Dir ebenfalls gern zur Übung ...

            Wie soll ich das verstehen?

            Zugegeben, der Weg erst aus einem zweidimensionale Array ein tief verschachteltes zu machen, um dass dann wieder auf zwei Dimensionen zu reduzieren, kann einem schon komisch vorkommen, aber es ist der einzige Weg, den ich gefunden habe, um alle Datensätze meiner in der DB gespeicherten Parent/Child-Struktur auf einmal auszulesen, um die Struktur des Baums im Ganzen darstellen und so auf rekursive Select-Statements verzichten zu können.

            beste gruesse,
            heinetz

            1. Hallo,

              Im Vertrauen darauf, dass das sicher sauberer gelöst ist, als meine Variante ... schon der Kommentare wegen ;)

              tja, bei copy & paste unterlaufen einem auch mal Fehler.
              Der Aufruf bei meiner dritten Funktion ist in Wirklichkeit der Aufruf bei der vierten Funktion (die ich Dir vorenthalten habe).

              Korrekt wäre

              # Wir bauen das Ergebnisarray in der Variablen $new_array zusammen  
              $new_array = array();  
              foreach($mydata as $root => $value) {  
                  # Wir starten in jedem Wurzelknoten mit der Tiefe 0  
                  $new_array = $new_array + tree_traversal($value, 0);  
              };  
              echo "<pre>\n";  
              print_r($new_array);  
              echo "</pre>";  
              
              

              ... werde ich das zur Übung umsetzen. Allerdings muss ich gestehen, dass ich drei Dinge, die mir nicht klar sind:

              die beiden Elemente [1] und [2700] haben faktisch eine Wurzel [0] und ich könnte daher auch ein Array (0=>array(1=>..., 2700=>...)) an die Funktion übergeben. Inwiefern würde das die Sache vereinfachen?

              so gar nicht:
              Für den Wurzelknoten eines Gesamtbaumes gilt, dass er sinnvollerweise die *gleiche* Struktur aufweist, wie die Wurzelknoten der Teilbäume. Sonst ist eine gesonderte Behandlung der Wurzel erforderlich, die den Code nur komplexer macht und unnötig aufbläht, d.h. der Gesamtwurzelknoten *muss* ein Array sein, die gleichen Elemente enthalten wie die Kindknoten (mit sinnvollen Werten) und vor allem müssen die Kindbäume (gemäß b) im Arrayelement mit dem Schlüssel 'children' enthalten sein.

              Ich sehe mit der derzeitigen Konstruktion kein besonderes Problem. Statt eines einfachen rekursiven Aufrufs, startest Du mit einer kleinen for-each-Schleife. Du musst Dir nur dieses Umstandes bewußt sein.

              Mein Array 'vorher' ist aus einem flacheren 'nochdavon' entstanden, dass in etwa so aussah:

              Array
              (
                  [0] => Array
                      (
                          [site_id] => 1
                          [parent_id] => 0
                          [link_title] => Home
                      )

              [1] => Array
                      (
                          [site_id] => 137
                          [parent_id] => 1
                          [link_title] => <freie Seiten>
                      )

              [2] => Array
                      (
                          [site_id] => 149
                          [parent_id] => 137
                          [link_title] => Newsletter
                      )

              [3] => Array
                      (
                          [site_id] => 2503
                          [parent_id] => 1
                          [link_title] => Footer
                      )

              [4] => Array
                      (
                          [site_id] => 138
                          [parent_id] => 2503
                          [link_title] => Impressum
                      )

              [5] => Array
                      (
                          [site_id] => 139
                          [parent_id] => 2503
                          [link_title] => Datenschutz
                      )

              [6] => Array
                      (
                          [site_id] => 2700
                          [parent_id] => 0
                          [link_title] => Aufgaben
                      )
              )

              ... und im ersten Schritt in das Array 'vorher' umgewandendelt wurde, um daraus ein Array 'nachher', dass Informationen über die Struktur enthält, machen zu können. Diese Informationen sind zum Einen die Reihenfolge der Elemente und zum Anderen die Tiefe, die ich mit 3 Leezeichen darstelle. Jetzt benötige ich nicht mehr nur die Tiefe, sondern den ganzen Pfad bis zur Wurzel als Element. Kommt man dann wohl immernoch ohne global definiertes array aus?

              ja klar: mit meiner vierten Funktion

              tree_traversal_with_path($root, $path)

              Dazu hast Du in den Zielarray-Elementen sinnvollerweise ein Arrayelement mit dem Schlüssel 'path' :-)

              Beseitigen der Rekursion überlasse ich Dir ebenfalls gern zur Übung ...

              Wie soll ich das verstehen?

              Na, Du wolltest doch idealerweise eine Lösung ohne Rekursion. Das geht, das ist klar - weil es für jede rekursive Lösung auch eine gleichwertige iterative Lösung gibt. Hier mit durchaus deutlichem Mehraufwand gegenüber der rekursiven Lösung.

              Zugegeben, der Weg erst aus einem zweidimensionale Array ein tief verschachteltes zu machen, um dass dann wieder auf zwei Dimensionen zu reduzieren, kann einem schon komisch vorkommen, aber es ist der einzige Weg, den ich gefunden habe, um alle Datensätze meiner in der DB gespeicherten Parent/Child-Struktur auf einmal auszulesen, um die Struktur des Baums im Ganzen darstellen und so auf rekursive Select-Statements verzichten zu können.

              Nicht unbedingt. Es gibt ein extrem elegantes, effizientes Sortierverfahren, dass genauso vorgeht: Heapsort.

              Nachdem Du Deinen Baum aufgebaut hast, kannst Du - wie gezeigt - diesen einfach in PreOrder durchlaufen ohne auch nur einen Knoten zweimal zu besuchen, um das von Dir gewünschte Ergebnis zu erhalten.

              Freundliche Grüße

              Vinzenz

              1. Hallo,

                tja, bei copy & paste unterlaufen einem auch mal Fehler.
                Der Aufruf bei meiner dritten Funktion ist in Wirklichkeit der Aufruf bei der vierten Funktion (die ich Dir vorenthalten habe).

                Ich hatte dein Beispiel mal umgesetzt, um auszuprobieren, ob ich den Pfad in das Array bekomme und es lief erstmal nicht. Du glaubst nicht, welche Freude mir diese Fehler gemacht hat, nachdem ich ihn gefunden hatte ;)

                Ich sehe mit der derzeitigen Konstruktion kein besonderes Problem.

                Stimmt, ich habe mich dennoch für dafür entschieden, die gesonderte Behandlung der Wurzel in die Funktion einzubauen und auf die Scheife beim Aufruf zu verzichten, weil ich es übersichtlicher finde:

                #Funktion
                function tree_traversal($root, $path) {
                 $result = array();

                if (isset($root['site_id'])) {
                  $path[]= $root['link_title'];
                  $result[$root['site_id']] = array(
                   'value' => $root['site_id'],
                   'text'  => $root['link_title'],
                   'pfad' => $path
                  );
                 }

                if (isset($root['children']) && is_array($root['children'])) {
                  foreach($root['children'] as $subtree => $value) {
                   $result = $result + tree_traversal($value, $path);
                  }
                 }
                 return $result;
                }

                #Aufruf
                $new_array = tree_traversal(array('children'=>$temp), array());

                ja klar: mit meiner vierten Funktion

                ;)

                Nicht unbedingt. Es gibt ein extrem elegantes, effizientes Sortierverfahren, dass genauso vorgeht: Heapsort.

                Danke für den Hinweis. Damit muss ich mich länger beschäftigen. Heute will ich endlich "tree_traversal_with_path" abgeschlossen haben ...

                besten Dank und gruesse,
                heinetz

  3. Hello,

    mein PHP-Skript liefert mir zwar das Ergebnis, das ich erwarte. Dennoch fühle ich mich damit unwohl, weil ich nicht genau weiss, was passiert ;(

    function flatten_array (&array){

    global $my_new_array;
    foreach ($array as $key => &$value){
      $my_new_array[$key] = $value['something'];
      if ($value['children']) {
       flatten_array($value['children']);
      }
    }
    return $my_new_array;
    }

    function test (){
    global $my_old_array;
    return flatten_array($my_old_array);
    }

      
      
    Du benutzt eine hässliche Abfragemethode, ob es ['children'] gibt, bzw. ob $value ein Skalar oder ein Array ist.  
      
    Außerdem ist die Gefahr sehr groß, dass Du im Ergebnisarray bereits vorhandene Elemente wieder überschreibst, wenn der der Schlüssel in unterschiedlichen Zweigen mehrfach vorkommt.  
      
      
      
    
    > Wie läuft das ab? 'Wartet' die Funktion test(), bis die Funktion flatten\_array() irgendwann irendwas zurückgibt? Oder ist das hier grundlegend falsch?  
      
    "Warten" ist hier ein irreführender Ausdruck. In einem Single-Thread-System gibt es immer nur eine aktuelle Programmstelle, die abgearbeitet wird. Der Programmzeiger wird also durch die Steuerinformationen strukturiert durch die Programmteile geführt. Unterbrechungen lassen wir mal außer Betracht.  
      
    Wenn Du also eine rekursive Funktion hast, dann wird der Programmzeiger in die Startfunktion gestellt, eine neue Instanz der Funktion im Speicher erzeugt, der Programmzeiger nachgeführt und diese Instanz abgearbeitet. Führt die Abarbeitung direkt zum Ergebnis, wird \_keine\_ neue Instanz mehr erzeugt, wird das Ergebnis zurückgegeben und der Speicher für die abgearbeitete Instanz wieder freigegeben.  
      
    Die Funktion Test "wartet" also nicht, sondern der Programmzeiger ist einfach noch nicht zurück von seinem Marsch durch den Speicher.  
      
    Anders ist das in Multithreading-Umgebungen. Da muss man sehr genau wissen, ob ein neuer Thread (Programmzeiger) aufgemacht wird, wenn eine Funktion aufgerufen wird.  
      
      
      
      
      
    Liebe Grüße aus dem schönen Oberharz  
      
      
    Tom vom Berg  
    ![](http://selfhtml.bitworks.de/Virencheck.gif)  
      
    
    -- 
     ☻\_  
    /▌  
    / \ Nur selber lernen macht schlau  
    <http://bergpost.annerschbarrich.de>