Seite 1 von 1
Bäume in Python
Verfasst: Donnerstag 1. September 2005, 20:00
von Tester
Gibt es in Python eigentlich eine "kanonische" Art, Bäume zu speichern
wie es das für Tupel,Listen und Dictionaries gibt ?
In C++ würde ich das mittels einer Datenstruktur "Knoten" machen, die eine Liste von Zeigern auf die Nachfolger-Knoten enthält, aber in Python ?!
Verfasst: Donnerstag 1. September 2005, 20:05
von jens
Aus Wikipedia:
Der Begriff kanonisch bezeichnet
* in der Informatik eine allgemeingültige und eindeutige Bezeichnung eines Datensatzes
Hört sich für mich nach einem Dict an...
Re: Bäume in Python
Verfasst: Donnerstag 1. September 2005, 21:50
von BlackJack
Tester hat geschrieben:Gibt es in Python eigentlich eine "kanonische" Art, Bäume zu speichern
wie es das für Tupel,Listen und Dictionaries gibt ?
Da es keinen eingebauten Typ `tree` gibt, bleibt nur das Missbrauchen von Tupeln oder Listen oder eben selbst schreiben. Einen eingebauten `tree` gibt's übrigens deswegen nicht, weil es nicht
den Baum gibt, mit dessen API alle glücklich wären und weil man Bäume ziemlich einfach selbst implementieren kann.
In C++ würde ich das mittels einer Datenstruktur "Knoten" machen, die eine Liste von Zeigern auf die Nachfolger-Knoten enthält, aber in Python ?!
Genauso!?
re
Verfasst: Freitag 2. September 2005, 06:22
von abc
Hallo
>>Genauso!?<<
also z.B. mit a=[3,1] b=[4,1] und c=[a,b] für einen Baum mit einer
Wurzel c und 2 Knoten a,b und 4 Blättern 3,1,4,1 oder wie meinst Du das ?
>>Der Begriff kanonisch bezeichnet
* in der Informatik eine allgemeingültige und eindeutige Bezeichnung eines Datensatzes<<
Diese Bedeutung des Worts "kanonisch" kannte ich noch gar nicht.
Ich verwendete das Adjektiv "kanonisch" eher im umgangssprachlichen Sinne von "auf ein Art und Weise, die nach allgemeiner Überzeugung oder
traditionellen Konformismen als guter Standard angesehen wird".
Grüße
Verfasst: Freitag 2. September 2005, 06:32
von jens
In PyLucid werden die Seiten so oganisiert, das jede eine eindeutige ID hat und eine parent-ID, die die ID der übergeortneten Seite ist.
Verfasst: Freitag 2. September 2005, 06:51
von mawe
Hi!
Ein Baum ist doch ein Graph (ach bin ich klug
), also warum schaust Du Dich nicht mal nach Graph-Modulen für Python um. Da gibts einiges.
Gruß, mawe
Verfasst: Freitag 2. September 2005, 08:15
von rayo
Hi
Ich würde es mit Klassen machen:
Code: Alles auswählen
class Node(list):
def __init__(self, parent=None):
self.parent = parent
def append(self, node):
if isinstance(node, Node):
if node.parent == None:
node.parent = self
list.append(self, node)
root = Node()
c1 = Node()
c2 = Node()
root.append(c1)
root.append(c2)
c2.append( Node() )
Die Node-Klasse kann man jetzt beliebig nach seinen Wünschen erweitern. Mit dem Parent kannst du relativ einfach durch den ganzen Baum iterieren.
Gruss
re
Verfasst: Freitag 2. September 2005, 14:09
von abc
rayo, mawe:
Danke ....! Genau so etwas wie das Codestück von Roya habe ich gesucht. Die Denkweise, die man für Python benötigt,
ist offenbar doch ziemlich anders, wenn man von C/C++ herkommt.
Ist schon arg ungewohnt, einem Objekt einfach Daten zuzufügen, ohne
Typdeklaration, ohne Speicheranforderung, ohne explizite Zeigervereinbarung auf den Nachfolger, ohne Speicherrückgabe nach Löschen des Objekts usw... Da bleibt mit Python ja kaum noch Arbeit für den Programmierer übrig
Verfasst: Freitag 2. September 2005, 15:35
von henning
...und man kann sogar "mit einem" Blick erkennen, was der Code macht im Gegensatz zu einer vollständigen C++ - klasse ,-)
(Je nachdem wie sorgfältig mit Einrückungen, Kommentaren, etc... gearbeitet wurde)
Re: re
Verfasst: Freitag 2. September 2005, 22:49
von BlackJack
abc hat geschrieben:Hallo
>>Genauso!?<<
also z.B. mit a=[3,1] b=[4,1] und c=[a,b] für einen Baum mit einer
Wurzel c und 2 Knoten a,b und 4 Blättern 3,1,4,1 oder wie meinst Du das ?
Das meinte ich bei Listen/Tupeln. Mit "Genauso" war gemeint: Genau wie in C++ eine `Node` Klasse mit den Kindknoten als Attribute(n).
>>Der Begriff kanonisch bezeichnet
* in der Informatik eine allgemeingültige und eindeutige Bezeichnung eines Datensatzes<<
Diese Bedeutung des Worts "kanonisch" kannte ich noch gar nicht.
Die Bedeutung kannte ich auch nicht. Ich kenne aus der Informatik auch die Bedeutung einer eindeutigen, quasi "normalisierten" Darstellung von Irgendwas. Irgendwie macht die Def. von Wikipedia nicht wirklich Sinn.