Knifflige rekursive Funktion, PHP

Galanos

Aktives Mitglied
Thread Starter
Dabei seit
19.12.2005
Beiträge
625
Reaktionspunkte
23
Hallo zusammen :)

Okay, vielleicht nicht ganz so knifflig fuer erfahrene Programmierer, aber auf jeden Fall fuer mich. Ich bin seit Ende letzten Jahres dabei, einen kleinen Shop fuer meine Frau zu konzipieren und zu schreiben. Den kompletten gestrigen Feiertag habe ich mich mit diesem Problem rumgeschlagen und bin letztendlich ziemlich gefrustet ins Bett gegangen. Vielleicht ist einer von euch so nett, sich in die Funktion hineinzudenken und kann mir sagen, an welcher Stelle ich den Denkfehler habe (oder einfach nur zu doof bin ;)).

Folgendes: Der Shop hat ca. 70 Kategorien, davon 6 Kategorien hoechster Ordnung, also in der Hierarchie ganz oben. Diese 6 Kategorien haben eine unbestimmte Anzahl an Kind-, Enkel-, Urenkel-, usw.-Kategorien, wovon jede eine unbestimmte Anzahl weiterer Unterkategorien hat. Also eine simple Baumhierarchie.

Das Ganze ist in PHP und MySQL realisiert. Fuer meine Funktion greife ich nur auf die Tabelle "categories" zu.

Um die Kategorien zu strukturieren, z. B. fuer mein Navigationsmenue, habe ich jeder Kategorie ihre jeweilige Elternkategorie hinterlegt ("cat_parent_id"). Die 6 Oberkategorien haben als Eltern-ID "NULL". Somit kann ich abfragen, fuer welche Kategorien "X" es keine weiteren Kind-Kategorien gibt, die "X" als Eltern-ID aufweisen, und bekomme die Kategorien, die in der Hierarchie zuunterst stehen. Diese Kategorien beinhalten letztendlich die Artikel.

Wenn jetzt eine Kategorie ausgewaehlt wird, sollen alle Artikel angezeigt werden, die dieser und allen Kindeskinder-Kategorien zugeordnet sind. Kleines Beispiel:
Code:
- Lebensmittel (Kategorie: 4, Eltern-ID: NULL)
	- Getraenke (Kategorie: 17, Eltern-ID: 4)
		- Wasser (Kategorie: 23, Eltern-ID: 17)
			(jede Menge Artikel)
		- Wein (Kategorie: 24, Eltern-ID: 17)
			(jede Menge Artikel)
	- Essen (Kategorie: 18, Eltern-ID: 4)
		(jede Menge Artikel)
Dafuer muss ich also alle Unterkategorien der gewaehlten Kategorie herausfinden. Ich habe versucht, dies mit einer rekursiven Funktion zu bewerkstelligen. Denn das Problem ist, dass die Tiefe, in der die Hierarchie durchsucht werden muss, niemals bekannt ist. Dem Script kann ich nur sagen, dass es aufhoeren kann, wenn fuer die untersuchte Kategorie keine Kind-Kategorien mehr zu finden sind.

Ich habe die Funktion, vor allem die Erfassung fuer die Ausgabe, mehrfach umgestellt. Der folgende Code ist der Versuch, bei dem ich das Gefuehl habe, dass er im Ansatz der "richtigste" ist, auch wenn er nur einen leeren Array ausgibt:
PHP:
<?php	
	function ld_get_descendants($testarray)
	{	
		global $ld_connection;
		
		foreach($testarray as $key => $value)
		{	
			global $testarray_ausgabe;

			$ld_curr_result = $ld_connection->query(sprintf("SELECT cat_id FROM categories WHERE cat_parent_id = %s", mysql_real_escape_string($value)));
				
			while($ld_curr_result_row = $ld_curr_result->fetchRow(DB_FETCHMODE_ASSOC))
			{
				$newarray[] = $ld_curr_result_row['cat_id'];

				if($ld_curr_result->numRows() > 0)
				{
					ld_get_descendants($newarray);
				} else {
					$testarray_ausgabe .= $ld_curr_result_row['cat_id'];
					$testarray_ausgabe .= ",";
				}
			}
			
		}
		return $testarray_ausgabe;
	}	
	
	$ausgabe = explode(",", ld_get_descendants(array(0 => 5)));
	print_r($ausgabe);
?>
"$ld_connection" ist eine PEAR-DB-Klasse und wird ausserhalb der Funktion definiert, funktioniert aber.

In meiner Datenbank-Tabelle "categories" weisen die Kategorien "55", "56", "57" und "58" die "5" als Eltern-ID auf. Diese 4 Kind-Kategorien enthalten, bis auf "56", keine Kind-Kategorien mehr, enthalten also Artikel. "56" hat "60", "61" und "62" als Kind-Kategorien, diese wiederum enhalten nur noch Artikel. Die Hierarchie ist also:
Code:
- 5:
	- 55
	- 56:
		- 60
		- 61
		- 62
	- 57
	- 58
Mein Ziel ist, alle Kategorien-IDs auszugeben, die Artikel enthalten, um sie spaeter einer Datenbankabfrage zu uebergeben, um, wie gesagt, alle Artikel der gewaehlten Kategorie "5" und ihrer Kindeskinder-Kategorien anzuzeigen. Wenn die "Zwischenkategorien" (also Ueberkategorien ohne Artikel, hier "5" und "56") in die Ausgabe geraten, ist das nicht so wild. Aber auf jeden Fall benoetige ich die IDs der Kategorien, die Artikel enthalten, hier also "55", "57", "58", "60", "61" und "62".

