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