Baumstruktur durchgehen

Status
Nicht offen für weitere Antworten.

magic_halli

Bekanntes Mitglied
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.
 
A

Anmeldeboykottierer

Gast
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

Bekanntes Mitglied
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.:
Code:
/*

                                         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
 

magic_halli

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

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

Mitglied
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

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

Leroy42

Top Contributor
magic_halli hat gesagt.:
Liege ich da richtig?

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

Code:
void traverse(Tree tree) {
  traverse(tree.left);
  myMethod(tree.node);
  traverse(tree.right);
}
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
J ternäre(3) Baumstruktur Java Basics - Anfänger-Themen 2
W Baumstruktur Java Basics - Anfänger-Themen 8
S Baumstruktur: tiefsten Knoten finden Java Basics - Anfänger-Themen 3
Helgon Baumstruktur tiefe N erzeugen Java Basics - Anfänger-Themen 3
C ausgabe Baumstruktur java.io.File Java Basics - Anfänger-Themen 2
GetStringFrmObj Klassen Baumstruktur aus XMls erstellen, aber wie? Java Basics - Anfänger-Themen 15
S Baumstruktur zusätzlich ebenenweise repräsentieren Java Basics - Anfänger-Themen 9
S RBTree - baumstruktur darstellen Java Basics - Anfänger-Themen 7
A Baumstruktur Java Basics - Anfänger-Themen 6
D Baumstruktur erzeugen Java Basics - Anfänger-Themen 18
R Baumstruktur Java Basics - Anfänger-Themen 4
G Baumstruktur rekursiv durchlaufen Java Basics - Anfänger-Themen 2
G Einfügen von Elementen in Baumstruktur Java Basics - Anfänger-Themen 3
K Java Ausgabe als Baumstruktur Java Basics - Anfänger-Themen 8
G Baumstruktur Java Basics - Anfänger-Themen 3
F Baumstruktur aus 2 DB-Tabellen Java Basics - Anfänger-Themen 6
M 2d ArrayList durchgehen Java Basics - Anfänger-Themen 2
B Verkettete Liste durchgehen und einzelne Elemente in neue Liste tun Java Basics - Anfänger-Themen 9
B Liste mit foreach-Schleife durchgehen Java Basics - Anfänger-Themen 4
S Suchmaske alle Möglichkeiten effinzent durchgehen Java Basics - Anfänger-Themen 4
G Alle Ordner durchgehen Java Basics - Anfänger-Themen 6
H BITTE SCHNELLE HILFE - VERZEICHNISSE DURCHGEHEN Java Basics - Anfänger-Themen 2
M ArrayList rückwärts durchgehen? Java Basics - Anfänger-Themen 9
G TreeMap vom 1. bis letzte eintrag durchgehen Java Basics - Anfänger-Themen 17
B ArrayList durchgehen Java Basics - Anfänger-Themen 4
Q Tabindex durchgehen Java Basics - Anfänger-Themen 5
J Verz rekursiv durchgehen Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben