baumstruktur basteln

Hi,

ich moechte gerne eine baumstruktur basteln, die in etwa so aussieht:

struct baumstruktur
{
std::string daten;
struct baumstruktur* linkes Kind;
struct baumstruktur* rechtes Kind;
}

Und mit dieser möchte ich dann durch rekursive Aufrufe einen Datenbaum basteln.
Allerdings habe ich die Struktur ja gerade erst angelegt, kann also innerhalb ja keine pointer darauf erzeugen.

Hat jemand eine Idee, wie man das loesen kann. Macht es so ueberhaupt Sinn?

Danke, Flo

Blue-Tiger

flo1234567 schrieb:

Hi,

ich moechte gerne eine baumstruktur basteln, die in etwa so aussieht:

struct baumstruktur
{
std::string daten;
struct baumstruktur* linkes Kind;
struct baumstruktur* rechtes Kind;
}

Und mit dieser möchte ich dann durch rekursive Aufrufe einen Datenbaum basteln.
Allerdings habe ich die Struktur ja gerade erst angelegt, kann also innerhalb ja keine pointer darauf erzeugen.

Hat jemand eine Idee, wie man das loesen kann. Macht es so ueberhaupt Sinn?

Danke, Flo

du suchst sowas glaub ich:

// erstellen der Baumwurzel
Baumstruktur* root = new Baumstruktur;
root->daten = "foo";
root->left = 0;
root->right = 0;

// einhaengen eines Elements im linken Teilbaum:
// (zuerst einhaengen, dann initialisieren)
root->left = new Baumstruktur;
root->left->daten = "bar";
root->left->left = 0;
root->left->right = 0;

// oder alternativ:
// (zuerst initialisieren, dann einhaengen)
Baumstruktur* newNode = new Baumstruktur;
newNode->daten = "bar";
newNode->left = 0;
newNode->right = 0;
root->left = newNode;

Uebrigens macht man in C++ eher eine Klasse draus, als lang mit structs rumzuhantieren

miller_m

Blue-Tiger schrieb:

Uebrigens macht man in C++ eher eine Klasse draus, als lang mit structs rumzuhantieren

struct == klasse
wenn man von den vorgabezugriffsrechten ab sieht

Das ist aber dann noch kein Baum, sondern eine doppelt verkettete Liste. Ein Baum wirds erst, wenn das ganze ausbalanciert wird. Siehe z.B. AVL-Tree.

Und um das ganze etwas dynamischer zu gestalten, sollte man ein Array, oder besser das Vector-Template verwenden. Man will ja schließlich nicht per Hand 100 newNode Variablen anlegen müssen.

Hmm,

vielen Dank für Eure Anregungen. Mal sehen, was ich damit anfangen kann.
Das mit der Klasse ist in etwa das was ich will.
Das Template Vector habe ich mir als eine Art Stapel vorgestellt. Ich glaube, dass ist nicht das, was ich will. Aber ich schaue es mir noch mal genauer an, habe damit noch nicht viel gemacht. Vielleicht verstehe ich dann, was Du meinst.
Danke schon mal,
flo

Hi,
ich hingegen glaube, eine 'std::vector<baumstruktur> Baum;' Variable ist genau das, was du brauchst, um deinen gesamten Baum darin verwalten zu können.

Wie sonst solltest du komfortabel die verschiedenen Nodes erzeugen und ansprechen können? Indem du für jede eine einzelne Variable anlegst? Die einzige sinnvolle non-vector Methode ist ein einfaches Array zu verwenden, was aber letztendlich wie das vector Template funktioniert, nur das letzteres viel einfacher zu bedienen ist, wenn es darum geht dynamisch Elemente in ein Array zu packen.

Einfach mit Baum.push_back(newnode); deine neue Node dem Array hinzufügen und fertig.

Greetz,
Neo

Ich bin in der STL nicht so bewandert... Dort gibt es Klassen für binäre Bäume?

Ansonsten ist das wovon ihr redet eine Liste (verkettete Liste, doppelt verkettete Liste), aber keine Baum. Bäume sind grundsätzlich balanciert, sonst ist es eben kein Baum, sondern eine Liste.

Joe_M. schrieb:

Ansonsten ist das wovon ihr redet eine Liste (verkettete Liste, doppelt verkettete Liste), aber keine Baum. Bäume sind grundsätzlich balanciert, sonst ist es eben kein Baum, sondern eine Liste.

Eine Liste ist ein degenerierter Baum. Ein Baum muss nicht unbedingt balanciert sein.

wikipedia schrieb:

Ein Baum ist ein einfacher Graph, der

1. zusammenhängend und ohne Kreis ist oder
2. in dem je zwei beliebige verschiedene Knoten durch höchstens einen Pfad verbunden sind oder
3. genau einen Knoten mehr als Kanten hat (#v=#e+1), falls der Graph zusammenhängend ist oder
4. genau einen Knoten mehr als Kanten hat, falls der Graph kreisfrei ist oder
5. zusammenhängend ist und falls durch Hinzunahme einer beliebigen neuen Kante ein Kreis entsteht.

http://de.wikipedia.org/wiki/Baum_(Graphentheorie)

nillable schrieb:

Eine Liste ist ein degenerierter Baum.

Nur eine einfach verkettete Liste.

Nun ja, ich bin immer noch dabei, zu lernen, wie man überhaupt Klassen anlegt.
Da scheitere ich momentan noch kläglich...
Bin noch Neuling und habe mich bis jetzt drum gedrückt....
Aber gut.
Nein, mein Baum wird nicht ausbalanciert sein. Mir geht es nicht primär um eine effektive Datenspeicherung sondern um die Baumstruktur an sich, die mir gegeben wird. Die Daten haben also definierte Vaterknoten und Geschwisterknoten.
Was ich mit Vector anfangen soll, ist mir immer noch nicht klar. Ich möchte meinen Datensatz durcharbeiten, der mir sagt, Datensatz soundso ist linkes oder rechtes Kind und so fort. Jedesmal erzeuge ich dann ein neues Objekt von dem ausgesehen, in dem ich gerade bin und wenn ich meinen Datensatz durchhabe, habe ich einen fertigen Baum, den ich wiederum von der Wurzel zu den Blättern (oder eher umgekehrt) durcharbeiten kann.
Soo ich es hinbekomme...
Danke Euch für die vielen Beiträge.

Blue-Tiger

miller_m schrieb:

Blue-Tiger schrieb:

Uebrigens macht man in C++ eher eine Klasse draus, als lang mit structs rumzuhantieren

struct == klasse
wenn man von den vorgabezugriffsrechten ab sieht

wir haben sehr unterschiedliche Vorstellungen von Klassen o_0