Sortierbaum und Suchfunktion

[Bratte]

Ich habe von meinem Lehrer eine Schöne Hausaufgabe bekommen die ich nicht gelöst bekomme, weil ich grade einfach nen Durchhänger habe, da dachte ich mir, dass her vielleicht jemand weiß, wie das zu gehen hat:
Gegeben ist das Programm sortierbaum.py

Code: Alles auswählen

def einfuegen(baum, name):
    if baum.empty():
        return baum.new(name, Tree(), Tree())
    else:
        wurzel = baum.root()
        if wurzel < name:
            return baum.new(wurzel, baum.left(), einfuegen(baum.right(),name))
        else:
            return baum.new(wurzel, einfuegen(baum.left(),name), baum.right())

def zeige(baum,ein):
    if not baum.empty():
        wurzel = baum.root()
        zeige(baum.right(),ein+1)
        print ein*"  "+wurzel
        zeige(baum.left(),ein+1)

def suche(baum):
    if not baum.empty():
        zu_suchen=""
        

baum=Tree()
liste=["Hans","Berta","Klaus","Anton","Christa","Peter"]
for name in liste:
    baum=einfuegen(baum,name)
print ".............................."
print "Hier ist der Sortierbaum:"
zeige(baum,0)

es soll eine funktion namens "suche" bekommen. Diese soll schauen ob ein bestimmter name im sortierbaum vorkommt oder nicht. wenn er vorhanden ist soll ne eins wiedergegeben werden ansonsten eine null (das kann ich grade noch, das is der return-befehl)
aber wie sieht der rest der funktion aus
ich bite um hilfe!

Edit (BlackJack): Code in Python-Tags gesetzt.

[modelnine]

Hausaufgaben werden hier prinzipiell nicht gemacht, siehe einen entsprechenden Thread im OT-Forum.

Kleiner Hinweis: Du mußt den Baum traversieren. Da ein Binärer Baum (wie der Code den Du leider völlig ohne Einrückung gepostet hast) immer ein kleineres Element als das aktuelle auf der linken, und ein größeres auf der Rechten hat, ist es auch nicht schwer den Baum entsprechend zu traversieren, indem Du eben rekursiv nach links gehst wenn Dein Suchbegriff kleiner als der aktuelle Knoten, und nach rechts gehst wenn er größer ist, und wenn er gleich ist, hast Du den gesuchten Wert gefunden. Wenn Du probierst eine Kante zu gehen die nicht existiert, weißt Du dass der Wert nicht existiert.

Soviel zum Algorithmus, und wenn Du Dich auch nur ein bissel mit Python beschäftigst dürfte es nicht zu schwer sein den Algorithmus mit der Baum-Klasse die Ihr ja schon habt zu implementieren...

Unabhängig davon: Eure Baumklasse ist enorm primitiv, weil Ihr im Endeffekt den Baum nicht reorganisiert wenn er sehr einseitig gewichtet wird... Das bedeutet, dass Euer Baum im schlechtesten Fall O(n) wird für das traviersieren, wobei man eben einen Baum eigentlich benutzt damit man O(log2n) für das traversieren braucht. Das hat man aber eben nur wenn der Baum balanciert ist/bleibt bei Einfügeoperationen.

[Bratte]

Sry eigentlich dachte ich dass ich eingerückt habe mit leerzeichen geht das wohl nicht
na ja kann man nichts machen trotzdem danke!

[modelnine]

Benutze

Code: Alles auswählen

 und 

um den Code-Teil als Python-Code kenntlich zu machen. Dann sieht man auch die Einrückung.

Leerzeichen entfernt

[Bratte]

Ich bekomms nicht hin. Egal danke vielleicht schaff ich es ja morgen

[Grinsekatze]

hm..komisch aber ich muss genau das gleiche machen wie du in Info..dein Info-Lehrer heißt nicht zufällig Bersch

ae: also ich hab übrigens auch aufgegeben...bei meiner funktion meckert der immer über nen invalid syntax rum
ich weiß auch nicht wie es besser sein sollte..also das prinzip mit dem algorithmus und so verstehe ich ja, aber ich kenn mich mit dme prgramm nicht besonders gut aus. hier ist mein versuch, vllr. kann mir ja jemand einen tip geben, wo genau der jetzt schwierigkeiten hat:

Code: Alles auswählen

def enthalten(baum,text):
    text= rawinput("Geben Sie den Namen ein, den Sie suchen: ")
    if not baum.root() == text
    and if not baum.left() == text 
    and if not baum.right() == text:
        return 0
    else:
        return 1

[Rebecca]

Deine if-and-Abfrage ist falsch. Sinnloses, aber richtiges Beispiel:

Code: Alles auswählen

if 1==1 and 2==2:
    print "hallo"

Uebrigens waere es nicht schlecht, die gesamte Fehlermeldung mitzuposten.

EDIT: Oder mit not:

Code: Alles auswählen

if not 1==2 and not 3==4:
    print "bla"

[BlackJack]

hm..komisch aber ich muss genau das gleiche machen wie du in Info..dein Info-Lehrer heißt nicht zufällig Bersch

Binärbäume sind bei allen Inf-Lehrern und auch bei Profs fürs Informatik-Grundstudium sehr beliebt. Scheint 'ne Epedemie zu sein.

Und mir scheint da hat jemand die Algorithmen von einer funktionalen Programmiersprache einfach 1:1 nach Python umgesetzt. Beim Einfügen immer jeden Knoten an dem man vorbeikommt neu zu erzeugen ist eigentlich was für Programmiersprachen ohne (Seiten)Effekte.

