[Python-de] binaerer Baum in Python

Julian Schaefer-Jasinski julschae at t-online.de
Fri Oct 26 18:42:14 EDT 2001


> Bis jetzt habe habe ich es mit Listen und Dictionaries versucht. musste
das
> aber erfolglos aufgeben.

Hmmm... verstehe das Problem. Hat mir vor 1 Jahr in der Uni den Rest
gegeben,
als ich ploetzlich Graphen in Python - und damit ohne Zeiger -
implementieren
sollte.... ;-)

Ist mit einzelnen Klassen für ein Node-Objekt, wie auf der Liste
vorgeschlagen,
bestimmt einfacher und übersichtlicher. Dennoch sollte eine Lösung mit
Dictionaries
und Listen möglich sein, wie Du sie vor hattest.

als Dictionary - mit dem Nachteil, dass zwei Knoten niemals denselben Wert
haben können:

  {<ident> : (left_descendant, right_descendant), ...}

oder als Liste - mit dem Nachteil, dass eine "komplizierte" Suchfunktion
nach
Knoten implementiert werden müsste - als zweidimensionale liste.

  [ [<ident>, left_descendant, right_descendant], [ ... ], ...]

Wie gesagt - die vorher vorgestellte Methode ist wahrscheinlich
effiziernter. Dies
nur wegen Deinem Ansatz.

[...]

Um eine sinnvolle Einsortierung in den Baum zu gewaehrleisten, sollte man
wahrscheinlich
Objekt-Klassen mit ueberladenen Vergleichsoperatoren erstellen. Sodass der
Einsortier-
ungsalgorithmus innerhalb des Binaeren Baums immer gleich funzt - egal was
fuer eine
Menge (und vor allem was fuer eine Ordnung auf ihr) Du verwendest.
Hier ein "dummes" Beispiel fuer limitierte Geographie!

# Frankfurt < Nirvana

>>> import UserString
>>> class DummyObject(UserString.UserString):
...  def __ge__(self, other):
...   if (self.data == "Frankfurt"):
...    return(self.data==other)
...   return(1)
...
>>> obj_01 = DummyObject("Frankfurt")
>>> obj_02 = DummyObject("Nirvana")
>>> obj_01 >= obj_02
0
>>> obj_02 >= obj_01
1
>>>

Hoffe, dass das auch geholfen hat.
Gruesse,

Julian


_________________________________________________
J. Schaefer-Jasinski,                                Frankfurt, Germany




More information about the Python-de mailing list