Python Turtle 递归二叉树

Question

我的目标是用 python 海龟画一棵二叉树，每条线分支成 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

据我所知：

您应该在海龟实例 a 和 b 上调用 penup() 和 pendown()，而不是在模块上。这将解决 goto.
如果您在每个深度级别上固定长度和角度，则在第二级别上您将开始具有叠加节点。级别 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

应该可以。

Answer 2

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

但是，我的主要动机是 OP 的代码和当前接受的解决方案都会生成大量海龟。这是一个问题，因为海龟是在全局列表中维护的，而不是垃圾收集的，因此不必要地创建它们会浪费 space。在深度 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()

输出：

你可以在tree()之后调用screen.turtles()来查看已经创建的海龟列表。

Answer 3

一个很好的解决方法是将高度范围作为参数传递给递归函数

进程：

绘制正在访问的节点（高度边界的中途）
计算新的界限；当前节点的高度将成为下子树的上界，上子树的下界
在当前节点的子节点上使用新边界调用方法

示例（括号是边界，每个节点 –O- 映射到实际的递归调用）：

[             O            ]
[      O     ][      O     ]
[  O  ][  O  ][  O  ][  O  ]

这是我的解决方案中的一段代码（在我的 GitHub 存储库中找到整个程序：BinaryTreeVisualization）。

def draw_tree(bst, node_radius, root, bound_bottom, bound_top, x_pos, x_step):

    if (root is not None):

        # Drawing current subtree root
        root_y = (bound_bottom + bound_top) // 2
        draw_node(x_pos, root_y, node_radius)

        # Drawing bottom subtree (bottom: same, top: root_y)
        draw_tree(bst, node_radius, root.left, bound_bottom, root_y, x_pos + x_step, x_step)
        # Drawing top subtree (bottom: root_y, top: same)
        draw_tree(bst, node_radius, root.right, root_y, bound_top, x_pos + x_step, x_step)

    pass

def draw_node(x, y, radius=5):
    canvas.penup()
    canvas.goto(x, y)
    canvas.pendown()
    canvas.dot(radius * 2)
    pass

这是一棵 example image 树（使用 repo 程序）

Python Turtle 递归二叉树

Python Turtle Recursive Binary Tree

python

recursion

binary-tree

turtle-graphics