Baumstruktur in c++

zwutz

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

pumuckl

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ß

Ad aCTa

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.

It0101

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

volkard

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.

Nexus

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.

volkard

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.

It0101

volkard schrieb:

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.

Ja ich hatte mir auch schon Gedanken gemacht, wie ich die Rekursion loswerden könnte:

Ich könnte die Klasse abschaffen, daraus ein struct ( POD ) bauen und mir nur die Offsets merken, wo meine Kindknoten liegen. Bzw falls nötig auch das (negative) Offset zum jeweiligen Elternknoten.
Die Version ist zwar nich gerade angenehm zu programmieren, aber dürfte einiges an Overhead einsparen.

Zum Glück ist bei mir ein Rekursionsdurchlauf des Baumes nicht so oft notwendig. Daher spar ich mir das vorerst

Ad aCTa

Du solltest erst mal wissen, was du für einen Baum willst. Da er nicht binär ist, fliegen "Binärer Baum", "AVL-Baum" und somit auch "Red-Black-Tree" raus. Du willst also eine Art B-Baum. Wo genau hast du Schwierigkeiten?

http://de.wikipedia.org/wiki/B-Baum#Operationen hat eine allgemeine Erklärung, unten sind Hilfe-Links.

Ich habe mir mal das durchgelesen, klingt nach dem was ich suche. Ich habe noch nach einem Tutorial oder einem guten Beispiel wie dass in C++ programmiert wird gesucht, habe aber nichts gefunden. Könnt ihr mir da weiter helfen.

Hi! bin neu hier. Meine Frage ist ähnlich der gestellten, ich will gerne mehrwertige Bäume programmieren, also Bäume mit mehr als nur 2 Knoten, nur habe ich bis jetzt die Erfahrung mit Binär Bäumen. Finde im Internet auch nur Binär Bäume und es heißt immer mehrwertige und Binär Bäume sind gleichwertig. Muss ich dann für jeden Knoten auch mehrere Zeiger anlegen, denn so geht das doch mit den Binär Baumen.
Danke!

unskilled

newbie1243 schrieb:

Hi! bin neu hier. Meine Frage ist ähnlich der gestellten, ich will gerne mehrwertige Bäume programmieren, also Bäume mit mehr als nur 2 Knoten, nur habe ich bis jetzt die Erfahrung mit Binär Bäumen. Finde im Internet auch nur Binär Bäume und es heißt immer mehrwertige und Binär Bäume sind gleichwertig. Muss ich dann für jeden Knoten auch mehrere Zeiger anlegen, denn so geht das doch mit den Binär Baumen.
Danke!

such mal nach B-Baum - b steht dort _nicht_ für binär sondern für beyer oder so^^
jopp - wenn du mehrere kindknoten brauchst musst du auch auf mehrere knoten verweisen können und dazu brauchst du auch mehrere zeiger ;o)
wenn ich deine frage(n) nich richtig verstanden habe, dann versuch mal noch mal konkreter zu fragen...

bb

Hi Leute !
Danke nochmal für eure Hilfe, habe es jetzt mit std::map gelöst.
Damit kann man zumindest in einer art Baumstruktur mit mehreren Kindern speichern wenn als Datentyp ein Container benutzt wird.

unskilled

struct_master schrieb:

Hi Leute !
Danke nochmal für eure Hilfe, habe es jetzt mit std::map gelöst.
Damit kann man zumindest in einer art Baumstruktur mit mehreren Kindern speichern wenn als Datentyp ein Container benutzt wird.

ne - du kannst nur mehrere werte(blätter / externe knoten) dazu speichern - nicht aber mehrere (innere) knoten...
vll sagst du uns einfach mal, wofür du diese struktur brauchst und wir sagen dir dann, was du besser nimmst^^

bb

ich muss eigentlich nur Parameter speichern können, die haben aber immer über Parameter wie zb. Parameter1->Name: test, Datentyp: ascii , Wert: ok
Im Prinzip müsste ich ein Stufe höher noch die Jeweilige Nummer Speichern, dies habe ich aber gelöst in dem ich eine Struct genommen habe wo zu einer Nummer immer diese unterparameter gehören. Klappt soweit gut, es sei denn ihr habt noch was besseres

unskilled

ich muss eigentlich nur Parameter speichern können, die haben aber immer über Parameter wie zb. Parameter1->Name: test, Datentyp: ascii , Wert: ok

struct parameter
{
  string name;
  string typ;
  string wert;
};

std::map<parameter> my_map;

oder wie meinst du das?
werd mal ein wenig genauer, bitte^^

bb