Baum implementieren

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
CoderGirl
User
Beiträge: 74
Registriert: Samstag 22. April 2017, 17:47

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
Nur ein Mädchen, das nie so viel weiss, wie die Jungs :ugeek:
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

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
User
Beiträge: 37
Registriert: Montag 8. Mai 2017, 15:26

Es kommt drauf an was du später damit machen willst.
Benutzeravatar
CoderGirl
User
Beiträge: 74
Registriert: Samstag 22. April 2017, 17:47

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

:)
Nur ein Mädchen, das nie so viel weiss, wie die Jungs :ugeek:
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. ;-)
Benutzeravatar
CoderGirl
User
Beiträge: 74
Registriert: Samstag 22. April 2017, 17:47

@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: :lol:
Nur ein Mädchen, das nie so viel weiss, wie die Jungs :ugeek:
Antworten