Baumstruktur in c++
-
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
-
It0101 schrieb:
Ein Baum ist schnell programmiert.
Naja, schnell im Vergleich zu einem Webserver. Langsam im Vergleich zu einem Array.
Du brauchst eine Klasse die ein Array/vector/Liste/whatever von pointern auf Subknoten/Kindknoten enthält.
Braucht man nicht. Ist aber erstmal der einfachste Anfang.
Und alles was du tust ist rekursiv zu erledigen.
Nee. Alles geht auch iterativ. Manche Sachen im Baum fühlen sich rekursiv aber ganz nett an.
-
Das Problem ist ich habe das noch nie gemacht, zumindest auch nichts ähnliches.
Ich weiß immoment irgendwie gar nicht wie ich anfangen soll.
Ich weiß ungefähr wie ein Binär Baum programmiert wird, dort werden für die beiden Subknoten jeweils ein Zeiger definiert. Bei mehreren Subknoten, weiß ich ja vorher net wie viele dieser Zeiger ich definieren muss.
Kennt ihr vielleicht irgendein tutorial, wo zumindest ein kleiner Beispielcode enthalten ist.
-
Lies dir mal die geposteten Links zur STL durch. In den Artikeln dieses Forums gibt es auch eine deutsche Einführung. Wenn du die STL-Container verstanden hast (sei nicht zu voreilig, das bringt dir nichts), kannst du sie einsetzen, um Kindknoten zu speichern.
-
struct_master schrieb:
Ich weiß immoment irgendwie gar nicht wie ich anfangen soll.
Ich kann Dir keine Tipps geben, weil ich keinen Schimmer habe, welche Eigenschaften der Baum haben soll und wozu er da ist.
Soll es ein Suchbaum (Geschwister sortiert im vector, Kinder kleiner als Papa aber größer als dessen älterer Bruder)
sein oder ein Stammbaum (Reihenfolge der Geschwister liegt fest)
oder ein Verzeichnisbaum (Reihenfolge der Geschwister ist egal)?
-
Es soll ein Baum werden, der ähnlich wie der Windows Explorer ist, ich brauche nichts grafisches, aber die Struktur ist die Selbst.
Es gibt sozusagen strings, die unter sich Kinder strings haben, die dann auch noch Kinder strings haben.
Also der Wurzelknoten soll nur ein string besitzen, die Kinder können mehrerer besitzen, wie halt im Explorer der Ordner Programme angeklickt, kommen mehrere Kinder ordner usw.
