Bäume in Python

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

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

[BlackJack]

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]

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

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

[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

[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

[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

[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)

[BlackJack]

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.