Baum implementieren

[CoderGirl]

Hallo

ich würde gerne einen binären Baum implementieren und an den Knoten dann Informationen
wie name und ID ablegen.
Später will ich auch auf die konkrete ID des Baumknotens zugreifen können?

Wie würdet ihr denn dies am besten umsetzen?
Gibt es da eine besonders gut passende Struktur für?

lg
codergirl

[__deets__]

Kannste halten wie ein Dachdecker

Du kannst ein Objekt nehmen:

Code: Alles auswählen

class Node(object);

    def __init__(self, left=None, right=None, data=None):
          ...

Du kannst einfach verschachtelte Listen nehmen und zB Tupel mit den Daten

Code: Alles auswählen

[[("id", "was anderes)], [("andere id", "noch was anderes")]]

Natuerlich auch dictionarys (sehen dann im Grunde aus wie die Objekte, nur mit keys statt Attributen).

Und natuerlich auch noch mehr, zB die klassische Array-Repraensentation, bei der du die Kinder eines Elementes i an der Stelle 2*i und 2*i + 1 (oder so aehnlich, genaueres https://de.wikipedia.org/wiki/Bin%C3%A4 ... _ein_Array ) stehen. Da hast du dann bei einem unterbesetzten Baum viele "Leerstellen".

Was davon nun das beste ist haengt sehr von deinem Anwendungszweck ab. Ist der baum ausgeglichen, kennst du seine endgueltige Groesse, musst du ihn veraendern.. usw.

[BlackJack]

Eventuell muss es auch gar kein binärer Baum sein und ein Wörterbuch ganz normal als Abbildung ID auf Knoten(daten) würde ausreichen. Oder eine Heapqueue in einer Liste (da gibt's ein Modul in der Standardbibliothek).

[beertonic]

Es kommt drauf an was du später damit machen willst.

[CoderGirl]

Ok danke euch

damit kann ich was anfangen.
Wollte nur nachfragen, ob es da nicht mal wieder die Megastruktur gibt
und ich am Ende mich unnötig rumschlage

[BlackJack]

@CoderGirl: Naja, wenn man irgendwelche Standardgraphenalgorithmen auf die Knoten loslassen möchte würde ich NetworkX für die Knoten verwenden.

Bezüglich Deiner Signatur („Leider kann man im Leben nicht alles pürieren....“) empfehle ich eine Suche nach „will it blend“ auf YouTube. Ich wette da ist jemand anderer Meinung.

[CoderGirl]

@BlackJack:

Naja, ich dachte an den Baum, die die Daten in einer binären Struktur vorliegen.
Werd es wohl über ein dictionary machen und den Key als ID verwenden

Und das Video: