Binärbaum

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Grinsekatze
User
Beiträge: 2
Registriert: Mittwoch 8. Februar 2006, 22:19

Hey Leute!
Also wir programmieren in Info gerade einen Binärbaum und ich wollte aml fragen ob mir jemand weiter helfen kann....
das Programm sieht bislang so aus:

Code: Alles auswählen

#Binaerbaum als ADT

class Tree:
    def __init__(self):
        self.element=None
        #self.l=None
        #self.r=None

    def empty(self):
        return self.element==None


    def left(self):
        if not self.empty():
            return self.l
        else:
            print "Fehler: leerer Baum"

    def right(self):
        if not self.empty():
            return self.r
        else:
            print "Fehler: leerer Baum"

    def root(self):
ich weiß nur leider nicht, womit ich die Funktion root füllen soll (mein Lehrer ist der Meinung die gehört da unbedingt rein.) PLZ help!

Edit (BlackJack): Code in Python-Tags gesetzt.
Python 47
User
Beiträge: 574
Registriert: Samstag 17. September 2005, 21:04

setz es doch bitte in python tags(oberhalb vom eingabefeld ist ein python-button)mit einrückung!Damit wird es für uns leichter! :wink:
mfg

Thomas :-)
stephan_strecker
User
Beiträge: 18
Registriert: Samstag 5. November 2005, 17:42
Kontaktdaten:

ich weiss jetzt nicht genau wie du deinen Baum aufbauen willst. aber jeder baum hat ja einen anfang den bezeichnet man ab und zu als root und an dieses objekt werden dann die anderen objekte drangehängt.

binärbaume haben auch schon einige leute mal gebaut schau mal in die suche da gibts auch was
BlackJack

Grinsekatze hat geschrieben: ich weiß nur leider nicht, womit ich die Funktion root füllen soll (mein Lehrer ist der Meinung die gehört da unbedingt rein.)
Dann wird er doch sicher auch gesagt haben was die Methode machen soll, oder? So vom Namen her könnte man vermuten, die soll die Wurzel des Baums zurückgeben, aber das ist eher ungewöhlich für die Grundfunktionalität eines Baums und würde extra Daten benötigen. Zum Beispiel das jeder Knoten weiss, wer sein Vaterknoten ist.

Euer Lehrer hat euch doch sicher eine Spezifikation des ADT gegeben und nicht nur die Namen von Methoden!?
PILLE
User
Beiträge: 8
Registriert: Mittwoch 23. Februar 2005, 15:38
Kontaktdaten:

wir haben dieses Projekt auch gerade im Unterricht ganz nett eigendlich q Baum ich habe allerdings ein anderes Problem.. ich habe eine Methode geschrieben um festzustellen auf welcher ebene ein Knoten sitzt.. das ist eine praktische und einfache Sache dachte ich mir.. Soviel zur Vorgeschichte.. realisiert ist das allerdings noch nicht ( 6 stunden arbeite ich schon dran)

also die Methode ist wie folgt aufgebaut.. ich mache eine rekursion bis ich beim gesuchten Knoten angekommen bin... soweit so gut die rekursion funktioniert auch habe ich bin finde eines Knoten auch benutzt.. jetzt das Problem die Mittlere IF- Bedingung wird 100% ausgeführt allerdings ist das was ich zurückbekomme immer none obwohl der counter gesetzt ist.. Wenn jemand ne idee hat woran das liegen kann bitte meldet euch.

Code: Alles auswählen

def countArea(self, value, node = None, counter = None):

        if node == None and counter == None:                            # prüfen ob der Erste durchlauf ist
            node = self.__root                                          # start auf die Wurzel setzen
            counter = 0                                                 # counter initialisieren

        if node.getContent() > value:                                   # wenn der Knoten größer als der Wert ist linken Wert prüfen
            if node.getLeftValue() != None:                             # wenn es einen linken Knoten gibt
                counter = self.countArea(value, node.getLeftNode(), counter+1)    # weiter im Baum nach links
            else:
                raise OwnError("ERROR_NOT_IN: Wert ist nicht im Baum")  # abbruch durch Fehler

        if node.getContent() == value:                                  # Werte sind gleich
            print "content" , value
            print "node", node.getContent()
            print "vor return", counter
            return counter

        if node.getContent() < value:                                   # wenn der Knoten kleiner als der Wert ist rechten Knoten prüfen
            if node.getRightValue() != None:                            # wenn es einen rechten Knoten gibt
                counter = self.countArea(value, node.getRightNode(), counter+1)   # weiter nach rechts gehen
            else:                                                       # wenn es keinen rechten Wert mehr gibt ist der Knoten nicht im Baum
                raise OwnError("ERROR_NOT_IN: Wert ist nicht im Baum")  # abbruch durch Fehler

Na also das war jetzt die Methode.. soo dann noch eine anmerkung wenn ich das return ohne IF_Bedingung mache dann bekomme ich eine 1 zurück.. ist erstmal an der stelle egal was denke ich.. dasDing ist nur das er die Ausgabe auch anständig ausspuckt und damit bewisen ist das er in die Besagt If-bedingung geht..
Es wäre schön wenn mir jemand helfen kann und es muss sich auch nicht Zwingend um In-Order traversierung handeln..

viel Dank schon mal

Pille
Theorie und Praxis sind in der Theorie das selbe, doch unterscheiden sie sich meist in der Praxis meilenweit
PILLE
User
Beiträge: 8
Registriert: Mittwoch 23. Februar 2005, 15:38
Kontaktdaten:

Ach so ja antworten wollte ich dir ja auch noch...

also ich habe eine methode getRoot() in der Knotenklasse die zurückgibt welcher wert der Root hat.

dann habe ich es allerdings im Baum etwas anderes gelöst und gesgat das es eine Klassenvarriable gibt.. diese Variable setht immer auf der Aktuellen Wurzel.. das ist aber eigendlich egal ob du jedes mal die Methode aufrufst und dann die aktuelle wurzel hast oder ob du sie dir merkst.. Mir fällte gerade auf das das mit der methode recht praktisch ist.. *grübel* na ja Unser lehrer meinet auch so einiges.. aber eigendlich hat er auch keine Ahnung :) aber darum geht es nicht..

Pille
Theorie und Praxis sind in der Theorie das selbe, doch unterscheiden sie sich meist in der Praxis meilenweit
PILLE
User
Beiträge: 8
Registriert: Mittwoch 23. Februar 2005, 15:38
Kontaktdaten:

soo ich ahbe mein problem gelößt es war was wegen der rekursion.. na ja viel spaß noch beim programmieren
Theorie und Praxis sind in der Theorie das selbe, doch unterscheiden sie sich meist in der Praxis meilenweit
BlackJack

PILLE hat geschrieben:also ich habe eine methode getRoot() in der Knotenklasse die zurückgibt welcher wert der Root hat.

dann habe ich es allerdings im Baum etwas anderes gelöst und gesgat das es eine Klassenvarriable gibt.. diese Variable setht immer auf der Aktuellen Wurzel..
Aber dann kann man ja im ganzen Programm nur *einen* Baum benutzen wenn die Wurzel in einer Klassenvariablen gespeichert ist. Das ist eher unschön.
Antworten