haskell pretty-print 二叉树无法正确显示

Question

我正在尝试在 Haskell 中漂亮地打印一棵二叉树，这样如果您将头向左转，它应该看起来像一棵树。树中的每一层都应比上一层缩进 2 个空格。

这是预期的输出:

--        18
--      17
--        16
--    15
--          14
--        13
--      12
--        11
--  10
--        9
--          8
--      7
--        6
--    5
--        4
--      3
--          2
--        1

对于这棵树:

treeB = (Node (Node (Node (Node Empty 1 (Node Empty 2 Empty)) 3 (Node Empty 4 Empty)) 5 (Node (Node Empty 6 Empty) 7 (Node (Node Empty 8 Empty) 9 Empty))) 10 (Node (Node (Node Empty 11 Empty) 12 (Node Empty 13 (Node Empty 14 Empty))) 15 (Node (Node Empty 16 Empty) 17 (Node Empty 18 Empty))))

树是这样定义的:

data BinTree a =
    Empty
  | Node (BinTree a) a (BinTree a)
  deriving (Eq,Show)

但是，我的结果看起来不是那样的。这是我的结果:

      18
  17
    16
  15
        14
  13
  12
    11
10
      9  
  8
  7
    6
  5
      4
  3
      2
  1

这是我的代码:

prettyTree :: (Show a) => BinTree a -> String
prettyTree Empty = "\n"
prettyTree (Node Empty x Empty) = "  " ++ show x ++ "\n"
prettyTree (Node Empty x r) = prettyTree' r ++ "  " ++ show x ++ "\n"
prettyTree (Node l x Empty) = show x ++ "\n" ++ "  " ++ prettyTree' l
prettyTree (Node l x r) = prettyTree' r ++ show x ++ "\n" ++ prettyTree' l

prettyTree' :: (Show a) => BinTree a -> String
prettyTree' Empty = "\n"
prettyTree' (Node Empty x Empty) = "  " ++ show x ++ "\n"
prettyTree' (Node Empty x r) = "  " ++ prettyTree' r ++ "  " ++ show x ++ "\n"
prettyTree' (Node l x Empty) = "  " ++ show x ++ "  " ++ "\n" ++ prettyTree' l
prettyTree' (Node l x r) = "  " ++ prettyTree' r ++ "  " ++ show x ++ "\n" ++ "  " ++ prettyTree' l

我不明白我做错了什么。任何帮助将不胜感激。

Answer 1

如何思考这个问题

我认为你需要更递归地思考这个问题。你的数据结构

data BinTree a =
    Empty
  | Node (BinTree a) a (BinTree a)
  deriving (Eq,Show)

本质上是递归的，因为它是根据自身定义的，所以我们应该利用它。 bheklilr 关于线条的评论非常明智，但我们可以更进一步。以下是如何打印树的一般计划:

1. 打印正确的子树，从我们所在的位置缩进一点，
2. 打印当前节点，
3. 打印左子树，从我们所在的位置缩进一点。

您正在尝试通过分析是否存在 Node 或 Empty 子树的所有情况来从一层向下处理细节。不。让递归来做。下面是我们如何处理空树:

1. 什么都不输出。

请注意，我们仍然可以按照总体计划进行，因为如果您什么都不缩进，您仍然一无所获

编写函数

太棒了。现在我们已经排序了，我们可以编写一些代码。首先让我们对缩进进行排序:

indent :: [String] -> [String]
indent = map ("  "++)

因此，无论有什么字符串，都会在前面附加 ""。好的。 (请注意，它对空列表起作用，而不管它。)

layoutTree :: Show a => BinTree a -> [String]
layoutTree Empty = []  -- wow, that was easy
layoutTree (Node left here right) 
         = indent (layoutTree right) ++ [show here] ++ indent (layoutTree left)

那不是很好吗？我们只是做了左边，然后是电流，然后是右边。递归不是很好吗!

这又是您的示例树:

treeB = (Node (Node (Node (Node Empty 1 (Node Empty 2 Empty)) 3 (Node Empty 4 Empty)) 5 (Node (Node Empty 6 Empty) 7 (Node (Node Empty 8 Empty) 9 Empty))) 10 (Node (Node (Node Empty 11 Empty) 12 (Node Empty 13 (Node Empty 14 Empty))) 15 (Node (Node Empty 16 Empty) 17 (Node Empty 18 Empty))))

> layoutTree treeB
["      1","        2","    3","      4","  5","      6","    7","        8","      9","10","      11","    12","      13","        14","  15","      16","    17","      18"]

您可以看到我们刚刚为每个元素制作了一个表示行的字符串，但是每行缩进的次数与它包含在另一个 Node 中的次数一样多。

现在我们只需要实际将它们放在一起，但这并不难。请注意，之前的功能很简单，因为这一步一直留到最后。

prettyTree :: Show a => BinTree a -> String
prettyTree = unlines.layoutTree

我们只需要组合两个函数layoutTree 和unlines。 (unlines 将所有字符串与换行符连接起来。)

和成品:

> putStrLn (prettyTree treeB)
      18
    17
      16
  15
        14
      13
    12
      11
10
      9
        8
    7
      6
  5
      4
    3
        2
      1