Baumstruktur in c++

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

Nein mehr
[code]
struct Parameter
{
string Nummer;
std::map<string,vector<string>> my_map;
}

die Nummer über den Parametern ist in der struct
und die unter parameter mit mehreren Kindknoten sind in der map!

unskilled

struct Parameter 
{ 
string Nummer; 
std::map<string,vector<string>> my_map; 
}

versteh ich nicht ganz...
was soll my_map hier darstellen?

bb

my_map speicher einen Parameter als Schlüssel (in first) und die dazu gehörigen Knoten speichert dieser als Container, da kann ich ja mehrere durch push_back speicher darunter (als second).

unskilled

struct_master schrieb:

my_map speicher einen Parameter als Schlüssel (in first) und die dazu gehörigen Knoten speichert dieser als Container, da kann ich ja mehrere durch push_back speicher darunter (als second).

na so weit war ich auch schon...
aber irgendwie macht das alles keinen sinn... (für mich) jz noch weniger als ohne deine erklärung
du hast nen struct "parameter", was ganz viele "parameter"-member hat...
und diese member-parameter können ganz viele "knoten" haben(knoten = werte? oder wie kommst du jz plötzlich auf knoten?)

außerdem weiß ich auch absolut gar nicht mehr, was du eigtl machen wolltest...

2 optionen: entweder du schreibst jz noch mal klipp und klar (und ausführlich), was du machen möchtest
oder machst nen neuen thread auf und schreibst dort das ganze hin - die ersten 3 seiten verwirren vrmtl eher als das sie helfen, dich zu verstehen...

aber du solltest auf jeden fall richtig beschreiben, was du machen möchtest und nicht nur, "ich will nen baum mit mehreren knoten" - vll gibts für das, was du machen möchtest ja auch schon irgendwo was fertiges oder ne bessere lösung oder oder oder ;o)

zumindest geht es mir so - vll versteht der rest dich ja besser?!

bb

struct Parameter
{
string Nummer;
std::map<string,vector<string>> my_map;
}

Also das ist meine Struktur,die ich habe.
So jetzt habe ich eine Nummer, die ich dort eintrage. Unter dieser Nummer befinden sich mehrere knoten. Diese Knoten sind gespeichert als Schlüssel(first) in der map. Unter diesen Knoten liegen noch Werte, wie z.B. Bezeichner, Kenner usw.
und diese werden in dem vectro<string> gespeichert. Damit habe ich alles gespeichert was ich benötige. Wenn ich jetzt etwas auslesen möchte suche ich ich nach der Nummer, dann nach dem Schlüssel und wähle mir den Wert deni ich benötige aus.
Ich hoffe, damit konnte ich mich nochmal klarer ausdrücken .