Eine mögliche Implementation

Binärbäume in Python

Nun wollen wir den nächsten Schritt gehen und unsere Datenstruktur Binärbaum in Python implementieren. Falls Du dich nicht mehr so gut an objektorientiertes Programmieren in Python erinnerst, lies es vorher am besten noch einmal hier in den jeweiligen Unterkapiteln zu Python nach.

Solltest Du es dir zutrauen, kannst Du gerne versuchen Binärbäume zunächst einmal selbst zu implementieren. Wenn Du eine andere Idee zur Implementation hast als die Vorgestellte, erstelle erst ein Klassendiagramm zu deiner Idee.

Ansonsten kannst Du einfach den folgenden Code betrachten:

class Knoten(object):
    def __init__(self, wert):
        self.wert=wert
        self.linkesKind = None
        self.rechtesKind =None
	
class Baum(object):
    def __init__(self):
        self.wurzel = None

Das ist natürlich eine sehr simple und spartanische Implementation eines Binärbaums. Allerdings erfüllt sie (zumindest vorerst) unsere Bedürfnisse. Um das zu testen, wollen wir nun die binäre Suche auf unseren Bäumen implementieren.

Aufgabe 1

(a) Entwickle auf Basis unseres Algorithmus binaere Suche einen Algorithmus, der binaereSuche anstatt auf einer Liste, auf einem Baum durchführt.

(b) Erstelle von Hand den Binaerbaum zur Liste [1,3,5,7,11] in Python.

(c) Überlege dir anhand deines Algorithmus noch einmal, wieviele überflüssige Elemente Du absuchen und wieviele Vergleiche Du durchführen musst.

(d) Teste deine Hypothese