baum_kompositum_turtle.py
baum_kompositum_turtle.py
—
Python Source,
9 KB (9818 bytes)
Dateiinhalt
# Implementation Binärer Suchbaum
# Design Pattern: Kompositum
# features: suchen(), einfügen(), __str__(), gibGrößtes/Kleinstes(),
# Durchläufe: inOrder(), preOrder(), postOrder()
# gibHoehe(), gibTiefe(Knoten), gibKnotenZahl(), speichern(), laden()
# grafik() = Turtle-Grafik
from turtle import * # Turtle-Grafik
class Knotenelement(object):
"abstrakte Klasse für Knoten und Abschluss eines binären Baumes"
def __init__(self, element, lnach, rnach):
"Konstruktor"
self.element=element
self.lnach = lnach
self.rnach = rnach
class Abschluss(Knotenelement): # 'pro forma'-Vererbung
"Modelliert Blätter des Binärbaumes"
def __init__(self):
"Konstruktor"
pass # tu' nix
def einfügen(self, neuKnot, altKnot):
"Blatt einfügen"
if neuKnot < altKnot.element: # falls neues Element kleiner...
altKnot.lnach = Knoten(neuKnot)
else: # falls neues Element größer ...
altKnot.rnach = Knoten(neuKnot)
return True
def inOrder(self): # tritt nicht in Erscheinung
"keine Information, da leer"
pass
def preOrder(self): # tritt nicht in Erscheinung
"keine Information, da leer"
return ""
def postOrder(self): # tritt nicht in Erscheinung
"keine Information, da leer"
pass
def suchen(self, vergleich):
"gibt NICHTS zurück"
return False
def restKnotenZahl(self):
"gibt Null zurück"
return 0
def __str__(self):
return "-"
def gibKleinstes(self, altKnot):
"gibt kleinstes Element zurück"
return altKnot.element
def gibGrößtes(self, altKnot):
"gibt größtes Element zurück"
return altKnot.element
def gibHöhe(self):
"gibt Hoehe -1 zurück"
return -1
def gibTiefe(self,elem):
"gibt False für nicht enthaltenes Datenelement zurück"
return False
def grafik(self,schrittweite):
"löscht den Ast (die 3 letzten turtle-Befehle) zu diesem Abschluss"
undo();undo();undo()
class Knoten(Knotenelement):
"modelliert Knoten des Binärbaums"
def __init__(self, element, lnach=Abschluss(), rnach=Abschluss()):
Knotenelement.__init__(self, element, lnach, rnach) # Aufruf OKl.konstr.
def __str__(self):
return self.element # gib Element auf Konsole aus
def gibGrößtes(self, altKnot):
"kleinster Knoten im Teilbaum"
return self.rnach.gibGrößtes(self)
def gibKleinstes(self, altKnot):
"größter Knoten im Teilbaum"
return self.lnach.gibKleinstes(self)
def einfügen(self, neuKnot, altKnot):
"neues Element einfügen"
if neuKnot == self.element: # vergleiche mit eig. Element...
print("Element schon vorhanden!")
return False
if neuKnot < self.element: # falls neues Element kleiner...
return self.lnach.einfügen(neuKnot, self) # dann rek. Aufruf links
else:
return self.rnach.einfügen(neuKnot, self) # dann rek. Aufruf rechts
def inOrder(self):
"Element sortiert ausgeben"
self.lnach.inOrder()
print(self.element, end=' ')
self.rnach.inOrder()
def preOrder(self):
"""Elemente als Zeichenkette mit Zeilenumbruch
zur Serialisierung des Baumes für Dateiablage"""
print(self.element, end=" ")
self.lnach.preOrder()
self.rnach.preOrder()
def postOrder(self):
"Element ausgeben"
self.lnach.postOrder()
self.rnach.postOrder()
print(self.element, end=" ")
def suchen(self, vergleich):
"Suche nach Zeichenkette"
if self.element == vergleich: # ist meine Element das Gesuchte?
return True # ...gib Erfolgsmeldung zurück
elif self.element < vergleich: # ist das Gesuchte größer...
return self.rnach.suchen(vergleich) # ...suche im r. Teilbaum weiter
else: # ist das Gesuchte kleiner...
return self.lnach.suchen(vergleich) # ...suche im l. Teilbaum weiter
def restKnotenZahl(self):
"gibt Anzahl der Knoten zurück"
return self.lnach.restKnotenZahl()+self.rnach.restKnotenZahl()+1
def gibHöhe(self):
"gibt größere Teilbaumhöhe zurück"
gHl = self.lnach.gibHöhe()
gHr = self.rnach.gibHöhe()
if gHl >= gHr:
return self.lnach.gibHöhe()+1
else:
return self.rnach.gibHöhe()+1
def gibTiefe(self,elem):
"gibt Tiefe eines Knotens(elem) zurück"
if self.element == elem:
return 0
elif self.element < elem:
return self.rnach.gibTiefe(elem)+1
else:
return self.lnach.gibTiefe(elem)+1
def grafik(self,schrittweite,farbeLinks="red", farbeRechts="blue"):
"gibt Knoten als Turtle-Grafik aus"
pencolor("black") # Stiftfarbe
write(self.element,align='left',
font=('Arial',12,'bold')) # Ausgabe Element + Schriftormatierung
pencolor(farbeLinks) # Stiftfarbe 'rot' für linken Ast
ort = pos() # Ortskoordinaten zwischenspeichern
right(45) # Rechtsschwenk für l. Ast
fd(schrittweite) # l. Ast auslaufen
left(45) # Linksschwenk in Senkrechte
self.lnach.grafik(schrittweite*0.5) # lnach zeichnen...
penup() # Stift hoch
setpos(ort) # Ursprungsort aufsuchen
pendown() # Stift runter
pencolor(farbeRechts) # Stiftfarbe 'blau' für r. Ast
left(45) # Turtle Linksschwenk f. r. Ast
fd(schrittweite) # r. Ast auslaufen
right(45) # Rechtsschwenk in Senkrechte
self.rnach.grafik(schrittweite*0.5) # rnach zeichnen...
setpos(ort) # Ursprungsort aufsuchen
class Baum(object):
"""Klasse implementiert binären Baum"""
def __init__(self, neuKnot):
"erzeuge Binärbaum mit Wurzel [string]"
self.wurzel = Knoten(neuKnot)
print("Neuer Baum erzeugt")
def __str__(self):
return self.inOrder()
def einfügen(self, neuKnot):
"Einfügen eines Knoten am Ende (ws)"
self.wurzel.einfügen(neuKnot, self)
def inOrder(self):
"liste alle Knoten in sortierter (Haupt-)Reihenfolge"
self.wurzel.inOrder()
def preOrder(self):
"liste alle Knoten in symmetrischer Reihenfolge"
return self.wurzel.preOrder()
def postOrder(self):
"liste alle Knoten in Nebenreihenfolge"
self.wurzel.postOrder()
def speichern(self, dateiname='binbaum.txt'):
"Baum in Datei 'baum.txt' speichern"
datei = open(dateiname,"w")
datei.write(self.preOrder())
datei.close()
print("Baum gespeichert!")
def laden(self, dateiname="baum.txt"):
"Baum aus Datei laden"
try:
datei = open(dateiname)
knotenliste = datei.readlines()
baum = Baum(knotenliste[0][:-1])
for i in knotenliste[1:]:
baum.einfügen(i[:-1])
return baum
except:
print("Datei nicht vorhanden")
def suchen(self,vergleich):
"Suche nach Zeichenkette"
return self.wurzel.suchen(str(vergleich))
def knotenZahl(self):
"gibt Anzahl der Knoten im Baum"
return self.wurzel.restKnotenZahl()
def gibKleinstes(self):
"gibt kleinstes Element zurück"
return self.wurzel.gibKleinstes(self)
def gibGrößtes(self):
"gibt größtes Element zurück"
return self.wurzel.gibGrößtes(self)
def gibHöhe(self):
"gibt Höhe des Baums zurück"
return self.wurzel.gibHöhe()
def gibTiefe(self,elem):
"gibt Tiefe eines Knotens aus"
if self.suchen(str(elem)):
return self.wurzel.gibTiefe(str(elem))
def grafik(self,farbe="black"):
"Baum mittels Turtle-Grafik visualisieren"
reset() # Zeichenfenster + Turtle auf Anfang
title("Binärbaum 'Max&Moritz'") # Benenne Turtle-Fenster
bgpic("MaxMoritz.gif") # Hintergrundbild f. Fenster
shape("classic") # klassisches Turtle-Symbol
pencolor(farbe) # Stiftfarbe
pensize(2) # Stiftdicke
speed(4) # Geschwindigkeit auf "mittelschnell"
delay(20) # Verzögerung festlegen
right(90) # Orientierung Turtle nach unten
self.wurzel.grafik(200) # Grafik-Funktion auf Wurzelknoten aufrufen
ht() # verstecken
if __name__=="__main__": # Falls Skript als Hauptprogramm ausgeführt..
b = Baum("Fritz") # erzeuge Baum
b.einfügen("Boeck") # füge Knoten hinzu...
b.einfügen("Mecke")
b.einfügen("Baecker")
b.einfügen("Bolte")
b.einfügen("Max")
b.einfügen("Moritz")
b.grafik() # zeichne Baum