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

Question

我有一个树数据类型:

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

...我需要使它成为 Show 的实例, 不使用 deriving .我发现很好地展示一个带有两片叶子的小 Twig 很容易:

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
-}