# Einen Hirarchischen-Baum aus einer Liste erstellen



## Prophet05 (25. Dezember 2005)

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 (26. Dezember 2005)

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 (26. Dezember 2005)

Ok ich habe mich verschrieben ist nun korrigiert


----------



## firstlord18 (26. Dezember 2005)

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 (26. Dezember 2005)

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 (26. Dezember 2005)

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


----------



## Prophet05 (26. Dezember 2005)

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


----------



## Matthias Reitinger (26. Dezember 2005)

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 (26. Dezember 2005)

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


----------



## Prophet05 (27. Dezember 2005)

Mir geht es genauso


----------



## Matthias Reitinger (27. Dezember 2005)

Welcher Schritt ist denn nicht verständlich?


----------



## firstlord18 (27. Dezember 2005)

Matthias Reitinger hat gesagt.:
			
		

> Welcher Schritt ist denn nicht verständlich?


des is halt meistens so, dass man zwar einzelne schritten ca versteht, aber den zusammenhang nicht so ganz ...

Die Referenzen verstehe ich soweit noch ...

am wenigsten verstehe ich das in der Foreach-Schleife (lol, das ist ja der Hauptteil), naja was genau macht denn das:


```
$nodeRefs[$element['ID']] = &$parent[$element['ID']];
```
</font></font>


----------



## Matthias Reitinger (27. Dezember 2005)

firstlord18 hat gesagt.:
			
		

