Einen Hirarchischen-Baum aus einer Liste erstellen

[Prophet05]

Hi,

Ich habe eine Liste in der es folgendes Felder gibt:
-> ID
-> Parent ID
-> Title

Nun will ich diese Liste mit hilfe eines schnellen PHP algorhytmus in eine Baum verwandeln.

Hier ein beispiel:

Array[0] = [1;0;Element1];
Array[1] = [2;1;Element2];
Array[2] = [3;2;Element3];
Array[3] = [4;2;Element4];
Array[4] = [5;3;Element5];
Array[5] = [6;3;Element6];

wird zu:

Array[1] = Element1;
Array[1][2] = Element2;
Array[1][2][3] = Element3;
Array[1][2][3][5] = Element5;
Array[1][2][3][6] = Element6;
Array[1][2][4] = Element4;

Ich hoffe es wird klar was ich suche...

EDIT: Alle daten werden aus einer MySQL Datenbank geladen. Wenn es also damit vorarbeit zu leisten gilt oder die arbeit komplett dort erledigt werden kann sind mir solche lösungen auch willkommen!

 

[firstlord18]

irgendwie verstehe ich nicht so recht, wie du von

 Array[4] = [5;4;Element5];
 Array[5] = [6;4;Element6];

auf

 Array[1][2][3][5] = Element5;
 Array[1][2][3][6] = Element6;

kommst ^^

 

[Prophet05]

Ok ich habe mich verschrieben ist nun korrigiert

 

[firstlord18]

Hm, hatte irgendwie sowas gedacht:

function disarrange($ary, $key = '', $val = '', $usekey = false)
{
	static $neu = array();
	
	if($usekey) {
		if(isset($ary[$key])) {
			$neu[] = $ary[$key];
			return disarrange($ary[$key], $val, $key, true);
		}
		else	
			$neu[$key] = $val;
	}
	else {	
		foreach($ary as $k => $val) {
			$e = explode(";", $val);
			return disarrange($ary, $e[1], $e[2], true);
		}	
	}	
	return $neu;
}
 
 $Array = array();
 $Array[0] = "1;0;Element1";
 $Array[1] = "2;1;Element2";
 $Array[2] = "3;2;Element3";
 $Array[3] = "4;2;Element4";
 $Array[4] = "5;3;Element5";
 $Array[5] = "6;3;Element6";
 
 $neu = disarrange($Array);

gibt für mich irgendwie nen logischen Inhalt, gibt aber leider TImeout ... vllt hab ich zu später Stunde was übersehn ...

 

[Matthias Reitinger]

Dieses Problem ließe sich sehr schön mittels Referenzen lösen:

<?php

$inputArray = array(
	array( 'ID' => 1, 'parentID' => 0, 'title' => 'Element1' ),
	array( 'ID' => 2, 'parentID' => 1, 'title' => 'Element2' ),
	array( 'ID' => 3, 'parentID' => 2, 'title' => 'Element3' ),
	array( 'ID' => 4, 'parentID' => 2, 'title' => 'Element4' ),
	array( 'ID' => 5, 'parentID' => 3, 'title' => 'Element5' ),
	array( 'ID' => 6, 'parentID' => 3, 'title' => 'Element6' ),
);

$outputArray = array();
$nodeRefs = array(0 => &$outputArray);

foreach ($inputArray as $element) {
	$parent = &$nodeRefs[$element['parentID']];
	$parent[$element['ID']] = array('title' => $element['title']);
	$nodeRefs[$element['ID']] = &$parent[$element['ID']];
}

print_r($outputArray);

?>

Eine Alternative wäre die Verwendung der Methode „Modified Preorder Tree Traversal“.

 

[firstlord18]

wow, man geil
Ich würde das nur gerne verstehen :/
Mit den Referenzen etc ist das total schwer, finde ich :/

 

[Prophet05]

Wirklich verstehen tue ich es auch nicht... aber danke

 

[Matthias Reitinger]

Na gut, dann werde ich jetzt mal hoffentlich für Erleuchtung sorgen

Referenzen an sich sind eigentlich nicht schwer zu verstehen. Man muss sich lediglich vorstellen, dass eine Variable nur auf ein bestimmtes Objekt im Speicher verweist (ein Integer, ein String, ein Array etc.).

       ___
$a -> |Obj|

Eine Referenz ist nun nichts anderes, als eine weitere Variable, die auf dasselbe Objekt zeigt:

       ___
$a -> |Obj| <- $b

Umgesetzt in PHP-Code sähe das so aus:

<?php

$a = 'foo';  // $a verweist auf den String 'foo' im Speicher
$b = &$a;    // $b verweist nun auf denselben String!

echo $b;     // Gibt "foo" aus.
$b .= 'bar'; // Der String, auf den $b zeigt, wird verändert

echo $a;     // Gibt "foobar" aus, da $a ja auf denselben String verweist

?>

Mit dieser Vorstellung, dass eine Variable nur auf einen Speicherbereich verweist, lässt sich mein Quellcode auch recht einfach erklären:

• $outputArray soll am Ende die in ein multidimensionales Array abgebildete Hierarchie enthalten
• $nodeRefs wird nach und nach mit Referenzen auf jedes einzelne Element der Hierarchie gefüllt, indiziert durch die jeweilige ID des Elements ($nodeRefs[4] verweist also auf das Element mit der ID 4)
• Da $outputArray die „Wurzel“ der Hierarchie ist, muss $nodeRefs[0] darauf verweisen (bereits in der Arrayinitialisierung festgelegt)
• In einer Schleife werden alle Elemente aus $inputArray durchlaufen. Für jedes Element wird folgendes erledigt:
  • Eine Referenz $parent auf das Elternelement aus $outputArray wird aus der Liste $nodeRefs geholt (über die ID des Elternelements)
  • Es wird ein neues Element für $outputArray erzeugt (array('title' => $element['title']))
  • Dieses Element wird dem Elternelement untergeordnet (über die Referenz $parent)
  • Die Liste $nodeRefs wird um eine Referenz auf das neu erzeugte Element erweitert
• Fertig!

Das klingt jetzt beim ersten Durchlesen vielleicht verwirrend, aber ergibt eigentlich schon Sinn

Wenn noch Unklarheiten bestehen, dann fragt einfach.

Grüße,
Matthias

 

[firstlord18]

Ok, die Referenzen kann ich verstehen, der Rest ist mir noch schwer einleuchtend :/
Egal, ich versuchs einfach

 

[Prophet05]

Mir geht es genauso