rekursive Logik

[heinetz]

Hallo Forum,

in meiner Datenbank speichere ich eine Baumstruktur
in etwa so:

id | parent_id
-----+----------
   1 |         0
-----+----------
   2 |         1
-----+----------
   3 |         1
-----+----------
   4 |         0
-----+----------
   5 |         4
-----+----------
   6 |         4

Wenn Root 0 ist, besteht der Baum also aus zwei Ebenen.
An oberster die id 1 mit den Unterebnen 2 und 3 und 4
mit den Unterebenen 5 und 6.

Um aus dieser Struktur eine verschachtelten Liste zu
bauen habe ich mir eine Funktion gebaut.

Etwa so:

  
  
function buildtreeList ($parentid)  
                    {  
                     global $tree;  
                     $statement = "  
                     SELECT *  
                     FROM `content`  
                     WHERE `parent_id` = ".$parentid;  
                     ...  
                     $result = mysql_query($statement);  
                     $result_num = mysql_num_rows($result);  
  
                     if ($result_num!=0)  
                       {  
                        while ($row = mysql_fetch_assoc($result))  
                             {  
                              $tree.= "<li>".$row['site_id']."</li>";  
                              buildTreeList ($row['site_id']);  
                              $str."</li>\n";  
                             }  
                        $tree.= "</ul>\n";  
                       }  
                    }  
  
buildtreeList(0);  
echo $tree;  

Wie man sieht, ruft sich die Funktion rekursiv selbst immer
wieder auf und befüllt so die Variable $tree mit einer verschachtelten
Liste. Das funktioniert soweit, aber ich will versuchen, die
Funktion umzuschreiben. Und zwar so, dass sie ein mehrdimensionales Array befüllt.

Irgendwie komme ich aber nicht auf die Idee, wie ich der
Funktion mitteile, an welcher Stelle, also Dimension des
Arrays die Elemente aus dem Resultset anhänge.

Hat jemand einen Tipp für mich ?

danke und

beste gruesse,
heinetz

[dedlfix]

Hi!

in meiner Datenbank speichere ich eine Baumstruktur
Um aus dieser Struktur eine verschachtelten Liste zu bauen habe ich mir eine Funktion gebaut.
[...]
Wie man sieht, ruft sich die Funktion rekursiv selbst immer wieder auf und befüllt so die Variable $tree mit einer verschachtelten Liste.

Soweit so schlecht. Einzelabfragen an das DBMS sollte man vermeiden. Frag lieber ddie Datensätze auf einmal ab und leg sie vorläufig in ein flaches Array. (Wenn du Teilbäume nach allen Regeln der Kunst abfragen willst, schau dir Nested Sets an. Brauchst du aber hier vermutlich nicht.) Selbst wenn du das Array mehrfach durchläufst um die Datensätze der verschiedenen Ebenen und Äste zu finden ist das effizienter als jedes Mal der DBMS-Query-Overhead.

Das funktioniert soweit, aber ich will versuchen, die Funktion umzuschreiben. Und zwar so, dass sie ein mehrdimensionales Array befüllt.

Mehrdimensional heißt für mich jeweils gleichmäßige Ausbreitung in mehr als eine Richtung. Du möchtest stattdessen eine Baumstruktur, bei der die Äste beliebig verzweigt sein können.

Irgendwie komme ich aber nicht auf die Idee, wie ich der Funktion mitteile, an welcher Stelle, also Dimension des Arrays die Elemente aus dem Resultset anhänge.

Besser wäre es, wenn du sammeln ließest. Das Wurzelelement delegiert das Zusammensuchen der Kinder an einen weiteren Funktionsaufruf. Der liefert die Kinder als Array zurück. Ein Kind verfährt ebenso mit den Kindeskindern.

Lo!

[heinetz]

hi,

Soweit so schlecht. Einzelabfragen an das DBMS sollte man vermeiden.

genaus das ist der Anlass meines Begehren:

Ich wollte die Struktur in einem Array ablegen, weil ich sie
in meinem Script mehrfach verwednen und so DB-Anfragen verweiden will.

