Binär-Bäume

[toper]

Hallo zusammen,
ich habe ein Programm geschrieben, dass rekursiv einen Binärbaum erstellen soll.(x und y sind im Moment noch irrelevant)

Code: Alles auswählen

class start:
    def __init__(self):

        x = 100
        y = 100

        
        
        k = BinTree(8)
        j = BinTree(7)
        f = BinTree(5,j,k)
        e = BinTree(6)
        b = BinTree(2,e,f)
        g = BinTree(4)
        empty = BinTree()
        c = BinTree(3,empty,g)
        a = BinTree(1,b,c)

        zeichnen = Zeichnen()
        zeichnen.sortieren(a.getRoot(),x,y)


class BinTree:
    def __init__(self, v=None, left=None, right=None):
        global root
        
        if v == None and left == None and right == None:
            root = None
            
        elif left==None and right==None:
            root = Node(v,None,None)
            
        else:
            root = Node(v,left.getRoot(),right.getRoot())

    def getRoot(self):
        return root


 
class Node:
    
    def __init__(self, pvalue, pleft, pright):
        global value,left,right
        value = pvalue
        left = pleft
        right = pright

    def getValue(self):
        return value

    def getLeft(self):
        return left

    def getRight(self):
        return right



class Zeichnen:
    def __init__(self):
        None

    def sortieren(self,node,x,y):
        self.malen(node,x,y)
        self.sort(node,x,y)


    def sort(self,node,x,y):
        if node.getLeft() != None:
            self.malen(node.getLeft(),x,y)
            self.sort(node.getLeft(),x,y)

        if node.getRight() != None:
            self.malen(node.getRight(),x,y)
            self.sort(node.getRight(),x,y)


    
    def malen(self,node,x,y):
        print(node.getValue())


start()

Die eigendliche Ausgabe sollte

1
2
6
5
7
8
3
4

sein. Aber statt dessen kommen nur sehr viele 1en und am Ende den Fehler, dass es zu viele Rekursionen gab.

Der Code ist ursprünglich in Java geschrieben. Dort funktioniert er.
Ich habe nun versucht in in Python zu schreiben aber anscheinend ist irgendetwas schiefgelaufen.

Weiß jemand woran das liegen könnte?

[__deets__]

Du musst

- global loswerden.
- Python Tutorial zur Objektorientierung durcharbeiten, damit du verstehst, warum du wann self.ein_name brauchst

[toper]

Wenn ich das global entferne, kommt bei getRoot, dass er root nicht kennt.
Ich habe bereits viel recherchiert, finde aber das Problem nicht.

[__deets__]

Natuerlich kenn er root nicht. Das ist ein lokaler Name. "Viel recherchiert" kann sein. Hast du das Tutorial zur Objektorientierung durchgearbeitet?

[toper]

Noch nicht vollständig, da es sehr lang ist.
Ich habe auch noch nicht sehr viel damit gemacht. Deshalb wäre ein einfacher Fix nett.

[__deets__]

Einfache Fixes für Hausaufgaben gibt’s bei mir zumindest nicht.

Das hier ist der relevante Teil: https://docs.python.org/3/tutorial/classes.html

[toper]

Ich habe es jetz geschaft das global zu entfernen indem ich das root durch self.root ersetzt habe.
Allerdings habe ich jetzt wieder das selbe Problem wie am Anfang.

P.S.
Es sind keine Hausaufgaben sondern ein privates Projekt. Der Java Code stammt zwar aus dem Unterricht aber die Python Version mache ich auf freiwilliger Basis

[toper]

Ich habe das Problem gelöst. Hatte noch einen syntax Fehler in zeichnen.

[bords0]

Wenn du global verwendest, heißt das, dass alle deine Nodes die gleichen Werte für value, left und right haben. Du musst auch hier global entfernen und mit self.value etc. arbeiten.

Es gibt das geflügelte Wort "Python ist nicht Java". Da steckt mehr dahinter, als man meinen könnte. Man muss in Python anders programmieren als in Java, sonst wird man nicht glücklich.

Zum Beispiel verwendet man in Python keine Setter- und Getter-Methoden. Das Problem, das man in Java damit löst, löst man in Python anders (falls es denn mal - sehr selten - auftritt).

Dann sähe die Klasse Node ungefähr so aus:

Code: Alles auswählen

class Node:
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right

Man sieht auch gleich, dass Node nur ein Datenspeicher ist, ohne Funktionalität. Den kann man gleich in BinTree stecken, das dadurch sogar einfacher wird. Und auch dort kann man den Getter entfernen und landet dann etwa hier:

Code: Alles auswählen

class BinTree:
    def __init__(self, v=None, left=None, right=None):
        self.v = v
        self.left = left
        self.right = right

Außerdem muss man in Python nicht alles in eine Klasse stecken. Es gibt Funktionen, und wenn man keine Klasse braucht, sollte man die auch verwenden. Ein Hinweis darauf ist das Nichtbenutzen von self. Die Klasse Zeichnen kann man durch zwei Funktionen ersetzen:

Code: Alles auswählen

def male_baum(baum, x, y):
    male(baum, x, y)
    if baum.left is not None:
        male_baum(baum.left)
    if baum.right is not None:
        male_baum(baum.right)
        
def male(baum, x, y):
    print(baum.v)

Evtl. kann es sinnvoll sein, diese Funktionen als Methoden der BinTree-Klasse zu definieren. Das hängt davon ab, was die noch so machen sollen, würde ich sagen.

Auch den start-Code würde man in Python nicht in eine Klasse stecken, sondern in eine Funktion, die üblicherweise main heißt. Und den Aufruf durch ein if-Konstrukt schützen, das du jetzt noch nicht verstehen musst.
Insgesamt bleibt:

Code: Alles auswählen

class BinTree:
    def __init__(self, v=None, left=None, right=None):
        self.v = v
        self.left = left
        self.right = right


def male_baum(baum, x, y):
    male(baum, x, y)
    if baum.left is not None:
        male_baum(baum.left, x, y)
    if baum.right is not None:
        male_baum(baum.right, x, y)

        
def male(baum, x, y):
    print(baum.v)


def main():
    x = 100
    y = 100

    k = BinTree(8)
    j = BinTree(7)
    f = BinTree(5, j, k)
    e = BinTree(6)
    b = BinTree(2, e, f)
    g = BinTree(4)
    c = BinTree(3, None, g)
    a = BinTree(1, b, c)
    
    male_baum(a, x, y)


if __name__ == "__main__":
    main()

Ergebnis:

Code: Alles auswählen

1
2
6
5
7
8
3
4