我正在考虑将二叉树展平为列表，以进行后续处理。
我首先想到了使用(++)联接左右分支，但随后想到了在更糟的情况下需要O(n^2)的时间。
然后，我想到了使用(:)在线性时间内附加到最前面来向后构建列表。但是，然后我想如果将这个列表发送给类似fold的函数，它必须等到遍历整个树后才能开始折叠，因此不能使用list fusion。
然后我想出了following:
data Tree a = Node a (Tree a) (Tree a) | Tip
flatten :: Tree a -> [a]
flatten x = (flatten' x) []
flatten' :: Tree a -> [a] -> [a]
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l)))
flatten' Tip l = l
main =
putStrLn $ show $ flatten $
(Node 2 (Node 1 Tip Tip) (Node 4 (Node 3 Tip Tip) Tip))
这将以
O(n)时间工作吗，占用的“堆栈空间”不超过与树的最大深度成比例的比例，并且可以将其与消耗函数(即消除中间列表)融合吗？这是拉平树的“正确”方法吗？ 最佳答案
我对融合知识不多，但是我认为一般来说递归函数不能融合。但是请记住，当您在Haskell中处理列表时，中间列表通常不会一次全部存在-您将知道开始并且没有计算结束，然后稍后您将丢弃开始并知道最后(与列表中的元素一样多的步骤)。这不是融合，更像是“流良好行为”，意味着如果逐步消耗输出，空间需求会更好。
无论如何，是的，我认为这是平整树木的最佳方法。当算法的输出是一个列表，但其他情况下该列表未经检查且正在进行串联时，通常使用difference lists(DList)是最好的方法。它们将列表表示为“prepender函数”，从而消除了在追加时进行遍历的需要，因为追加只是函数组成。
type DList a = [a] -> [a]
fromList :: [a] -> DList a
fromList xs = \l -> xs ++ l
append :: DList a -> DList a -> DList a
append xs ys = xs . ys
toList :: DList a -> [a]
toList xs = xs []
这些是实施的基本要素，其他可以从中得出。
DList中的朴素展平算法为:flatten :: Tree a -> DList a
flatten (Node x left right) = flatten left `append` fromList [x] `append` flatten right
flatten Tip = fromList []
让我们做一点扩展。从第二个方程开始:
flatten Tip = fromList []
= \l -> [] ++ l
= \l -> l
flatten Tip l = l
看到这是怎么回事？现在第一个方程:
flatten (Node x left right)
= flatten left `append` fromList [x] `append` flatten right
= flatten left . fromList [x] . flatten right
= flatten left . (\l -> [x] ++ l) . flatten right
= flatten left . (x:) . flatten right
flatten (Node x) left right l
= (flatten left . (x:) . flatten right) l
= flatten left ((x:) (flatten right l))
= flatten left (x : flatten right l)
其中显示了
DList公式如何等于您的函数!flatten' :: Tree a -> [a] -> [a]
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l)))
flatten' Tip l = l
对于
DList为什么比其他方法更好(最终取决于您如何使用输出)，我没有任何证据，但是DList是有效执行此操作的规范方法，这就是您所做的。关于algorithm - Haskell:展平二叉树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10592920/