Personal tools
You are here: o studio 110 2016-17 tmp Inf 11 doku doku .py script baum_mC_7.py

Die einzige Konstante im Universum ist die Veränderung.

Heraklit von Ephesus

When you need a function, just declare it.

 

Ego ist eine Illusion.

Marco Asam

Life is like a camera -
focus on what's important
capture the good times,
develop from the negatives
and if things don't work out
take another shot.

Anonymous

 

 

 

 

 

 

 

 

 

baum_mC_7.py

baum_mC_7.py — Python Source, 10Kb

File contents

# Implementation Binärer Suchbaum
# SH 2013-12-03
# Design Pattern: Kompositum
# features: einfügen()
# __str__(), gibGrößtes/Kleinstes(),
# Durchläufe: inOrder(), preOrder(), postOrder()
# gibHoehe(), gibTiefe(Knoten), gibKnotenZahl(), speichern(), laden()
# 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):
        self.element=element
        self.lnach = lnach
        self.rnach = rnach

  
class Abschluss(Knotenelement):
    "Abschluss modelliert Blätter des Baumes"
    def __init__(self):
        "Konstruktor"
        pass                                # keine Attribute 
    
    def einfügen(self, element, altKnot):
        "Blatt einfügen"
        if element < altKnot.element:       # falls neues Element kleiner...
            altKnot.lnach = Knoten(element)
        else:                               # falls neues Element größer ...
            altKnot.rnach = Knoten(element)
        return True
  
    def inOrder(self):                      
        "gibt Leerstring zurück"
        return ""

    def preOrder(self):                     
        "gibt Leerstring zurück"
        return ""

    def postOrder(self):                    
        "gibt Leerstring zurück"
        return ""

    def suchen(self, vergleich):            
        "gibt Misserfolg zurück"
        return False

    def restKnotenZahl(self):
        "gibt Null zurück"
        return 0

    def gibKleinstes(self, altKnot):
        "gibt kleinstes Element zurück"
        return altKnot.element
    
    def löscheKleinstes(self, vorgänger, vorvorgänger):
        "löscht Knoten mit kleinstem Element und gibt dieses zurück"
        vorvorgänger.lnach = vorgänger.rnach
        return vorgänger.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,element):
        "gibt False für nicht enthaltenes Datenelement zurück"
        return False

    def grafik(self,schrittweite):
        "löscht den Ast (3 letzte turtle-Befehle) zu diesem Abschluss"
        undo();undo();undo()



