Baum mit mehr als zwei Nachfolgern?

Moppel

Hallöchen!

Ich bin ein ziemlicher Newbie auf dem Gebiet der Programmierung.
Trotzdem brauche ich für eine Aufgabe eine Baumstruktur.
Allerdings ist zum Start des Programms nicht bekannt, wie viele Nachfolger ein Knoten haben kann. Dies wird erst anhand der Eingaben des Benutzers ermittelt.
Ein Binärbaum hat ja in aller Regel folgende Struktur:

struct knoten{
int wert;
struct knoten *links;
struct knoten *rechts;
};

Wenn man mehr als zwei Nachfolger hat, kann man das (statisch) ja wie folgt realisieren (in diesem Fall z.B. maximal fünf Nachfolger):

struct knoten{
int wert;
struct knoten zeiger[5];
};

Wenn ich nun jedoch gar nicht weiß, wie viele Nachfolger es sein können, wie realisiere ich das dann?
Das muss man dann wohl irgendwie dynamisch über Pointer realiseren, oder?
Ich habe davon leider überhaupt keinen Plan.
Wäre sehr nett, wenn mir da jemand einen Tipp geben könnte.
Schon mal vielen Dank im Voraus.

MfG Moppel

In dem du ne dynamische Liste nimmst anstatt ein festes Array.

Moppel

Aha.

Moppel schrieb:

Aha.

Okay.

Piioo

benutze einen Vector solltest recht viel im Netz zu finden.

Sonnst gibt es noch Queue, Stack etc. falls du ein FIFO oder LIFO Konzept benutzen willst... (bevor du fragst First In First Out, Last In First Out)

Solltest mit Google viel informationen zu finden koennen..

Blue-Tiger

ich wuerd auch Piio zustimmen, mit einem std::vector tust du dir sicher am leichtesten.

Ein vector benutzt du eigentlich wie ein Array, das automatisch groesser wird wenn du's brauchst, einfaches Beispiel:

#include <vector>
using namespace std;  // ich hoff das hast du bisher immer so gemacht :) 

int main()
{
    vector<int> meinVector; // vector<int> bedeutet: das ist ein vector, der int's speichert

    // was AM ENDE es Vectors (also an der letzten Position) einfuegen
    meinVector.push_back(42);
    meinVector.push_back(23);

   // schauen wie viele Elemente im Vector sind:
   cout << "Elemente im vecor: " << meinVector.size() << '\n';  // sollte "2" ausgeben

   // Auf Elemente zugreifen funkioniert wie bei einem Array:
   cout << "Erstes Element: " << meinVector[0] << '\n';    // gibt "42"
   cout << "Zweites Element: " << meinVector[1] << '\n';   // gibt "23"

   // Element Aendern:
   meinVector[1] = 25;
   ++meinVector[1];

   cout << "Zweites Element: " << meinVector[1] << '\n';   // gibt "26"

   return 0;
}

Jetzt alles klar? hoff ich doch

um mal am ursprungsproblem zu bleiben...

struct knoten{
int wert;
struct knoten *links;
struct knoten *rechts;
};

ist ein binärer baum.

für beliebige knoten (asymmetrischer baum) sähe das struct vielleicht so aus:

struct knoten{
int wert;
std::vector<*knoten> kinder;
};

(oder std::vector<struct knoten> kinder; ? benutz structs so selten ^^)

Moppel

Danke an alle, vor allem an "Piioo", "Blue-Tiger" und "longpointer".
Die erste Antwort von "std::list" war sicherlich gut gemeint, aber bei meinen bescheidenen Programmierkenntnissen hat mir das nicht wirklich weiter geholfen. Und der Beitrag von "Kater Klausi" ... nun ja, was soll ich dazu sagen: mehr oder weniger sinnfrei bzw. einfach nur SPAM.
Aber allen anderen ein dickes Dankeschön. Jetzt weiß ich wenigstens in welche Richtung ich meine Anstrengungen richten muss.
DANKE!!!

Ciao Moppel

chris90

Moppel schrieb:

Und der Beitrag von "Kater Klausi" ... nun ja, was soll ich dazu sagen: mehr oder weniger sinnfrei bzw. einfach nur SPAM.

Nuja, er meint eben, dass man immer formulieren sollte WAS man nicht versteht. Ein Beitrag mit " " ist zwar emotional ausreichend, aber nicht effizient wenn's um Problemlösung geht. Schreib nächstes mal doch lieber: "Ich hab folgendes mit lists versucht <blblbl>" bzw "welche header brauche ich für lists?" oder meinetwegen auch "lists sind mir zu kompliziert im umgang <weil...> ! gibt es auch eine weniger komplexe methode um dynamische arrays anzulegen?"

viele grüße,
chris90

chris90 schrieb:

Moppel schrieb:

Und der Beitrag von "Kater Klausi" ... nun ja, was soll ich dazu sagen: mehr oder weniger sinnfrei bzw. einfach nur SPAM.

Nuja, er meint eben, dass man immer formulieren sollte WAS man nicht versteht. Ein Beitrag mit " " ist zwar emotional ausreichend, aber nicht effizient wenn's um Problemlösung geht. Schreib nächstes mal doch lieber: "Ich hab folgendes mit lists versucht <blblbl>" bzw "welche header brauche ich für lists?" oder meinetwegen auch "lists sind mir zu kompliziert im umgang <weil...> ! gibt es auch eine weniger komplexe methode um dynamische arrays anzulegen?"

viele grüße,
chris90