Haskell，来自树的列表列表 [英] Haskell, list of lists from a tree

问题描述

我有一个树的数据结构:

I have this data structure for a tree:

数据树 a = NodeT a (树 a) ( 树 a) |空T

data Tree a = NodeT a (Tree a) ( Tree a) | EmptyT

我需要创建一个函数，该函数返回一个列表列表，其中列表的每个元素代表树的一个级别.例如，从这里:

I need to create a function that returns a list of lists where each element of the list represents a level of the tree. For instance, from this:

          1
         / 
       2     3
      /    / 
     4   5 6   7     

到这个:[[1],[2,3],[4,5,6,7]]

to this: [[1],[2,3],[4,5,6,7]]

该函数必须具有以下形式:

The function must have the following form:

                     f :: Tree a -> [[a]]

如何使用递归来实现?

有人吗?

谢谢

推荐答案

您递归计算层级，并始终逐点合并来自两个子树的列表(因此相同深度的所有切片合并在一起).

You recursively compute the levels and always merge lists from two subtrees point-wise (thus all the slices in the same depth get merged together).

f :: Tree a -> [[a]]
f EmptyT = []
f (NodeT a t1 t2) = [a] : merge (f t1) (f t2)

merge :: [[a]] -> [[a]] -> [[a]]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = (x ++ y) : merge xs ys

如果树是完整的(从根到列表的所有路径的长度都相同)，那么您可以使用 zipWith (++) 作为 merge.

If the tree were complete (all the paths from the root to a list are of the same length) then you could use zipWith (++) as merge.

这篇关于Haskell，来自树的列表列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！