nicht angemeldet
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