# Baumstruktur durchgehen



## magic_halli (24. Aug 2006)

Hi,

gibt es irgendwo irgendwie ein einfaches Codebeispiel o.ä., wie man eine Baumstruktur mit unbekannter Tiefe durchgehen bzw. durchsuchen kann? Hier müsste ich sicher rekursiv rangehen?!
Es soll quasi vom Rootknoten, in die Tiefe, jeder auftretende Knoten gefunden werden, in diesen reingegangen werden, die Kinder ermittelt (mit jedem gefundenen Kind etwas tun) und wieder ne Ebene höher gesprungen und die Baumstruktur weiter durchsucht werden  ???:L  !
Klingt erstmal logisch für mich, nur hab ich sowas noch nie gemacht... will´s aber lernen!!!  :### 

Deshalb würde ich mir gern mal anhand eines Beispiels das ganze zu Gemüte führen um es besser zu verstehen.

Kann mir jemand helfen?

Vielen Dank.


----------



## AlArenal (24. Aug 2006)

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


----------



## Anmeldeboykottierer (24. Aug 2006)

Hi,
das durchwandern eines Baumes nennt man Traversieren, such einfach mal bei google oder im Wiki (oder hier) nach dem Begriff und du solltest schnell mehrere Möglichkeiten finden.
Zudem sind die Begriffe Tiefensuche und Breitensuche immer ganz hilfreich und als weitere Möglichkeit bietet A* eine (etwas komplexere) Kombination der letzten Beiden (mehr oder weniger).

Gruß Der Anmeldeboykottierer


----------



## magic_halli (24. Aug 2006)

So, ich hab jetzt tausende Artikel gewälzt :###  ...aber ein allgemeines Beispiel hab ich leider nicht gefunden. Ich bin eigentlich "nur" auf der Suche, nach einem allgemeinen Codebeispiel, welches Tiefensuche (PreOrder) mit Rekursion realisiert.

So ein Beispiel müsste ich sowieso auf meine Gegebenheiten anpassen... 
Meine Baumstruktur beschreibt den Aufbau von einer Baugruppe(BG) und deren Einzelteile(ET). Diese BG kann wiederum Baugruppen mit Einzelteilen enthalten usw. Die Tiefe ist mir vorher nicht bekannt.
Bsp.:

```
/*

                                         BG
                                      /         \
                                  BG           ET
                                 /     \
                              ET      BG
                                       /       \
                                   ET         ET
*/
```
Eine Verarbeitung erfolgt nur auf ET. Beim Auftauchen einer BG soll diese lediglich durchsucht werden, ob ET´s enthalten sind und diese werden dann wieder verarbeitet usw.
Wie schon gesagt, hab viel gelesen, aber nichts gefunden, wo ich mal drauf aufsetzen kann - zumal ich noch keinerlei Erfahrung mit Tiefensuche mit Rekursion gemacht habe.  ???:L


----------



## SamHotte (24. Aug 2006)

Komisch, in dem Link von AlArenal steht doch so'n Beispiel (unter "Algorithmus (formal)") ...


----------



## magic_halli (24. Aug 2006)

Ahh, mich hat das mit dem Stack in dem Beispiel Algorithmus(formal)  zu sehr verwirrt   

Aber jetzt... :idea: :idea: :idea:    Der Stack ist ja nichts weiter, als ein Array, in welches ich z.B. meine Baugruppen- und Einzelteilnamen reinspeichere. Dieses Array(bzw. Stack) gehe ich dann durch, bearbeite jedes einzelne Element darin und rufe direkt nach der jeweiligen Abarbeitung die Funktion wieder auf. (und natürlich muss ich das jeweilige Element im Array vor dem rekursiven Aufruf löschen) 

Liege ich da richtig?

Ach ja, wie ich das verstehe, wird in dem Beispiel etwas auf den Stack geschoben. Aber was wird von dort wieder entfernt - das erste oder das letzte Element???


----------



## CeadeS (11. Nov 2006)

Hallo, ich habe ein ähnliches Problem.
Ich möchte einen Binären Baum iterativ inOrder traversieren.
Halt sortiert ausgeben.
So komme ich zu meine Frage:
Ist das ohne Stack möglich und wenn ja wie?

Gruß 

Ceades


----------



## SnooP (11. Nov 2006)

Iterativ glaub ich nicht... - rekursiv ja... der Stack baut dir beim iterativen nur die Rekursion nach.


----------



## byte (11. Nov 2006)

Hier gibts Pseudo Code zum iterativen traversieren: http://en.wikipedia.org/wiki/Tree_traversal


----------



## Leroy42 (11. Nov 2006)

magic_halli hat gesagt.:
			
		

> Liege ich da richtig?



An sich schon aber in deinem Fall würde ich den direkten Weg der Rekursion nehmen


```
void traverse(Tree tree) {
  traverse(tree.left);
  myMethod(tree.node);
  traverse(tree.right);
}
```


----------

