很好地在Haskell中打印/显示二叉树

Question

我有一个树数据类型:

data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a

......我需要将它作为一个实例Show而不使用deriving.我发现很好地显示一个带有两个叶子的小分支很容易:

instance (Show a, Show b) => Show (Tree a b) where
   show (Leaf x) = show x
   show (Branch val l r) = " " ++ show val ++ "\n" ++ show l ++ "  " ++ show r

但是如何将一个漂亮的结构扩展到任意大小的树？似乎确定间距需要我知道底部有多少叶子(或者总共有多少叶子),以便我可以分配我需要的所有空间并且只需要工作. " 我可能需要调用一个大小函数.我可以看到这是可行的,但这是否使它变得更难？

Answer 1

您可以drawTree在基本Data.Tree模块中学习该功能.只是无耻地导入它会给你这样的东西:

import Data.Tree hiding (Tree )
data Tree a b = Branch b (Tree a b) (Tree a b) 
              | Leaf a deriving (Eq,Ord,Show)

toDataTree (Leaf a) = Node a []
toDataTree (Branch b cs ds) = Node b [toDataTree cs, toDataTree ds]

d = Branch "1" (Branch "11" (Leaf "111") (Leaf "112")) 
               (Branch "12" (Leaf "121") (Leaf "122"))

e = toDataTree d
f = putStrLn $ drawTree e

{-
*Main> f
1
|
+- 11
|  |
|  +- 111
|  |
|  `- 112
|
`- 12
   |
   +- 121
   |
   `- 122
-}

Answer 2

使用applicative的Data.Tree源链接我想出了这个.我想写自己的,所以我可以了解更多.drawTree源中的方法被推广为与具有多个子节点的节点一起工作; 我的只是二叉树.

注意:我的树定义与OP略有不同.我不太明白a类型参数的用途,但方法应该仍然相同

data Tree a
    = Branch (Tree a) a (Tree a)
    | Leaf

prettyprint (Leaf)
    = "Empty root."
-- unlines concats a list with newlines
prettyprint (Branch left node right) = unlines (prettyprint_helper (Branch left node right n h))

prettyprint_helper (Branch left node right)
    = (show node) : (prettyprint_subtree left right)
        where
            prettyprint_subtree left right =
                ((pad "+- " "|  ") (prettyprint_helper right))
                    ++ ((pad "`- " "   ") (prettyprint_helper left))
            pad first rest = zipWith (++) (first : repeat rest)
prettyprint_helper (Leaf)
    = []

这产生了一棵树

4
+- 8
|  +- 9
|  |  +- 10
|  `- 6
|     +- 7
|     `- 5
`- 2
   +- 3
   `- 1

我只是想解释一下这个pad函数是如何工作的,因为那是我最难遵循的(shift在源代码中调用).

首先,zipWith应用函数(第一个参数)来"加入"两个列表.zipWith (+) [1, 2, 3] [4, 5, 6]回来[5, 7, 9].当其中一个列表为空时它会停止.zipWith只应用于一个列表返回一个可以应用于压缩第二个列表的函数(我相信这被称为函数currying).这是一个更简单的pad函数版本:

> let pad = zipWith (++) (repeat "   ")
> :type pad
pad :: [[Char]] -> [[Char]]
> pad ["1", "2", "3"]
["   1", "   2", "   3"]

注意:1.其中一个列表是infinite(repeat " "),但是当其中一个列表为空时,它会停止.zipWith只需要一个函数和一个列表.pad然后是一个函数,它获取字符/字符串列表的列表,并返回字符/字符串列表的压缩列表.因此,您应用pad单个列表将其压缩到第一个列表

现在让我们来看看

prettyprint_subtree left right =
    ((pad "+- " "|  ") (prettyprint_helper left))
        ++ ((pad "`- " "   ") (prettyprint_helper right))

(pad "+- " "| ")创建一个无限的列表,如["+- ", "| ", "| ", "| ", ...].(prettyprint_helper right)从右侧的根节点开始构建表示右侧子树的行列表.但整棵树需要向右移动; 我们通过用填充物压缩它来做到这一点.我们使用无限列表,因为我们不知道子树有多大; 总是有足够的"| "s来填充多余的线(这也是因为懒惰的评估而起作用).注意第一行; 即,子树根节点用"+- "相反的方式填充右边节点的"符号".

左侧实际上是相同的.左节点的表示法是"`- ".唯一的区别是填充; " "而不是"| ".那么为什么左边的节点不需要"分支"呢？好吧,您可以将其视为右侧节点的后面(附加填充;左侧)到达下面的左侧节点.您需要在右侧后面的填充将左节点/子树连接到父节点.除了父树之外,树的左侧后面没有任何东西.这让我想到了最后一点; 每个子树(在prettyprint_helper函数中表示为行列表)都会获得每个父树的额外填充级别.我认为最好以一个例子来说明.

在创建上面的树时(注意,我不完全知道执行顺序,特别是对于懒惰的评估,但这只是为了帮助可视化它的工作原理):

让我们说我们递归到10.那么左边的子树和右边的子树是空的,所以prettyprint_helper (Branch Leaf 10 Leaf)返回["10"].

现在我们要做到9.它的子树是:( "9" : ([] ++ ((pad "+- " "| ") [10]))没有左侧),或者"9" : ["+- 10"],或者:

9
+- 10

现在我们要做到8.((pad "+- " "| ") (prettyprint_helper right))创建:

+- 9
|  +- 10

您可以自己跟踪,但左侧是:

6
+- 7
`- 5

哪个垫(第一个元素"`- ",休息" "):

`- 6
   +- 7
   `- 5

所以总共为8,左侧附加到右侧,我们有:

8
+- 9
|  +- 10
`- 6
   +- 7
   `- 5

如果我们向上一步,8则为树填充此子4树,再次可以在另一侧进行跟踪以验证它是否有效.你得到

+- 8
|  +- 9
|  |  +- 10
|  `- 6
|     +- 7
|     `- 5

最终结果如上.请记住,在整个过程中,树被表示为行列表.只有在最后才与它结合在一起unlines.也许我的绘图是误导性的,因为它可能看起来像是以多行字符串传递的子树.一旦你理解了这一点,这是很容易添加额外的分支("|"左,右节点之间),像Data.Tree的drawTree功能.我会让你搞清楚:)

如果这太过分,我道歉; 作为初学者,我很难从源头上理解,这对我来说是个大跳跃.我希望它可以帮助别人试图解决这个问题.