Wie implementiere ich eine Baumstruktur?

Tach,

wie implementiere ich am besten Bäume? Also von der Idee und unabhängig von der Programmiersprache. (allgemein gefasst)

Nehmen wir mal an, ich habe so einen Baum.

A
         /   \
        /     \
       /       \
      B         C
     /\        /\
    /  \      /  \
   /    \    /    \
  B1    B2  C1     C2

Nehmen wir mal an, ich will die einzelnen knoten 'A, B, C, B1, B2, C1, C2' durch ein hash (std::map) ansprechen. wenn ich aber nun alle oben genannten knoten direkt in dem hash speichere, dann hab ich am ende so ne map:

A     B     C    B1   B2   C1    C2

also die knoten scheinen nicht voneinander abzuhängen. genau diese abhängigkeite brauche ich aber.zB beim "abarbeiten" des baumes möchte ich,dass C 'durchlaufen' wird bevor man bei C1,C2 ankommt. Wie realisiere ich das ambesten?

Klar, ich könnte verschachtelte listen verwenden. Also

(A (B(B1, B2), C(C1, C2)) )

Hierbei bestünde aber wieder das problem, dass ich eventuell bei C ein weiteres C3-knoten einfügen will, und zwar über den hash. (ich möchte unbedingt die einzelnen knoten (string-)geben)

Ich stehe gerade sehr arg auf dem schlauch. Könnte mir jemand helfen?
Da muss man doch verschachtelte listen & hashes miteinander kombinieren oder irgendwas an den indices der listen frickeln?

Achso, wollte noch etwas hinzufügen:

Wer gleich mit gidf.de oder ähnlichem kommen will, der sollte hier besser nicht posten und diesen Thread am besten ignorieren.

Julian__

wenn es nur eine liste von werten ist, zum bsp. mal von int-wrten, kann man einfach ein int-array benutzen.

das 1. element ist das oberste (root) element, die children jedes elements sind jeweils an index pos*2 bzw. pos*2+1, wobei pos die position/der index d. entspr. elter-elements im array ist.

... das waere dann ein binaerer baum natuerlich, fuer beliebig viele children pro knoten/element geht das nicht.

mfg,
julian

Julian__ schrieb:

wenn es nur eine liste von werten ist, zum bsp. mal von int-wrten, kann man einfach ein int-array benutzen.

das 1. element ist das oberste (root) element, die children jedes elements sind jeweils an index pos*2 bzw. pos*2+1, wobei pos die position/der index d. entspr. elter-elements im array ist.

... das waere dann ein binaerer baum natuerlich, fuer beliebig viele children pro knoten/element geht das nicht.

mfg,
julian

Öhm aber ich wollte die einzelnen Knoten per string (also hash) ansprechen.

frenki

Mach deinen String einfach als.

"A/B/B2".

Dann kannst du einen ganz normalen Baum implementieren (den mit den zwei Pointern auf linkes und rechtes Element) und dich über diesen "Pfad" zu dem gewünschten Element durchhangeln.

Badestrand

IchMagBäume schrieb:

beim "abarbeiten" des baumes möchte ich,dass C 'durchlaufen' wird bevor man bei C1,C2 ankommt. Wie realisiere ich das ambesten?

Evtl ein Hash-Algorithmus, wo ein kleinerer Hashwert für einen "kleineren" String steht?

Tanren

Bäume implementiert man so das du eine Datenstruktur hast die einen Knoten des Baums representiert.
Diese Datenstruktur enthält den Wert des Elements (können auch mehrere sein)
und Verweise auf die Kinder. Bei einem Binären Baum hast du genau zwei Verweise
einen für das linke Kind einen für das rechte.
Bei Bäumen bei denen ein Element mehr als zwei Kinder haben kann hast du dann halt eine Liste mit Verweisen.

Du solltest aber besser mal konkret sagen was deine Datenstruktur den genau können muss. Vielleicht brauchst du ja gar keinen Baum sondern eine Hash-Tabelle oder was anderes.

rüdiger

http://magazin.c-plusplus.net/artikel/Binary%20Heaps