打印出二叉树
问题描述:
这是我的理念为指导:打印出二叉树
data BinTree α = Empty
| Node (BinTree α) α (BinTree α)
deriving (Eq, Show)
现在我想创建一个函数:
levels :: BinTree a -> [[a]]
这应该打印出二叉树的名单,但每个级别的它自己的。例如:[[1],[2,3],[4,5,6,7]]
或
[1]
[2,3]
[4,5,6,7]
...
我所定义的roots
和childs
:
roots ts = [ a | Node _ a _ <- ts ]
childs ts = [ t | Node l _ r <- ts, t <- [l, r] ]
和横动功能,其获取子树和其节点的列表。
traverse' :: [BinTree α] -> [α]
traverse' [] = []
traverse' ts = roots ts ++ traverse' (childs ts)
levels :: BinTree α -> [α]
levels t = traverse [t]
但那不是我真正想要的。有人有一个想法。
答
这工作得很好:
f Empty = []
f (Node l v r) = case (f l, f r) of
((x:xs),(y:ys)) -> [[v],x++y] ++ (zipWith (++) xs ys)
([],[]) -> [[v]]
......
完成的模式。 (你可以用一棵完整的树来测试它,以确保它是一个好的开始)。
尝试编写'f :: BinTree a - > [[a]]',它将二叉树转换为列表列表,其中第一个列表包含根目录,第二个列表包含子目录,其次是孙子目录等等。之后你几乎完成了。 – ThreeFx
否则看看[这](http://*.com/questions/12556469/nicely-printing-showing-a-binary-tree-in-haskell?rq=1)的问题,它可能有助于设计功能。 – ThreeFx
考虑如何以左右子节点的级别表示节点的级别。你有没有被介绍过'zip'函数? – ErikR