我有一个树的结构,我想按级别打印该树。
data Tree a = Nd a [Tree a] deriving Show
type Nd = String
tree = Nd "a" [Nd "b" [Nd "c" [],
Nd "g" [Nd "h" [],
Nd "i" [],
Nd "j" [],
Nd "k" []]],
Nd "d" [Nd "f" []],
Nd "e" [Nd "l" [Nd "n" [Nd "o" []]],
Nd "m" []]]
preorder (Nd x ts) = x : concatMap preorder ts
postorder (Nd x ts) = (concatMap postorder ts) ++ [x]
但是如何通过层次来实现呢?“层次树”应该打印[“a”,“bde”,“cgflm”,“hijkn”,“o”]。我认为“iterate”是适合这个目的的函数,但是我不能想出一个如何使用它的解决方案。你能帮助我吗?
5条答案
按热度按时间qvsjd97n1#
You just need to compute the levels for all of the subtrees and zip them all together after the root:
Sadly,
zipWith
doesn't do the right thing, so we can instead use:Update: there is some concern (which I agree with) that what you originally asked is a little weird as it's not a generic breadth-first tree to list convertor. What you probably really want is to concat the result of:
izj3ouym2#
I'm guessing this is homework. On the assumption that it is, then here's some ideas for how to think about the problem that might lead you to an answer:
In
preorder
, first the current item is "reported", then recurse for all this node's tails. Inpostorder
these two steps are done in reverse. In both cases, the recursion is "local", in the sense that it only need deal with one node at a time. Is this true forlevelorder
? Or to ask it another way, whenlevelorder
recurses, do the results of the recursions interact or no? If so, then, what is the "unit" of recursion, if not a singleTree
?Understanding the nature of the recursion (or iteration..?) of
levelorder
will lead you to a solution that very simple and elegant. My version is only three lines long!By the way, it might be nice to have these utility functions to make the code even clearer in some places:
Or, if you are familiar with record syntax in Haskell, you can achieve exactly this by changing your original
Tree
definition to:A full solution:
The key is realizing that
levelorder
requires recursion on a list ofTree
. At each step the elements from eachTree
is extracted, and the next step is upon the concatenation of the subtrees:This produces the elements in a single, flattened list, much like
preorder
andpostorder
do, and is the usual definition of a breadth-first traversal.If instead you really want the elements grouped by level, a single change of the
++
operator to:
will yield that version:Note: I have given type signatures for all top-level functions. This is a really good habit to get into, and will save you considerable time debugging.
ht4b089n3#
Here is another version which can be applied to
Tree a
instead ofTree [a]
.If you want to concatenate the strings at the end you may use:
zbwhf8kr4#
我的方法比我想的要笨拙一些。如果我错了,请纠正我,因为字符串是字符列表,但是您使用的是多态类型,打印出问题中指定的结果真的这么简单吗?这段代码生成了字符串列表。***Chris在他更优雅的回答中提醒我使用concat!!
zazmityj5#
您可以对空列表重复[],这样就不会遇到zipWith的问题