[Python-de] Selbstorganisierender Binaerer Baum

Albert Hermeling Albert.Hermeling at t-online.de
Don Dez 25 22:20:36 CET 2003


Guten Abend,

aus Langeweile habe ich mir die Aufgabe gestellt ein Programm zu schreiben das 
einen binaeren Baum erzeugt. Da das alleine keine richtige Herausforderung 
mehr ist, soll sich dieser Baum auch noch selber aufbauen, sprich neue Knoten 
werden nicht von aussen eingefuegt sondern von der Klasse Node selber. Da das 
ziemlich umstaendlich klingt hier der Code:

class Node:
    def __init__(self,string, parent=None):
        self.app=parent
        self.string=string
        self.lings=0
        self.rechts=0

    def einfuegen(self, string, adresse):
        a=hash(string)
        b=hash(self.string)
        if a > b and self.lings:
            self.lings.einfuegen(string)
        elif a > b and not self.lings:
            self.lings=Node(string, self)
        elif a < b and self.rechts:
            self.rechts.einfuegen(string)
        elif a < b and not self.rechts:
            self.rechts=Node(string, self)
        else:
            self.adressen[adresse]=None

    def suchen(self, string):
        a=hash(string)
        b=hash(self.string)
        if a > b and self.lings:
            self.lings.suchen(string)
        elif a < b and self.rechts:
            self.rechts.suchen(string)
        elif a == b:
            self.ausgabe(self.string)

    def ausgabe(self,a=None):
        if not self.app:
            return a
        else:
            b=getattr(self.app,"ausgabe")
            b(a)

Beschreibung:
Die Methode "einfuegen" erzeugt neue Knoten. Die Methode "suchen" durchsucht 
den Baum nach dem zu suchenden String. Wenn eine Uebereinstimmung gefunden 
wurde wird die Methode "ausgabe" aufgerufen, diese wiederum hangelt sich 
durch den binaeren Baum bis es auf den Rootknoten stoeßst. Der soll dann den 
gesuchten String ausgeben.

Aufruf:
text=["Bettdecke","Gilbert","Wassers","Gefaengnis","Gold","schwenkte","Bett","die","das","dem"]
node=Node("Rootknoten")

# Neue Knoten einfuegen
for item in text:
	node.einfuegen(item)

# String suchen
node.suchen("Wassers")
print node.ausgabe()

Alles funktioniert, bis auf eins, die Methode ausgabe gibt None zurueck. 
Ersetzt man aber return a durch print a funktioniert es. Kann mir einer sagen 
woran das liegt und ob man dieses Problem loesen kann?

Frohe Weihnachten

Albert