Baumstruktur in c++
-
Hi.
ich möchte eine Baumstruktur in C++ schreiben. Ein Knoten kann dabei theoretisch zieeemlich viele Nachfolgeknoten haben,also kein Binarbaum der ja nur 2 Knoten haben kann, typischerweise werden es wohl ca. 30 sein.Wie macht man sowas am Besten?
Ein Link zu einem Tutorial wo eine Baumstruktur mit beliebig vielen Nachfolgern implementiert ist, wär auch cool!
Bedanke mich schon mal im voraus!
-
Ein Baum ist schnell programmiert. Du brauchst eine Klasse die ein Array/vector/Liste/whatever von pointern auf Subknoten/Kindknoten enthält.
Und alles was du tust ist rekursiv zu erledigen. d.h. man sollte schon Rekursion verstanden haben
-
Danke für die schnelle Antwort!
Ich weiß aber nicht wie man Rekursiv programmiert, habt ihr da vielleicht irgendwelche tuts, die ihr empfehelen könntet?
-
Es bringt jedenfalls nix, wenn du Bäume bauen willst, also musst du dich zuerst mit Rekursion beschäftigen:
Hier z.B. ist leicht verständlicher Code
http://tutorial.schornboeck.net/rekursion.htm
den du einfach mal ausführen solltest und dir die Ausgaben anschauen solltest.
Einleitend kannst du durchaus auch mal den Wikipedia-Artikel lesen:
-
oder mit Iteration!
wegen Stack-Overflow bei zu tiefer Rekursion
-
Den baum will ich mal sehen, der rekursiv einen Stakcoverflow bringt und pro Knoten etwa 30 Kinder hat
Wenn man einen Stackoverflow bei rekursiv hat, macht man meistens irgendwas falsch... oder die Datensturktur ist wirklich paar millionen einträge tief
-
@Maxi
Wenn der Baum sonst keine Strukturbedingung enthält ist das schnell passiert. Ein entarteter Suchbaum z.B. kann den Stack recht schnell füllen.
-
der OP schrieb, typischerweise hat ein Knoten 30 Kinder. Einen solchen Baum, der dann einen Stacküberlauf provoziert, kann man wohl kaum speichern...
-
Warum?
-
Maxi schrieb:
der OP schrieb, typischerweise hat ein Knoten 30 Kinder.
Also wie ein Suchbaum im Schachspiel.
Maxi schrieb:
Einen solchen Baum, der dann einen Stacküberlauf provoziert, kann man wohl kaum speichern...
Naja, mal ohne 3-Zug-Regel und 50-Zug-Regel. Wenn das Spiel für beide Seiten zwangsläufig geworden ist und der eine Dauerschach geben muß, um nicht zu verlieren, haben wir ab da nur noch Knoten mit einem Kind (obwohl weiterhin eine Schchstellung typischerweise 30 Kinder hat).
-
Hi.
Und zwar sind im Baum eigentlcih nicht 30 Subknoten statisch vorgesehn, sondern kann bis zu haben. Also am besten irgendwie dynamisch zu erzeugen, wäre gut.
Denn am Ende will ich einen Baum der z.b 30 Subknoten hat, von denen die Subkonoten 10 weitere Subknoten haben, und diese Subknoten 20 weitere und so weiter, geht das dann auch rekursiv oder kommt es zu einem Stackoverflow.
-
Also sowas wie eine Art windows explorer nur jetzt keine Grafische anzeige, sondern es sollen darin Datengespeichert werden, in diesem Baum
-
zu implementieren wäre es iA so:
struct Node { Container<Node*> children; // hier die Daten im aktuellen Knoten }
-
was ist den ein container, sowas wie ein STL vektor oder wie ist das mit dem container gemeint?
-
struct_master schrieb:
was ist den ein container, sowas wie ein STL vektor oder wie ist das mit dem container gemeint?
http://www.cplusplus.com/reference/stl/
such dir einen aus
-
-
leider verstehe ich gerade den nutzen einer solchen baumstrukur nicht.
Könnte vielleicht wer einen kleinen verständlichen code reinschreiben wo solch eine baumstruktur mit rekurxiver anwendung benutzt wird?
Wäre klasse...
Gruß
-
Dann mache dich per SuMa mal etwas darüber schlau. Es hat was mit dem sog. "effektiven Laufzeitverhalten" zu tun.
Bei Bäumen ist es je nach Art verschiedenartig logarithmisch, z.B. O(log n).
-
Ich habe mich mal im Internet umgeguckt und bin auf Tree Library Container(TLC) gestoßen, ist von einem Mitchel Haas geschrieben worden.
Es steht zwar viel da, aber es gibt kein tutorial, kennt sich jemand von euch damit aus.
Ist ein Container ähnlich der STL's nur für eine Baumstruktur, klingt alle svielversprechend nur komm damit irgendwie nicht klar.
-
Versuch doch einfach, dir selber einen zu programmieren. Dabei lernst du mehr. es dauert vielleicht ein wenig länger, aber dafür weißt du was du tust und kannst selbst am Code Veränderungen vornehmen.
Edit: ich arbeite auch gerade selbst an einer Baumstruktur und verändere fast täglich aus Performancegründen irgendwas. Und jeden Tag wird es ein bisschen besser
