# Verschachteltes Array aus Nested Sets



## tequito (27. April 2008)

Hallo,

ich komme einfachnicht weiter. Ziel ist ein verschachteltes Array, das aus einer Nested Sets Anordnung gebildet wird.

So sähe der Baum optisch aus:

```
Lebewesen
|
`-- Säugetiere
|   |
|   `-- Primaten
|   |   |
|   |   `-- Halbaffen
|   |   |
|   |   `-- Affen
|   |
|   `-- Nagetiere
|
`-- Menschen
    |
    `-- Asiaten
    |
    `-- Afrikaner
```

Die Abfrage liefert, wie nachfolgend sortiert, diese Werte:

```
id  name        level  kinder  davor  danach
============================================
 7  Lebewesen    0     8       0      0
10  Säugetiere   1     4       1      0
 2  Primaten     2     2       1      0
 8  Halbaffen    3     0       1      0
 4  Affen        3     0       0      1
33  Nagetiere    2     0       0      1
52  Menschen     1     2       0      1
22  Asiaten      2     0       1      0
26  Afrikaner    2     0       0      1
```
"davor sagt, ob der Eintrag ein Elternelement hat, "danach" sagt ob der Eintrag Kinder hat.

Wie kann man nun anhand dieser Werte ein verschachteltes Array bauen mit der ID als Key?

```
Array
(
  [7] => Array
    (
      [id] => 7
      [name] => Lebewesen
      [child] => Array
        (
          [10] => Array
            (
              [id] => 10
              [name] => Säugetiere
              [child] => Array
                (
                  ...
                )
            )
          [52] => Array
            (
              [id] => 52
              [name] => Menschen
              [child] => Array
                (
                  [22] => Array
                    (
                      [id] => 22
                      [name] => Asiaten
                    )
                  [26] => Array
                    (
                      [id] => 26
                      [name] => Afrikaner
                    )
                )
            )
        )
    )
)
```


----------



## metalalisa (27. April 2008)

von Anfang, sollst du SQL-Abfrage bilden mit 
ORDER BY level ASC, davon ASC, danach DESC 
wenn ich deine Frage richtig versteht habe...


----------



## tequito (27. April 2008)

Mein Problem ist, dass ich keinen verschachtelten Array hinbekomme.


----------



## metalalisa (27. April 2008)

du braucht die Rekursion....


----------



## tequito (27. April 2008)

Und wie mache ich das? Habe gar keinen Code-Ansatz. 

Im Internet habe ich jetzt 4 Stunden gesucht und alles was ich gefunden habe waren die selbe Frage, aber nie Antworten.

Nirgends konnte ich finden wie ich mit Nested Sets eine <UL>-<LI>-HTML-Ausgabe hinbekomme.


----------



## Sven Mintel (27. April 2008)

Hast du dir schonmal nested sets genauer angeschaut...wie die aufgebaut sind?

Um deine Struktur als nested set abzuspeichern, müsstest du folgende Daten hinterlegen:

```
|lft|rgt
----------+---+---
Lebewesen | 1 | 18
Säugetiere| 2 | 11
Primaten  | 3 |  8
Halbaffen | 4 |  5
Affen     | 6 |  7
Nagetiere | 9 | 10
Menschen  |12 | 17
Asiaten   |13 | 14
Afrikaner |15 | 16
```


Sowas wie Eltern, Kinder etc. benötigst du da nicht 

http://de.wikipedia.org/wiki/Nested_Sets


----------



## Gumbo (28. April 2008)

```
$struct = array();
$level = 0;
$helper =& $struct;
foreach($data as $item) {
	if($level < $item['level']) {
		$keys = array_keys($helper);
		$helper =& $helper[$keys[count($keys)-1]]['children'];
	} else if($level > $item['level']) {
		$helper =& $struct;
		for($i=0; $i<$level-1; $i++) {
			$keys = array_keys($helper);
			$helper =& $helper[$keys[count($keys)-1]]['children'];
		}
	}
	$helper[$item['id']] = array(
		'id'       => $item['id'],
		'name'     => $item['name'],
		'children' => array(),
	);
	$level = $item['level'];
}
```


----------



## tequito (28. April 2008)

Sven Mintel hat gesagt.:


> Hast du dir schonmal nested sets genauer angeschaut...wie die aufgebaut sind?
> 
> Sowas wie Eltern, Kinder etc. benötigst du da nicht


Ich möchte mir die Ausgabe als <ul><li> im HTML generieren und weiß leider überhaupt nicht wie ich die Verschachtelung hinbekomme.

@Gumbo:
Was genau soll der Code machen? Bei mir gibt das nur die einzelnen Datensätze als Array untereinander aus.


----------



## xErY (28. April 2008)

Hallo,

Gumbo erstellt dort aus deinem Set einen Mehrstufigen Array den du dann wiederum durchlaufen könntest um eine Liste wie du sie haben möchtest, anzulegen.
Mfg xErY


