haskell - 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)

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

这是我的代码：

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

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

score 13 · Accepted Answer

如何思考这个问题

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

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

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

打印右子树，从我们所在的位置缩进一点，
打印当前节点，
打印左子树，从我们所在的位置缩进一点。

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

什么都不输出。

请注意，我们仍然可以继续进行总体计划，因为如果您什么都不缩进，您仍然什么也得不到

编写函数

伟大的。现在我们已经完成了排序，我们可以编写一些代码。首先让我们对缩进进行排序：

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

score 4 · Accepted Answer

我只是想提供一种替代方法，一些读者可能会觉得很有趣；我支持 user2727321 的回答，因为它更适合您的目的。

我将要演示的称为“最终编码”（与“初始编码”相反，这是您的 ADT 表示形式），之所以这样称呼，是因为它是数据类型在语义方面的编码（它的解释）而不是根据它的句法（它的构造）。假设我们没有数据类型，而是只想使用函数而不是构造函数。这意味着我们可以将逻辑直接编码到我们的“构造函数”中，而不是创建一个单独的函数来解释数据。

将一棵树表示为它自己的漂亮打印机

请注意，对数据结构的每一种解释，包括漂亮的打印在内，都会对数据赋予一些意义。在这种特殊情况下，树的含义是依赖于深度的字符串。也就是说，相同的子树可以在不同的深度渲染。例如，这是在深度 0 处渲染的树：

  3
2
  1

这是在深度 4 渲染的同一棵树：

          3
        2
          1

我们可以进一步假设，对于这种情况，深度仅用于生成空格前缀，因此我们可以说树是依赖于某个给定前缀的字符串，而这只是另一个字符串。我们可以说我们的树具有以下表示：

type BinTree a = String -> String

有趣的是，a这里实际上从未使用过 type 参数，但为了保留与您的原始问题的一些不必要的相似性，我将把它留在那里。

构造函数

现在我们可以定义我们的每一个“构造函数”。回想一下，您的原始Empty构造函数具有以下类型：

Empty :: BinTree a

因此，我们希望我们自己的empty值具有相同的类型，只是根据我们的最终编码而不是您的初始编码：

empty :: BinTree a

如果我们扩展类型同义词，我们有：

empty :: String -> String

All emptyis 是空字符串，完全忽略前缀：

empty _prefix = ""

现在我们转到内部节点。回想一下原始Node构造函数的类型：

Node :: BinTree a -> a -> BinTree a -> BinTree a

所以我们想写一个node类型大致相同的函数。但是，我们将使用show，因此Show约束将在此处显示：

node :: Show a => BinTree a -> a -> BinTree a -> BinTree a

扩展类型同义词非常麻烦，但在学习此技术时可能有助于参考：

node :: Show a =>
        (String -> String) -> a -> (String -> String) ->
        (String -> String)

为了在给定的前缀处渲染内部节点，我们首先渲染右分支，前缀稍长，然后使用我们的前缀渲染当前值，添加换行符，然后渲染左分支，前缀更长：

node l x r prefix =
  let prefix' = "  " ++ prefix
  in r prefix' ++ prefix ++ show x ++ "\n" ++ l prefix'

包起来

我们编写一个函数来方便地漂亮地打印没有前缀的树：

prettyTree :: BinTree a -> String
prettyTree tree = tree ""

有趣的是，由于我们使用的是showinnode而不是 in prettyTree，因此实际上不必在Show此处添加约束。我们只需要Show实际使用该a参数的唯一函数。

在 GHCi 中测试它：

> let 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))))
> putStr $ prettyTree treeB
      18
    17
      16
  15
        14
      13
    12
      11
10
      9
        8
    7
      6
  5
      4
    3
        2
      1

多重解释呢？

有人可能会合理地反对所有这一切，因为您并不总是只想漂亮地打印一棵树。我完全同意。幸运的是，类型类支持我们。我们所要做的就是使用类型类重载类似构造函数的函数：

class BinaryTree f where
  empty :: f a
  node  :: Show a => f a -> a -> f a -> f a

我们之前的实现只是这个类的一个实例（使用适当的新类型包装而不是类型同义词，因为这是使其成为类型类的实例所必需的）。其他解释可以有其他表示。您甚至可以使用多态性构建一次树并以多种方式解释它。

这是一个带有类型类的完整实现，使用-XConstraintKindsand-XTypeFamilies将烦人的Show约束从类型类移动到这个特定实例：

class BinaryTree f where
  type Elem f a
  empty :: Elem f a => f a
  node  :: Elem f a => f a -> a -> f a -> f a

newtype BinTree a = BinTree { prettyTree' :: String -> String }

instance BinaryTree BinTree where
  type Elem BinTree a = Show a
  empty      = BinTree $ const ""
  node l x r =
    BinTree $ \prefix ->
    let prefix' = "  " ++ prefix
    in prettyTree' r prefix' ++ prefix ++ show x ++ "\n" ++ prettyTree' l prefix'

prettyTree :: (forall f. BinaryTree f => f a) -> String
prettyTree tree = prettyTree' tree ""

我做了一件事我还没有解释过，那就是强制二叉树参数的实际类型prettyTree是多态的。这可以防止您使用prettyTree某些使用特定表示的特殊知识构建的树BinTree；它必须仅使用emptyand构建node，就像使用 ADT 一样。