在Haskell中恰好打印/显示二叉树 [英] Nicely printing/showing a binary tree in Haskell

问题描述

我有一个树型数据类型：

 数据树a b =分支b（树a b）（树a b）叶a 
  

...我需要使它成为的实例Show ，而不使用派生。我发现，很好地显示一个有两个叶子的小分支很容易：

  instance（Show a，Show b）=> Show（Tree ab）
 show（Leaf x）= show x 
 show（Branch val lr）=++ show val ++\\\
++ show l ++ ++ show r 
  

但是，如何将一个漂亮的结构扩展到任意大小的树？看起来确定间距需要我知道有多少树叶会落在底部（或者可能总共有多少树叶），以便我可以将所需的所有空间分配到那里，并且只是工作起来。 '我可能需要调用一个尺寸函数。我可以看到这是可行的，但它是否比它更难？

解决方案

您可以研究 drawTree 函数在 Data.Tree 模块。只是无耻地导入它会给你这样的东西：

  import Data.Tree隐藏（树）
数据树ab =分支b（树ab）（树ab）
 | （aq，Ord，Show）
 
 toDataTree（Leaf a）= Node a [] 
 toDataTree（Branch b cs ds）= Node b [toDataTree cs，toDataTree ds] 
 
d分支1（分支11（叶子111）（叶子112））
（分支12（叶子121）（叶子122 ））
 
e = toDataTree d 
f = putStrLn $ drawTree e 
 
 { -  
 * Main> f 
 1 
 | 
 +  -  11 
 | | 
 | +  -  111 
 | | 
 | ` -  112 
 | 
` -  12 
 | 
 +  -  121 
 | 
` -  122 
  - } 
  

I have a tree data type:

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

...and I need to make it an instance of Show, without using deriving. I have found that nicely displaying a little branch with two leaves is easy:

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

But how can I extend a nice structure to a tree of arbitrary size? It seems like determining the spacing would require me to know just how many leaves will be at the very bottom (or maybe just how many leaves there are in total) so that I can allocate all the space I need there and just work 'up.' I would probably need to call a size function. I can see this being workable, but is that making it harder than it is?

解决方案

You might study the drawTree function in the base Data.Tree module. Just shamelessly importing it would give you something like this:

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

这篇关于在Haskell中恰好打印/显示二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！