Frag lieber ddie Datensätze auf einmal ab und leg sie vorläufig in ein flaches Array.

... was noch konsequenter ist, um die DB-Anfragen zu minimieren.

Besser wäre es, wenn du sammeln ließest. Das Wurzelelement delegiert das Zusammensuchen der Kinder an einen weiteren Funktionsaufruf. Der liefert die Kinder als Array zurück. Ein Kind verfährt ebenso mit den Kindeskindern.

... so wie ich Dich verstehe, entspricht das der Logik meines
Skripts:

Die Funktion (mal unabhänig von der DB-Abfrage) wird mit einem
Element in der Struktur als Parameter aufgerufen und soll die
Kinder des Elements herausfinden und irgendwie zurückgeben bzw.  anhängen. Die Funktion wird initial mit dem Root als Element
aufgerufen und ruft sich selbst bei jede gefundenen Kind mit
diesem als Parameter auf.

Danke, ich werde de Weg weiterverfolgen.

gruss,
heinetz

[dedlfix]

Hi!

Besser wäre es, wenn du sammeln ließest. Das Wurzelelement delegiert das Zusammensuchen der Kinder an einen weiteren Funktionsaufruf. Der liefert die Kinder als Array zurück. Ein Kind verfährt ebenso mit den Kindeskindern.
... so wie ich Dich verstehe, entspricht das der Logik meines Skripts:
Die Funktion wird initial mit dem Root als Element aufgerufen und ruft sich selbst bei jede gefundenen Kind mit diesem als Parameter auf.

Ja. Hier noch etwas ausführlicher:

Es kommt auch darauf an, wie deine Struktur letzlich genau aussieht. Zwei Arten gibt es
1. Ein Ast führt entweder zu einem Blatt oder zu einer Verzweigung mit mehreren weiteren Ästen. Informationen sind allein im Blatt enthalten.
2. Wie eben, allerdings ist auch in der Verzweigung selbst Information enthalten.

So sieht das Resultat gemäß 1 aus:

array(
  'blatt 1',
  array(
    'blatt 2',
    array(
      'blatt 3',
      'blatt 4',
    )
  )
)

Du triffst also beim Durchlaufen entweder auf einen String oder ein Array.

Nummer 2 könnte so aussehen, wenn die Informationen skalar sind (also kein Array oder Objekt).

array(
  'blatt 1' => null,
  'zweig 1' => array(
    'blatt 2' => null,
    'zweig 2' => array(
      'blatt 3' => null,
      'blatt 4' => null,
    )
  )
)

Bei nichtskalaren Informationen sähe ein Ast so aus:

array(
  'info 1' => '...',
  'info 2' => '...',
  'children' => array(...)
)

Das Zusammenbauen nach 1 geht so: Du durchläufst die Daten auf der Suche nach der aktuellen ID (fängt mit 0 an). Dazu gibt es entweder ein Blatt, was du gleich zurückgibst. (Wie du das erkennst, weiß ich nicht, das geht aus deinem OP nicht hervor.) Oder du erkennst, dass es mehrere Kinder gibt - also Einträge mit Parent-ID gleich aktueller ID - erstellst ein zunächst leeres Ergebnisarray und steigst mit der Kindes-ID in die nächste Runde ab. Wenn du alle Kinder abgeklappert hast, gibst du ds Array zurück.

Das Zusammenbauen nach 2 geht prinzipiell genauso, hat aber das Problem bei der skalaren Variante, dass eine Funktion immer nur einen Wert zurückgeben kann. Man muss also beide Werte in einer Struktur bringen und in der aufrufenden Ebene wieder auseinanderfummeln oder man übergibt den zweiten Wert per Referenz nach oben. Etwa so:

function find($id, &$children) {
  $info = ...;
  if (no_children) {
    $children = null;
  } else {
    $children = array();
    foreach (get_children($id) as $child_id) {
      $child_info = find($child_id, $grandchildren);
      $children[$child_info] = $grandchildren;
    }
  }
  return $info;
}

Lo!

[heinetz]

Hi,

1000 Dank für Deine ausführliche Anleitung !

besten gruss,
heinetz