Bäume in Python

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.
Tester

Bäume in Python

Beitragvon Tester » Donnerstag 1. September 2005, 20:00

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 ?!
Benutzeravatar
jens
Moderator
Beiträge: 8458
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Beitragvon jens » Donnerstag 1. September 2005, 20:05

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...

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
BlackJack

Re: Bäume in Python

Beitragvon BlackJack » Donnerstag 1. September 2005, 21:50

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!?
abc

re

Beitragvon abc » Freitag 2. September 2005, 06:22

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
Benutzeravatar
jens
Moderator
Beiträge: 8458
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Beitragvon jens » Freitag 2. September 2005, 06:32

In PyLucid werden die Seiten so oganisiert, das jede eine eindeutige ID hat und eine parent-ID, die die ID der übergeortneten Seite ist.

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Beitragvon mawe » Freitag 2. September 2005, 06:51

Hi!

Ein Baum ist doch ein Graph (ach bin ich klug :D), also warum schaust Du Dich nicht mal nach Graph-Modulen für Python um. Da gibts einiges.

Gruß, mawe
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Beitragvon rayo » Freitag 2. September 2005, 08:15

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
abc

re

Beitragvon abc » Freitag 2. September 2005, 14:09

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 :)
henning
User
Beiträge: 274
Registriert: Dienstag 26. Juli 2005, 18:37

Beitragvon henning » Freitag 2. September 2005, 15:35

...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)
BlackJack

Re: re

Beitragvon BlackJack » Freitag 2. September 2005, 22:49

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.

Wer ist online?

Mitglieder in diesem Forum: brainstir, Yahoo [Bot]