ae: also ich hab übrigens auch aufgegeben...bei meiner funktion meckert der immer über nen invalid syntax rum
ich weiß auch nicht wie es besser sein sollte..also das prinzip mit dem algorithmus und so verstehe ich ja, aber ich kenn mich mit dme prgramm nicht besonders gut aus. hier ist mein versuch, vllr. kann mir ja jemand einen tip geben, wo genau der jetzt schwierigkeiten hat:

Code: Alles auswählen

def enthalten(baum,text):
    text= rawinput("Geben Sie den Namen ein, den Sie suchen: ")
    if not baum.root() == text
    and if not baum.left() == text 
    and if not baum.right() == text:
        return 0
    else:
        return 1

Du hast dort mehrere ``if`` in der einen Abfrage, die sind syntaktisch falsch. Ausserdem darf das nicht über eine "logische" Zeile hinausgehen, Du benutzt aber drei Zeilen. Das kannst Du mit Klammern um die Bedingung lösen, weil eine "logische" Zeile erst zu ende ist, wenn jede geöffnete Klammer (, {, und [ auch wieder entsprechend geschlossen wurde.

Als Rückgabewerte solltest Du besser `False` und `True` statt ``0`` und ``1`` benutzen, das bringt die Absicht der Funktion deutlicher zum Ausdruck. Da die Bedingung selbst schon zu einen Wahrheitswert, also `True` oder `False` ausgewertet wird, kannst Du das ``if/else`` komplett weglassen:

Code: Alles auswählen

def enthalten(baum, text):
    return baum.root() == text or baum.left() == text or baum.right() == text

Noch etwas kürzer wäre:

Code: Alles auswählen

def enthalten(baum, text):
    return text in (baum.root(), baum.left(), baum.right())

Wobei natürlich keine der Funktionen Dein Problem löst. Ausser wenn es nur Bäume der Höhe 1 gibt. Das wäre aber eine ziemlich massive Einschränkung.

[modelnine]

Scheint 'ne Epedemie zu sein.

Kanns auch einfach daran liegen dass sie ungeheuer sinnvoll und brauchbar sind?

Ganz davon abgesehen: ihr habt ja schon ein paar Ansätze gezeigt. Ich hab in meinem ursprünglichen Post geschrieben wie man an das ganze rangehen muß, nämlich je nachdem wie ein Binärbaum aufgebaut ist muß man einfach nach links oder nach rechts weiter rekursiv (oder auch iterativ mit einem externen Stack) suchen. Sprich: nicht nur den Knoten an der Wurzel fragen ob er dem Text entspricht, sondern den String damit vergleichen, und dann je nachdem ob er größer oder kleiner ist nach rechts oder links gehen und mit dem Knoten an der Position weitermachen.

Das ganze ist nicht schwer umzusetzen...

Wenn Ihr bis morgen mittag keine vernünftige Lösung beisammen habt poste ich eine kurze Baumklasse die das ganze demonstriert (die Ihr dann aber logischerweise noch an Euren besonderen Anwendungsfall anpassen müsst, da Ihr ja den Baum nicht als Objekt, sondern nur als Datenstruktur verwendet...)

[modelnine]

Ich hab gerade noch ein bissel im Netz gestöbert, und folgende Seite (im besonderen zu AVL-Bäumen) gefunden:

http://www.tilman.de/uni/ws03/alp/baeume.php

Guckt Euch das Applet zu AVL-Bäumen an, das ist auf jeden Fall extrem empfehlenswert zum Verständnis der Theorie hinter dieser Art von Baum...

[modelnine]

Code: Alles auswählen

# -*- coding: iso-8859-15 -*-

class Node(object):

    def __init__(self,val):
        self._val = val
        self._left = None
        self._right = None

    def add(self,val):
        if val > self._val:
            if self._right is None:
                self._right = Node(val)
            else:
                self._right.add(val)
        elif val < self._val:
            if self._left is None:
                self._left = Node(val)
            else:
                self._left.add(val)

    def search(self,val):
        if val > self._val:
            if self._right is None:
                return False
            else:
                return self._right.search(val)
        elif val < self._val:
            if self._left is None:
                return False
            else:
                return self._left.search(val)
        else:
            return True

    def show(self,depth=0):
        print "%s|-%r" % ("| "*(depth),self._val)
        if self._left is None and self._right is not None:
            print "%s|-[left is empty]" % ("| "*(depth+1),)
        elif self._left is not None:
            self._left.show(depth+1)
        if self._right is None and self._left is not None:
            print "%s|-[right is empty]" % ("| "*(depth+1),)
        elif self._right is not None:
            self._right.show(depth+1)
        if self._right is not None or self._left is not None:
            print "| "*(depth+1)

root = Node("hello")
for val in ("test","irgendeinstring","abba","blubb","welcome",
            "hastenichgesehen","wasistdas","ichhabefertig","hannover",
            "wunstorf","berlin","münchen","bremen","hamburg","wülfel"):
    root.add(val)
root.show()
print "'test' drin:", root.search("test")
print "'nichdrin' drin:", root.search("nichdrin")

Ich hatte ja gesagt dass ich noch mal ein Beispiel fertigmachen würde wenn Ihr bis heute mittag nix mehr hier postet, das obige Beispiel ist eine Klasse (Node) die einen Knoten eines binären Baumes repräsentiert und eben genau das macht was in einem Binären Baum passiert: add, search und show. Das ganze ist rekursiv implementiert der Einfachheit halber, müßte man aber nicht...

Hoffe das hilft!