> am wenigsten verstehe ich das in der Foreach-Schleife (lol, das ist ja der Hauptteil), naja was genau macht denn das:
> 
> 
> ```
> ...


Dadurch wird der Liste $nodeRefs ein neuer Eintrag hinzugefügt, der auf das soeben (eine Zeile vorher) erstellte Element verweist.


----------



## firstlord18 (27. Dezember 2005)

hm, stimmt eigentlich 
Und der erste Schritt in der foreach Schleife ist doch, dass ein dann entweder ein neuer Key im Output Array angelegt wird, oder (falls der Key schon existiert), eine Ebene tiefer gegangen wird !?


----------



## Matthias Reitinger (27. Dezember 2005)

Na ja, also eigentlich wird nur dafür gesorgt, dass die Variable $parent auf das Elternelement des neu anzulegenden Elements verweist.


----------



## firstlord18 (27. Dezember 2005)

ich werds irgendwann noch komplett verstehen, sodass ich das eventuell auch selbst coden kann  Geb mir noch n Jahr


----------



## Prophet05 (28. Dezember 2005)

Desto länger ich es mir anschaue desto mehr sinn ergibt es also desto transparenter wird es aber verstehen nein...
ich habe das gefühl das nodeRefs und outputArray ein und dasselbe sind...


----------



## ballistic (25. Juni 2006)

Hi,

ich habe ewig nach einer solch genialen Funktion gesucht, da ich genau das Problem habe, aus der beschriebenen Struktur dynamisch ein Menü zu erstellen.

Jetzt habe ich nur noch ein Problem, und zwar möchte ich das ganze in einem Listenfeld ausgeben. Und dazu reichen meine Array-Kenntnisse leider nicht aus  

Wäre super dankbar für einen Tipp, wie ich das anstelle.

Das Resultat sollte z.B. in etwa so aussehen:

Europa
- Deutschland
-- Bayern
--- München
--- Nürnberg
-- Hessen
- Österreich
-- Voralberg
...
Amerika
- USA
-- Florida
-- Kalifornien
...

Viele Grüße,
Martin


----------



## Sven Mintel (25. Juni 2006)

Schau mal in dies Tutorial: http://www.tutorials.de/forum/php-tutorials/235467-kategorienuebersicht-wie-hier-im-board.html

Dort wird eine HTML-Liste aus solch einem Array verwendet.


----------



## ballistic (25. Juni 2006)

Hi,

vielen Dank für die schnelle Antwort! 

Ich sehe schon, das ist auch wieder garnicht so einfach. V.a. weil der Aufbau des Arrays in deinem Link um das Child-Kennzeichen von Mathias Reitingers Beispiel, das ich eingesetzt hab, abweicht. 

Wenn du mir einen Tipp geben könntest, wie ich es in o.g. Beispiel mit einbaue, müsste ich mit der Fuktion print_asList() eigentlich zurecht kommen.

Viele Grüße,
Martin


----------



## Sven Mintel (25. Juni 2006)

Mmmh...das verstehe ich jetzt nicht, was du meinst.

Ich sehe bei Mathias' Array:

```
$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' ),
);
```
...und bei meinem Array:

```
$items = array(
    array( 'ID' => 1,   'pID' => 0, 'title' => 'Drinks' ),
    array( 'ID' => 2,   'pID' => 1, 'title' => 'Bier' ),
    array( 'ID' => 3,   'pID' => 1, 'title' => 'Wein' ),
    array( 'ID' => 4,   'pID' => 1, 'title' => 'Schnaps' ),
    array( 'ID' => 6,   'pID' => 2, 'title' => 'Radeberger' ,'href'=>'http://www.radeberger.de'),
    array( 'ID' => 7,   'pID' => 2, 'title' => 'Edelstoff' ),
    array( 'ID' => 8,   'pID' => 3, 'title' => 'Rotwein' ),
    array( 'ID' => 9,   'pID' => 3, 'title' => 'Weisswein' ),
    array( 'ID' => 10,  'pID' => 4, 'title' => 'Wodka' ),
    array( 'ID' => 11,  'pID' => 4, 'title' => 'Whisky' ),
    array( 'ID' => 14,  'pID' => 8, 'title' => 'Bordeaux' ),
    array( 'ID' => 16,  'pID' => 9, 'title' => 'Riessling' )
);
```
...keine entscheidenden Unterschiede. Falls du die Namen der ArraySchlüssel meinst...benenne sie einfach um.


----------



## ballistic (25. Juni 2006)

das stimmt, das input Array ist identisch aufgebaut. Aber das output Array, dass dann als Liste ausgegeben werden soll, hat bei dir doch ein Kennzeichen, falls eine Unterkategorie existiert. (array['child']).
Die fehlt mir. 

Ich hätte das ganze gern halbwegs einfach (= dass ich es noch halbwegs kapiere ) gehalten, also ohne Klassen gearbeitet.

Kurzum: Ich würde sehr gerne aus diesem Array (nach Matthias' Funktion ermittelt): 
	
	
	



```
Array
(
    [1] => Array
        (
            [bezeichnung] => FH Weihenstephan
            [3] => Array
                (
                    [bezeichnung] => Fachbereich LE
                    [5] => Array
                        (
                            [bezeichnung] => Landwirtschaft
                        )

                    [6] => Array
                        (
                            [bezeichnung] => Agrarmarketing und -management
                            [7] => Array
                                (
                                    [bezeichnung] => Skripte und Ähnliches
                                )

                            [8] => Array
                                (
                                    [bezeichnung] => Prüfungen
                                )

                        )

                )

            [4] => Array
                (
                    [bezeichnung] => Fachbereich LA
                )

        )

    [2] => Array
        (
            [bezeichnung] => TU München
            [9] => Array
                (
                    [bezeichnung] => Ernährungswissenschaften
                )

            [10] => Array
                (
                    [bezeichnung] => Agrarwissenschaften
                    [11] => Array
                        (
                            [bezeichnung] => Prüfungen
                        )

                    [12] => Array
                        (
                            [bezeichnung] => Skripte u.ä.
                        )

                )

        )

)
```
 ein Listenmenü erstellen. 

Wenn ich hier im Forum und auch bei Google die Suchergebnisse zu diesem Thema sehe, glaube (und hoffe ) ich, dass ich nicht der einzige bin, der zu doof ist, das zu verstehen und sich über eine möglichst einfache Lösung freuen würde


----------



## forsterm (25. Juni 2006)

Hallo,
so

```
<?php
    function generateList($array, &$output=''){
        $output .= '<ul>';
        foreach ($array as $arr){
            if (is_array($arr)){
                generateList($arr, $output);
            } else {
                $output .= '<li>'.$arr.'</li>';
            }
        }
        $output .= '</ul>';
        return str_replace('</ul><ul>', '', substr($output, 4, -5));
        // Die folgende Zeile generiert eine ul-List, die für dieses Tutorial (http://www.tutorials.de/forum/javascript-tutorials/164340-javascript-treemenu.html) verwendet werden könnte
        #return str_replace('</ul></ul>', '</ul></li></ul>', str_replace('</ul><li>', '</ul></li><li>', str_replace('</li><ul><li>', '<ul><li>', str_replace('</ul><ul>', '', substr($output, 4, -5)))));
    }

    $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' ),
        array( 'ID' => 7, 'parentID' => 0, 'title' => 'Element7' ),
        array( 'ID' => 8, 'parentID' => 7, 'title' => 'Element8' ),
        array( 'ID' => 9, 'parentID' => 7, 'title' => 'Element9' ),
        array( 'ID' => 10, 'parentID' => 0, 'title' => 'Element10' ),
        array( 'ID' => 11, 'parentID' => 0, 'title' => 'Element11' ),
    );
    
    $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']];
    }
    
    echo generateList($outputArray);
