haskell漂亮的打印二进制树没有正确显示

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"]

您可以看到我们刚刚为每个元素创建了一个String表示行,但每行都缩进了多次,因为它被包含在另一个元素中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