[Python-de] binaerer Baum in Python

Julian Schaefer-Jasinski julschae at t-online.de
Sat Oct 27 03:55:25 EDT 2001


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

Tut mir leid. Aber so ganz habe ich noch nicht verstanden, was Du da machen
willst.
Beachte, dass das tolle an binaeren Baeumen ist, dass man einen bereits
eingefuegten
Knoten nicht mehr in seiner Position zu veraendern braucht... so wie ich
Deinen An-
satz verstanden hatte, musst Du um die Listen so zu verschachteln Werte
ueber-
schreiben... anders: wo ist der Name des Referenzelementes das aktuellen
Teil-
baums. <hmmm. haette ich jetzt wahrscheinlich auch nicht verstanden. deshalb
ein beispiel fuer meine listenstruktur>:

[<ident>, left_leaf, right_leaf]

None
["sein", None, None]
["sein", ["oder", None, None], None]
["sein", ["oder", ["nichtsein", None, None], None], None]
["sein", ["oder", ["nichtsein", ["das", None, None], None], None], None]
["sein", ["oder", ["nichtsein", ["das", None, ["ist", None, None], None],
None], None]
["sein", ["oder", ["nichtsein", ["das", None, ["ist", ["hier", None, None],
None], None], None], None]
["sein", ["oder", ["nichtsein", ["das", None, ["ist", ["hier", ["die", None,
None], None], None], None], None], None]
["sein", ["oder", ["nichtsein", ["das", None, ["ist", ["hier", ["die", None,
["frage", None, None]], None], None], None], None], None]

Hoffe das stimmt alles so... ist schon verdammt spaet ;-) - Beschwerden dann
bitte an mich!
Habe das ganze schnell mal getestet:

--------------------->
import types

def realy_ins_node(obj, ref):
  if not (type(ref) == types.NoneType):    # <- platz fuer einzufuegendes
element noch nicht gefunden
    if (obj < ref[0]):
      return([ref[0], realy_ins_node(obj, ref[1]), ref[2]])
    else:
      return([ref[0], ref[1], realy_ins_node(obj, ref[2])])
  else:        # <- platz fuer einzufuegendes element ist gefunden: None!
    return([obj, None, None])

class BinTree:
  def __init__(self):
    self.storage = None

  def ins_node(self, obj):
    self.storage = realy_ins_node(obj, self.storage)

sample = "sein oder nichtsein das ist hier die frage"
bintree = BinTree()

import string
words = string.split(sample, " ")

for word in words:
  bintree.ins_node(word)

print bintree.storage

<----------------------------

frage mich bitte nicht warum ins_node() nicht in der klassendefinition
steckt.
Es gab ne fehlermeldung (wahrscheinlich bei rekursion), dass self nicht
bekannt
sei... wie auch immer...

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

naja - ob es sinnvoll ist seine informations-entities nicht eindeutig zu
machen ist eine
andere geschichte. erst einmal ist es in einem baum moeglich mehrere knoten
mit
demselben namen zu haben. deren position ist gemaess des verwendeten
operators
(ordnung) bei der einsortierung eindeutig definiert.


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

vielleicht war das etwas weit gegriffen. mir ging es darum, dass du nicht
immer
strings als objekte verwenden wirst, sondern evt etwas wie autokennzeichen,
die einer eigenen ordnung gehorchen koennen (nicht unbedingt
lexikografisch).
eine moegliche ordnung waere nach groesse der staedte und innerhalb der
staedte lexikografisch. damit dein relationsoperator im
binaerbaum-einsortier-
algorithmus funktioniert (gemaess unserer autokennzeichen-ordnung)
definierst
du diese halt einfach extern. ok - eigentlich hat das ganze nicht wirklich
was
mit deinem problem zu tun - als sorry ;-)

wenn ich nicht schon total eingeschlafen bin, dann funzt der code sogar.
wenn dir das immernoch nicht hilft, dann schreibe mir doch bitte einmal
auf wie der "magische Satz" einsortiert in deiner datenstruktur aussieht.
denn in letzter konsequenz habe ich deine methode noch nicht durchschaut.

Also z.B.:
["sein", ["oder", ["nichtsein", ["das", None, ["ist", ["hier", ["die", None,
["frage", None, None]], None], None], None], None], None]

Gruesse,

Julian

_____________________________________________________
J. Schaefer-Jasinski                            Frankfurt, Germany




More information about the Python-de mailing list