Um die Funktion zu erklaeren:
  • die gewaehlte Kategorie wird mit "ld_get_descendants(array(0 => 5))" an die Funktion uebergeben (spaeter natuerlich dynamisch, hier zu Testzwecken fix)
  • die PEAR-DB-Verbindung wird innerhalb der Funktion verfuegbar gemacht
  • in einer foreach-Schleife wird jeder Index des uebergebenen Arrays geprueft
  • der Ausgabe-String "$testarray_ausgabe;" wird global gemacht (notwendig, um ihn in der naechsten Instanz der Funktion verfuegbar zu machen?)
  • die Kind-Kategorien der aktuellen ID werden abgefragt (die error-Abfrage habe ich mal zur besseren Uebersicht weggelassen)
  • der von der Datenbankabfrage zurueckgegebene Array wird abgeklappert
  • jede Kind-Kategorie wird als neuer Index in den Array "$newarray" gespeist
  • falls die Abfrage ueberhaupt ein Ergebnis geliefert hat, wird die aktuelle Kind-Kategorie rekursiv an die Funktion uebergeben, alles geht von vorne los
  • ansonsten wird die aktuelle Kind-Kategorie in den String "$testarray_ausgabe" gefuettert und ein Komma angesetzt
  • wenn alles fertig ist, wird dieser String zurueckgegeben, anschliessend per explode zerteilt und testhalber mal mit print_r ausgegeben
Gedacht ist, dass das Script bei jeder Kategorie, fuer die er Kind-Kategorien findet, eine neue Instanz der Funktion startet, deren Kind-Kategorien wiederum abklappert und noetigenfalls eine weitere Instanz startet. Wenn es sich nach ganz unten durchgegraben hat, soll es Schritt fuer Schritt wieder zurueckkehren und die uebrigen Kind-Kategorien der vorherigen Instanzen abarbeiten.
Waehrenddessen immer den Ausgabe-String fuettern, moeglichst ohne Doppelungen.

Ich habe irgendwo einen ganz daemlichen Fehler gemacht, oder? Muss die foreach-Schleife in eine weitere Funktion? if und while tauschen? Ich bekomme schon Kopfschmerzen, wenn ich nur den Code anschaue :(

Ich weiss, Wall of Text :( Wenn ihr bis hierhin mitgelesen habt, bin ich euch schon irre dankbar. Wenn mir jemand eine Loesung oder einen Schubser in die richtige Richtung geben kann, hat er bei mir einen gaaanz dicken Stein im Brett!

Danke vorab, Galanos
 
ja in Bäumen suchen und sortieren kann schon ganz schön fordern :)

Ich habe das auch irgendwann im Studium machen müssen, seitdem eher selten. Die Antwort kann ich Dir aus Zeitgründen leider nicht geben, wohl aber einen Link der sich mit den zug. Algorithmen befaßt. Vielleicht findest Du damit ja eine Lösung für Dein Problem:

http://www.mi.uni-koeln.de/c/mirror...n.de/~schieder/programmieren-2-ss97/tree.html
 
  • Gefällt mir
Reaktionen: Galanos
Danke dir, Wegus. Das Thema kann ein echter Hirnverdreher sein. Hat man die Schleife ausgetueftelt, ueberschreibt man versehentlich die Ausgabe. Und andersrum.

Ich habe mich nochmals in Google reingekniet und ein paar mehr oder minder taugliche Artikel dazu gefunden. Im SelfHTML-Forum wird geraten, mit Referenzen zu arbeiten, damit habe ich etwas rumexperimentiert. War aber letztendlich nicht noetig. Habe nun die if- und die while-Schleife quasi getauscht:
PHP:
	$GLOBALS["puffer"] = "";
	
	function ld_get_descendants($testarray)
	{	
		global $ld_connection;
		
		foreach($testarray as $key => $value)
		{	
			$ld_curr_result = $ld_connection->query(sprintf("SELECT cat_id FROM categories WHERE cat_parent_id = %s", mysql_real_escape_string($value)));

			if($ld_curr_result->numRows() > 0)
			{
				while($ld_curr_result_row = $ld_curr_result->fetchRow(DB_FETCHMODE_ASSOC))
					$newarray[] = $ld_curr_result_row['cat_id'];
				
				ld_get_descendants($newarray);

			} else {
				$GLOBALS["puffer"][] = $value;
			}
		}
	}
	
	ld_get_descendants(array(0 => 5));

	print_r($GLOBALS["puffer"]);
Wenn also Kinder der aktuellen Kategorie gefunden werden, wird nichts in den "Ausgabepuffer" geschrieben, sondern eine neue Instanz der Funktion geschaffen und die Kinder geprueft. Ansonsten kommt die ID der aktuellen Kategorie in den Ausgabepuffer.

Damit werden nur alle Unterkategorien ohne weitere Kinder ausgegeben, ohne "Zwischenkategorien" - was mir sogar entgegenkommt.

Okay, war ein kurzer Thread, aber vielleicht hilft das ja dem naechsten Verzweifelten ;)

Danke an alle, die sich die Muehe gemacht haben, sich in mein Problem einzulesen!
 
Zurück
Oben Unten