[Python-de] binaerer Baum in Python

Albert Hermeling Albert.Hermeling at t-online.de
Sat Oct 27 00:50:59 EDT 2001


Am Freitag, 26. Oktober 2001 17:42 schrieben Sie:


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


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

Mag sein, meine Idee war die das ich Listen ineinander verschachteln wollte. 
Dabei habe ich mir folgende Lösung ausgedacht:

Gegeben sei folgender String: "Sein oder Nichtsein das ist hier die Frage"

1. Von jedem Wort wird der ASCII-Wert berechnet.
2. Das erste Wort ist die Wurzel (hier "sein")
3. Ist Wort kleiner als Knoten > Links, ist Wort größer als Knoten >rechts.
4. Links und Rechts sind in den Listen 0 und 1.
5. Wenn Liste(n) initialisiert wird ist Index 0 = None und Index 1 = None.

Nach meinen Schema würde das Ganze folgendermaßen ablaufen:

1. Liste "sein" erzeugen
2. Liste "oder" erzeugen und als rechter Sohn von Liste "sein" einordnen.
3. Liste "nichtsein" erzeugen und als linker Sohn von Liste "sein" einordnen.
4. Liste "das" erzeugen und als linker Sohn von Liste "oder" einordnen
5. Liste "ist" erzeugen und als rechter Sohn von Liste "das" einordnen
6. Liste "hier" erzeugen und als linker Sohn von Liste "ist" einordnen
7. Liste "die" erzeugen und als linker Sohn von Liste "hier" einordnen
8. Liste "Frage" erzeugen und als linker Sohn von Liste "Nichtsein einordnen.

Tja das Funktioniert so leider nicht. Denn die einzelnen Listen haben in den 
Listen keinen Namen und lassen sich auch nicht erzeugen (Habe ich zumindest 
nicht rausgefunden). Außerdem wird das einfügen der Listen mit zunehmender 
Tiefe immer aufwendiger und unübersichtlicher. 

> als Dictionary - mit dem Nachteil, dass zwei Knoten niemals denselben Wert
> haben können:
Wenn das gehen würde hätte man die Information Doppelt abgespeichert was in 
einem Baum meines Erachtens unnötig ist.


> oder als Liste - mit dem Nachteil, dass eine "komplizierte" Suchfunktion
> nach
> Knoten implementiert werden müsste - als zweidimensionale liste.
>
>   [ [<ident>, left_descendant, right_descendant], [ ... ], ...]
Das leuchtet mir nicht so recht ein. Mit ident meinst du woll Index aber wie 
habe ich mir jetzt den Baum vorzustellen?

> Um eine sinnvolle Einsortierung in den Baum zu gewaehrleisten, sollte man
> wahrscheinlich
> Objekt-Klassen mit ueberladenen Vergleichsoperatoren erstellen.
Was meinst du mit ueberladenen Vergleichsoperatoren?

> 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.
Nein leider nicht :-(( faIls es Dir nicht zu viel mühe macht würde ich mich 
über ein paar erklärende Worte sehr freuen.

mfg

Albert



More information about the Python-de mailing list