在 haskell 中绘制二叉树结构

Question

我正在 Haskell 工作并试图绘制一个树数据结构，它使用 'nodes' 有一个或两个 children 树和 'tips' 是空的树.

绘制过程取最高层节点向上绘制一条直线，长度等于节点本身的值

提示没有画线。

从这条初始线开始，节点的 children 与 parent 线成 'd' 角度绘制。对于节点的左侧 children，线向左倾斜，对于节点的右侧 children，线向右倾斜。这些行的长度分别等于每个 child 的值。

这对树结构下的每个节点重复。

我的问题是我们使用单个光标（可以向前、向后和旋转）来绘制树木。因此绘制整棵树似乎需要某种算法来系统地绘制一棵树（例如优先在左侧绘制 children 直到到达尖端，然后向后跟踪并绘制右侧 child )

但是这种方法看起来非常复杂，因为 Haskell 无法存储变量，这些变量需要记住光标已经绘制了树的哪些部分。

有没有算法可以做到这一点？如果没有，是否有其他方法可以在二维平面上使用单个光标绘制树？

感谢您的帮助。

Answer 1

假设这是您的绘图 API:

forward :: Int -> IO ()
backward :: Int -> IO ()
rotate :: Double -> IO ()

根据您的描述，树数据类型如下所示：

data Tree
  = Bin Tree Int Tree
  | Tip

然后您可以按照您的建议递归地绘制左子树，然后再绘制右子树：（"pre-order depth-first" 遍历树）

draw :: Double -- ^ Angle
     -> Tree
     -> IO ()
draw d Tip = return () -- no lines for Tips
draw d (Bin l v r) = do
  -- draw this node's line
  forward v

  -- draw left subtree
  rotate d
  draw d l

  -- draw right subtree
  rotate (2 * (-d))
  draw d r

  -- return to starting position
  rotate d
  backward v

在 haskell 中绘制二叉树结构

Drawing a binary tree structure in haskell

tree

drawing

haskell

draw