class Knoten(Knotenelement):
    "Knoten und Blätter des Baums"
    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 löscheKleinstes(self, vorgänger, vorvorgänger):
        "löscht Knoten mit kleinstem Element und gibt dieses zurück"
        return self.lnach.löscheKleinstes(self,vorgänger)

    def einfügen(self, element, altKnot):
        "neues Element einfügen"
        if element == self.element:             # vergleiche mit eig. Element... 
            print("Element schon vorhanden!")
            return False
        if element < self.element:              # falls neues Element kleiner... 
            return self.lnach.einfügen(element, self) # ...dann rek. Aufruf links
        else:
            return self.rnach.einfügen(element, self) # ...dann rek. Aufruf rechts

    def inOrder(self):
        "Element sortiert in Zwischenordnung ausgeben"
        return self.lnach.inOrder()+self.element+" "+self.rnach.inOrder()

    def preOrder(self):
        """Elemente in Vorordnung als Zeichenkette mit Zeilenumbruch
        zur Serialisierung des Baumes für Dateiablage"""
        return self.element+"\n"+self.lnach.preOrder()+self.rnach.preOrder()

    def postOrder(self):
        "Elemente in Nachordnung ausgeben"
        return self.lnach.postOrder()+self.rnach.postOrder()+" "+self.element

    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,element):
        "gibt Tiefe eines Knotens(elem) zurück"
        if self.element == element:
            return 0
        elif self.element < element:
            return self.rnach.gibTiefe(element)+1
        else:
            return self.lnach.gibTiefe(element)+1

    def grafik(self,schrittweite):
        "gibt Knoten als Turtle-Grafik in neuem Fenster aus"
        pencolor("black")   # Stiftfarbe 'schwarz' f. Knoten
        write(self.element,align='left',font=('Arial',12,'bold'))# Formatierung Stift
        pencolor("red")     # Stiftfarbe 'rot' für l. Ast
        ort = xcor(),ycor() # Ortskoordinaten zwischenspeichern
        right(45)           # Turtle 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("blue")    # 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, element):
        "erzeuge Binärbaum mit Wurzelknoten"
        self.wurzel = Knoten(element)
        print("Neuer Baum erzeugt")

    def __repr__(self):
        return self.wurzel.inOrder()
        
    def __str__(self):
        return self.wurzel.inOrder()
        
    def einfügen(self, element):
        "Einfügen eines Knotens"
        self.wurzel.einfügen(element, self)
               
    def inOrder(self):
        "liste alle Knoten in sortierter (Haupt-)Reihenfolge"
        return self.wurzel.inOrder()

    def preOrder(self):
        "liste alle Knoten in symmetrischer Reihenfolge"
        return self.wurzel.preOrder()

    def postOrder(self):
        "liste alle Knoten in Nebenreihenfolge"
        return self.wurzel.postOrder()

    def suchen(self,vergleich):
        "Suche nach Zeichenkette"
        return self.wurzel.suchen(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 löscheKleinstes(self):
        "löscht Knoten mit kleinstem Element und gibt dieses zurück"
        return self.wurzel.löscheKleinstes(self,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,element):
        "gibt Tiefe eines Knotens aus"
        if self.suchen(element):
            return self.wurzel.gibTiefe(element)


    def grafik(self,farbe="black"):
        "Baum mittels Turtle-Grafik visualisieren"
        reset()                         # Zeichenfenster löschen
        shape("turtle")                 # Figur "Turtle" setzen
        pensize(2)                      # Stiftbreite
        speed(1)                        # Geschwindigkeit (0, 1-10)
        delay(50)                        # Wartezeit (in ms)
        right(90)                       # Orientierung Turtle nach unten
        self.wurzel.grafik(200)         # starte Zeichnen auf Wurzel
        ht()                            # Turtle verstecken

    def speichern(self,filename = 'baum.txt'):  # speichere in Datei 'filename'
        "Baum in Datei  speichern"
        datei = open(filename,"w")              # öffne Datei 'filename' schreibend
        datei.write(self.preOrder())            # schreibe den preOrder-Extrakt hinein
        datei.close()                           # schließe Datei
        print("Baum in Datei '%s' gespeichert!"%filename) # in bisschen Geplänkel :)

    def laden(self, filename="baum.txt"):
        "Baum aus Datei laden"
        try:                                     # versuche...
            datei = open(filename)               # ...die Datei zu öffnen
            neuBaum = Baum(datei.readline()[:-1])# Auslesen d. 1. Zeile
            for i in datei:                      # Durchschreiten der Zeilen...
                neuBaum.einfügen(i[:-1])         # alles bis aufs letzte Zeichen
            return neuBaum                       # gib den Baum zurück
        except:                                  # Ausnahmebehandlung:
            print("Datei nicht gefunden")        # sag' dem Benutzer...
    
    
if __name__=="__main__":
    b = Baum("Fritz")
    b.einfügen("Boeck")
    b.einfügen("Mecke")
    b.einfügen("Baecker")
    b.einfügen("Bolte")
    b.einfügen("Max")
    b.einfügen("Moritz")
    b.grafik()
    print("Inorder-Durchlauf:   ",b.inOrder())
    print("Preorder-Durchlauf:  ",b.preOrder())
    print("Postorder-Durchlauf:",b.postOrder())
    b.speichern()
    nb = b.laden()
    print(nb.inOrder())
Document Actions