Python Turtle Rekursiver binärer Baum

Question

Mein Ziel ist es, mit der Python-Schildkröte einen binären Baum zu zeichnen, in dem Sinne, dass jede Linie in 2 verzweigt, und jeder dieser Zweige in zwei usw. von links nach rechts geht, sieht aus wie , außer von links nach rechts horizontal. Hier ist, was ich bis jetzt habe, und es funktioniert, aber wenn Sie es ausführen, erkennen Sie schnell, dass es in vielerlei Hinsicht vermasselt ist.

def tree(d,x1,y1): 
    #d is the depth 

    if d==0: #base case 
     return 0 

    a = t.Turtle() 
    b = t.Turtle() 

    t.penup() 

    a.goto(x1,y1) 
    b.goto(x1,y1) # move to the correct position 

    t.pendown() 

    a.left(30) 
    b.right(30) 
    a.forward(50) 
    b.forward(50) 

    ax,ay = a.pos() #get position of new turtles 
    bx,by = b.pos() 

    input() # Debug (PRESS ENTER FOR EACH LOOP) 
    tree(d-1,ax,ay) #recurse top branch 
    tree(d-1,bx,by) #recurse bottom branch 

tree(3,0,0) 

Kann mir jemand sagen, was los ist und wie kann ich es beheben? Ich kann sagen, dass sich die Winkel ändern müssen, aber ich weiß nicht, was ich tun soll.

Answer 1

Meine Lösung versucht, Winkel und Beziehungen zwischen Knoten des ursprünglichen Beispiels zu reproduzieren.

Meine primäre Motivation ist jedoch, dass der OP-Code, und derzeit akzeptierte Lösung, beide viele Schildkröten erzeugen. Dies ist ein Problem, da Schildkröten auf einer globalen Liste verwaltet werden und nicht Müll gesammelt wird, so dass unnötigerweise Platz verschwendet wird. In der Tiefe 4 würden die bisher gezeigten Algorithmen 30 Schildkröten erzeugen, die nach tree() Läufen unerwünscht und unzugänglich wären. Meine Lösung unten können Sie in einer einzigen Schildkröte Pass zum Zeichnen des gesamten Graphen verwenden:

from math import acos 
from turtle import Turtle, Screen 

DOT_DIAMETER = 20 
GENERATION_DISTANCE = 75 

def tree(turtle, d, origin): 
    # d is the depth 

    turtle.penup() 
    turtle.setposition(origin) 
    turtle.dot(DOT_DIAMETER) 

    if d == 0: # base case 
     return 

    distance = (GENERATION_DISTANCE**2 + (2**d * DOT_DIAMETER/2)**2)**0.5 
    angle = acos(GENERATION_DISTANCE/distance) 

    turtle.pendown() 
    turtle.left(angle) 
    turtle.forward(distance) 
    upper = turtle.position() 
    turtle.right(angle) 

    turtle.penup() 
    turtle.setposition(origin) 
    turtle.pendown() 
    turtle.right(angle) 
    turtle.forward(distance) 
    lower = turtle.position() 
    turtle.left(angle) 

    tree(turtle, d - 1, upper) # recurse upper branch 
    tree(turtle, d - 1, lower) # recurse lower branch 

screen = Screen() 

yertle = Turtle() 
yertle.radians() # to accommodate acos() 

tree(yertle, 3, (-150, 0)) 

screen.mainloop() 

OUTPUT:

Sie screen.turtles() nach tree() nennen können die Liste der Schildkröten zu sehen das wurde erstellt.

Answer 2

Soweit ich sehen kann:

1. Sie penup() und pendown() auf die Schildkröte Instanzen nennen sollte a und b, nicht auf dem Modul. Dies löst die sichtbaren Linien auf goto.

2. Wenn Sie Länge und Winkel auf jeder Tiefebene festlegen, werden auf der zweiten Ebene Knoten überlagert. Der vertikale Abstand zwischen zwei Knoten auf der Ebene n sollte größer als der Abstand auf der Ebene n + 1 sein, um sicher zu sein, dass Sie keine überlappenden Knoten (oder Kanten) auf niedrigeren Ebenen haben. Beachten Sie, dass der vertikale Abstand von zwei Knoten auf Ebene n + 1 2*forward(n)*sin(angle(n)) ist.

So etwas wie

def tree(d,x1,y1): 
    #d is the depth 

    if d==0: #base case 
     return 0 

    a = t.Turtle() 
    b = t.Turtle() 

    a.penup() 
    b.penup() 

    a.goto(x1,y1) 
    b.goto(x1,y1) # move to the correct position 

    a.pendown() 
    b.pendown() 

    a.left(45) 
    b.right(45) 
    a.forward(10*(2**d)) 
    b.forward(10*(2**d)) 

    ax,ay = a.pos() #get position of new turtles 
    bx,by = b.pos() 

    tree(d-1,ax,ay) #recurse top branch 
    tree(d-1,bx,by) #recurse bottom branch 

funktionieren sollte.