----------



## Gumbo (28. April 2008)

Der Algorithmus erzeugt die genannte Datenstruktur auf der Basis der Datensätze in der Form:
	
	
	



```
$data = array(
	array(
		'id'    => 7,
		'name'  => 'Lebewesen',
		'level' => 0,
	),
	array(
		'id'    => 10,
		'name'  => 'Säugetiere',
		'level' => 1,
	),
	// […]
);
```


----------



## tequito (28. April 2008)

Unfassbar! 

Wie lange muss man PHP lernen um sowas hinzukriegen?

Kann mir jemand sagen was das bedeutet?

```
$helper =& $struct;
```

Wenn ich nach =& bei Google suche kommt kein Treffer.


----------



## Gumbo (28. April 2008)

Das ist eine Referenzzuweisung. Die ist notwendig um die neuen Elemente an der richtigen Stelle einzufügen.


----------



## tequito (14. Mai 2008)

Nachdem ich dachte, das tolle Script von Gumbo bildet einen korrekten Baum ab, bin ich mittlerweile auf Probleme gestoßen deren Ursache ich einfach nicht sehe.

```
$struct = array();
$level = 0;
$helper =& $struct;
foreach($data as $item) {
    if($level < $item['level']) {
        $keys = array_keys($helper);
        $helper =& $helper[$keys[count($keys)-1]]['children'];
    } else if($level > $item['level']) {
        $helper =& $struct;
        for($i=0; $i<$level-1; $i++) {
            $keys = array_keys($helper);
            $helper =& $helper[$keys[count($keys)-1]]['children'];
        }
    }
    $helper[$item['id']] = array(
        'id'       => $item['id'],
        'name'     => $item['name'],
        'children' => array(),
    );
    $level = $item['level'];
}
```

Diese Daten liefern die Abfrage korrekt zurück:

```
Array
(
  [0] => Array
    (
      [id] => 1
      [name] => Root
      [level] => 0
      [children] => 7
    )

  [1] => Array
    (
      [id] => 3
      [name] => Menschen
      [level] => 1
      [children] => 2
    )

  [2] => Array
    (
      [id] => 6
      [name] => Afrikaner
      [level] => 2
      [children] => 1
    )

  [3] => Array
    (
      [id] => 14
      [name] => Ureinwohner
      [level] => 3
      [children] => 0
    )

  [4] => Array
    (
      [id] => 9
      [name] => Pflanzen
      [level] => 1
      [children] => 0
    )

  [5] => Array
    (
      [id] => 10
      [name] => Steine
      [level] => 1
      [children] => 0
    )

)
```

Der Baum sieht allerdings komischerweise Weise so aus:

```
Array
(
  [1] => Array
    (
      [id] => 1
      [name] => Root
      [type] => root
      [level] => 0
      [children] => Array
        (
          [3] => Array
            (
              [id] => 3
              [name] => Menschen
              [type] => content
              [level] => 1
              [children] => Array
                (
                  [6] => Array
                    (
                      [id] => 6
                      [name] => Afrikaner
                      [type] => content
                      [level] => 2
                      [children] => Array
                        (
                          [14] => Array
                            (
                              [id] => 14
                              [name] => Ureinwohner
                              [type] => user
                              [level] => 3
                              [children] => Array
                                (
                                )
                            )
                        )
                    )

                  [9] => Array
                    (
                      [id] => 9
                      [name] => Pflanzen
                      [type] => content
                      [level] => 1
                      [children] => Array
                        (
                        )
                    )

                  [10] => Array
                    (
                      [id] => 10
                      [name] => Steine
                      [type] => content
                      [level] => 1
                      [children] => Array
                        (
                        )
                    )
                )
            )
        )
    )
)
```

Die letzten beiden Punkte müssten eigentlich unterhalb von Root hängen:

```
Root
|
`-- Menschen
|   |
|   `-- Afrikaner
|       |
|       `-- Ureinwohner
|
`-- Pflanzen
|
`-- Steine
```

Kommt das Script mit dem Sprung von einem Level 3 (Ureinwohner) auf Level 1 (Pflanzen) nicht zurecht,also wenn zwei nachfolgende Knoten mehr als 1 LEvel auseinander sind?

Wo steckt der Fehler in Gumbos Script?


----------



## 4654515454 (10. Mai 2010)

Sorry fürs Leichengraben,

Bin gerade über Google auf dieses Thema gestoßen und musste folgende abwandlung durchführen damit es ordentlich funktioniert.

Das:

```
for($i=0; $i<$level-1; $i++) {
            $keys = array_keys($helper);
            $helper =& $helper[$keys[count($keys)-1]]['children'];
        }
```

Zu:

```
$i=0;
        while($i<$item['level']) {
            $keys = array_keys($helper);
            $helper =& $helper[$keys[count($keys)-1]]['children'];
            $i++
        }
```

dann geht es.


----------

