蟒海龟递归二叉树

Question

我的目标是用蟒龟绘制一棵二叉树，意思是每条线分成2条，每条分支到另外两条等，从左到右，看起来像，除了从左到右水平。这是我到目前为止所拥有的，并且它可以工作，但是如果你运行它，你很快就会意识到它在很多方面都是混乱的。

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) 

有人可以告诉我什么是错的，也许如何解决它？我可以告诉角度需要改变，但我不知道该怎么做。

Answer 1

我的解决方案试图重现原始示例节点之间的角度和关系。

但是，我的主要动机是OP的代码和当前接受的解决方案都生成大量的海龟。这是一个问题，因为海龟被保存在全球名单中，而不是垃圾收集，因此不必要地创建它们，浪费空间。在深度4处，到目前为止显示的算法会产生30只乌龟，在运行tree()之后将会是不需要的并且不可访问。下面我的解决方案可以让你在一个单一的龟传递给用于绘制整个图形：

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：

可以tree()后打电话screen.turtles()看到海龟的列表已经创建。

Answer 2

至于我可以看到：

1. 你应该叫penup()和pendown()在龟实例a和b，而不是模块。这将解决goto上的可见行。

2. 如果您在每个深度级别上固定长度和角度，则在第二级上，您将开始叠加节点。级别n上两个节点之间的垂直距离应该大于级别n + 1上的距离，以确保在较低级别上没有重叠节点（或边缘）。请注意，级别n + 1上两个节点的垂直距离为2*forward(n)*sin(angle(n))。

喜欢的东西

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 

应该工作。