?>
```
 //Edit: Hab die Funktion jetzt (02.08.2006) ein wenig geändert, sodass sie meiner Meinung nach besser ist, da auf [phpf]global[/phpf] verzichtet werden kann.
sollte es funktionieren.

mfg
forsterm


----------



## ballistic (25. Juni 2006)

super, 1000 Dank!

Die Ausgabe is ja recht einfach, wenn man weiß, wie sie geht 

Ich hoffe, dass ich es jetzt endlich hin bekomme, aber das ganze noch in eine select-Box mit ID als Wert zu packen, sollte zu schaffen sein. 

Probiere an dem Menü schon ein "paar" Tage rum...

Deshalb nochmal vielen Dank für Eure super Hilfe!


----------



## ballistic (1. Juli 2006)

Hier noch als Ergänzung das ganze wie oben nur als SELECT Feld ausgegeben und das Array über ein SQL-Query erzeugt:


```
<?php

/** DB auslesen und inputArray erzeugen **/

$connect = mysql_connect('localhost', 'usr', 'pwd');
mysql_select_db('db1');

$j=0;
$rescat1 = mysql_query("SELECT ID, parentID, title FROM categories ORDER BY parent");
while ($row = mysql_fetch_assoc($rescat1)) {
  foreach($row as $key => $value) {
    $inputArray[$j] [$key] = $value;
  }
  $j++;
}

/*
// oder zum Testen ohne DB
    $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' ),
        array( 'ID' => 7, 'parentID' => 0, 'title' => 'Element7' ),
        array( 'ID' => 8, 'parentID' => 1, 'title' => 'Element8' ),
        array( 'ID' => 9, 'parentID' => 1, 'title' => 'Element9' ),
    );
*/


    echo "Array:<pre>";
    print_r($inputArray);
    echo "</pre>";


/** Hierarchie ermitteln **/

    $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']];
    }

    echo "Array:<pre>";
    print_r($outputArray);
    echo "</pre>";

/** outputArray als SELECT-Feld ausgeben **/

    $output = '';
    $i='';
    $id = 0;
    function generateList($array, $i, $id){
        global $output;
        foreach ($array as $key => $value){
            if (is_array($value)){
              $id = $key;
              generateList($value, $i, $id);
            } else {
                $output .= "<option value='".$id."'>".$i.$value."</option>\n";
                $i .='&nbsp; &nbsp; ';
            }
        }

        $i = '';
        return $output;
    }

    echo "<select name='cat_id' size='1'>\n";
    echo generateList($outputArray, $i, $id);
    echo "</select>\n";

?>
```


----------



## Matthias Reitinger (26. Juli 2006)

Hallo,

das hier:


			
				ballistic hat gesagt.:
			
		

> ```
> $j=0;
> $rescat1 = mysql_query("SELECT ID, parentID, title FROM categories ORDER BY parent");
> while ($row = mysql_fetch_assoc($rescat1)) {
> ...


kann allerdings auch verkürzen werden zu:

```
$rescat1 = mysql_query("SELECT ID, parentID, title FROM categories ORDER BY parent");
$inputArray = array();
while ($row = mysql_fetch_assoc($rescat1)) {
	$inputArray[] = $row;
}
```

Grüße,
 Matthias


----------



## Flixxtoras (14. September 2006)

Hallo habe noch ein kleines Problem sonst funktioniert es super ;-)

