在 haskell 中使用 Diagrams 库（绘制二叉树）

Question

我正在尝试使用 Haskell 图库来绘制二叉树。

这是我的树类型：

data Tree a = Empty
            | Node { label :: a, left,right :: Tree a }

leaf :: a -> Tree a
leaf a = Node a Empty Empty

这是一棵随机树：

t0 = Node 1 (Node 2 (leaf 3) (leaf 4))   (Node 5 (leaf 6) (leaf 7))

为了在中间画一个带有字符的圆，我使用了这个简单的函数（工作正常）：

diagNode :: String -> Diag

这是我绘制二叉树的代码：

diagTree :: Show s => Tree s -> Diag
diagTree Empty = diagNode "Empty"

diagTree (Node x Empty Empty) = connectOutside "X" "L" $
                                connectOutside "X" "R" $
          nx
          ===
      (nl ||| nr) # center
  where
    nx = named "X" ( diagNode (show x) )  
    nl = named "L" (diagNode "Empty" )
    nr = named "R" (diagNode "Empty" )  

diagTree (Node x left right) = connectOutside "X" "L" $
                               connectOutside "X" "R" $
          nx
          ===
      (nl ||| nr) # center
  where
    nx = named "X" ( diagNode (show x) ) 
    nl = named "L" (diagTree left )
    nr = named "R" (diagTree right )

你可以看到我的代码只适用于最后一个"leafs"，但它没有将上面的节点与下面的节点连接起来。我认为问题是，我正在递归调用 diagTree。

我该如何解决这个问题？

Answer 1

我认为问题在于您在命名时为内部节点赋予了相同的名称，因此 connectOutside 连接了它找到的第一个名称（恰好是树中的最后一个节点）。您可以通过根据每个节点的位置给每个节点一个唯一的名称来解决这个问题：

diagTree :: Show s => Tree s -> Diagram Rasterific
diagTree = go [] where
  go nm Empty        = diagNode  "Empty" # named nm
  go nm (Node x l r) = 
    connectOutside nm nmL .
    connectOutside nm nmR $
          nx
          ===
      (nl ||| nr) # centerX
    where
      (nmL, nmR) = ('L':nm, 'R':nm)
      nx = diagNode (show x) # named nm 
      nl = go nmL l # named nmL
      nr = go nmR r # named nmR

与

data Tree a = Empty
            | Node { label :: a, left,right :: Tree a }
  deriving Show

leaf :: a -> Tree a
leaf a = Node a Empty Empty

diagNode :: String -> Diagram Rasterific
diagNode txt = text txt # fontSizeL 0.4 <> circle 1 & pad 2

我明白了

在 haskell 中使用 Diagrams 库（绘制二叉树）

Using Diagrams library in haskell (draw binary trees)

tree

recursion

binary-tree

haskell

functional-programming