Seite 1 von 1
Binärbaum
Verfasst: Mittwoch 8. Februar 2006, 22:23
von Grinsekatze
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.
Verfasst: Mittwoch 8. Februar 2006, 22:49
von Python 47
setz es doch bitte in python tags(oberhalb vom eingabefeld ist ein python-button)mit einrückung!Damit wird es für uns leichter!
Verfasst: Mittwoch 8. Februar 2006, 23:43
von stephan_strecker
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
Re: Binärbaum
Verfasst: Mittwoch 8. Februar 2006, 23:55
von 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!?
auch ein Baum
Verfasst: Freitag 10. Februar 2006, 22:27
von PILLE
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
Antwort
Verfasst: Freitag 10. Februar 2006, 22:35
von PILLE
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
Verfasst: Samstag 11. Februar 2006, 00:12
von PILLE
soo ich ahbe mein problem gelößt es war was wegen der rekursion.. na ja viel spaß noch beim programmieren
Re: Antwort
Verfasst: Samstag 11. Februar 2006, 00:33
von 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.