Ich möchte gern für jeden Eintrag noch eine ID mit ausgeben habe aber keine Ahnung wie ich das mit dem Arrays machen soll. D.h ich möcht efür jeden Punkt noch eine ID (für einen Link) ausgeben. Gibt es da eine Möglichkeit?

```
$inputArray = array(
        array( 'ID' => 1, 'parentID' => 0, 'title' => 'Element1', 'kID' => '4711' ),
    );
    
    $outputArray = array();
    $nodeRefs = array(0 => &$outputArray);
    
    foreach ($inputArray as $element) {
        $parent = &$nodeRefs[$element['parentID']];
        $parent[$element['ID']] = array('title' => $element['title'], 'kID' => $element['kID']);
        $nodeRefs[$element['ID']] = &$parent[$element['ID']];
    }
```


----------



## ballistic (14. September 2006)

*Id*

Hi,
schau dir doch mal meinen vorigen Post an, die Ausgabe als select-Feld. Dort geb ich den Array-Schlüssel, der ja der ID entspricht, mit aus. Hatte nämlich genau das gleiche Problem wie du.


----------



## Flixxtoras (14. September 2006)

So habe es mir noch mal durch den Kopf gehen lassen. Genau das war es was ich gesucht habe vielen Dank!!



			
				ballistic hat gesagt.:
			
		

> Hi,
> schau dir doch mal meinen vorigen Post an, die Ausgabe als select-Feld. Dort geb ich den Array-Schlüssel, der ja der ID entspricht, mit aus. Hatte nämlich genau das gleiche Problem wie du.


----------



## megapreisbrecher (3. Oktober 2006)

Matthias Reitinger hat gesagt.:


> Dieses Problem ließe sich sehr schön mittels Referenzen lösen:
> 
> ```
> <?php
> ...



Das ganze funktioniert nur, wenn der erste Eintrag auch die niedrigste ID hat. Setzt man die ID des ersten Eintrags auf z.B. 999 liefert es nur noch diesen Eintrag.


----------



## Matthias Reitinger (3. Oktober 2006)

Hallo,



megapreisbrecher hat gesagt.:


> Das ganze funktioniert nur, wenn der erste Eintrag auch die niedrigste ID hat. Setzt man die ID des ersten Eintrags auf z.B. 999 liefert es nur noch diesen Eintrag.


Das ist korrekt. Gegebenenfalls müsste man vorher also noch eine Sortierung vornehmen.

Grüße,
 Matthias


----------



## Flex (3. Oktober 2006)

Dann sortier das Array vor der entsprechenden Weiterverarbeitung...

/Edit:
Und wieder zu lange gewartet mit dem Antworten...


----------



## megapreisbrecher (3. Oktober 2006)

Das dürfte nicht immer möglich sein, wenn man das ganze als Ordner betrachtet.

Hätte das ganze Anfangs diese Struktur

```
1 => Root 1
  2 => Sub A
  3 => Sub B
  4 => Sub C

5 => Root 2
```

und würde man dann die Ordner verschieben

```
1 => Root 1

5 => Root 2
  2 => Sub A
  3 => Sub B
  4 => Sub C
```

und der ersten Root-Ordner löschen, wäre die ID des ersten Eintrags zu hoch.

Nach was also sortiern?


----------



## Matthias Reitinger (3. Oktober 2006)

Hallo,



megapreisbrecher hat gesagt.:


> Das dürfte nicht immer möglich sein, wenn man das ganze als Ordner betrachtet.
> 
> […]
> 
> Nach was also sortiern?


Die Sortierung muss derart erfolgen, dass der Eintrag mit der ID _x_ vor allen Knoten mit einer parentID _x_ steht.

Grüße,
 Matthias


----------



## megapreisbrecher (3. Oktober 2006)

Wie kann man mit dem Array denn so einen Baum darstellen?


```
+-Root
|-Eintrag 1
+-Eintrag 2
| |-Eintrag 2.1
| +-Eintrag 2.2
| | |-Eintrag 2.2.1
| | |-Eintrag 2.2.2
| | `-Eintrag 2.2.3
| `-Eintrag 2.3
|-Eintrag 3
|-Eintrag 4
+-Eintrag 5
  |-Eintrag 5.1
  `-Eintrag 5.2
```

Er soll genau so ausgegeben werden (mit den Strichen).


----------

