haskell - generate all binary trees with size n

Question

I'd like to write a function which returns all possible binary trees for any given size.

Unfortunately I have no clue, why my solution always returns an empty list, except for size 1.

allTreesN :: Int -> t -> [Tree t]
allTreesN n t 
    | n == 0 = [ Leaf ]
    | otherwise = [(Node x t y) | i <- [0..n-1], x <- (allTreesN i t),y <- (allTreesN i t), size (Node x t y) == n]

标签： haskellbinary-treelist-comprehension

Answer 1

您基本上为 和 生成所有大小的树，然后旨在构建大小为 的树。这只有在. 但是现在出现了第二个问题：我们永远无法在这里生成大小树，因为不能被二除。由于我们无法生成大小为 的树，因此我们无法生成大小为 的树，依此类推。ixyni = 2 *n1112

因此，我们需要确保生成正确大小的树。我们可以通过生成一个 size 的树i和另一个size 的树来做到这一点n-i-1。如果我们构造一个这样大小的节点，我们肯定知道承载这些子树的节点的大小是 size n，所以我们甚至可以省略检查。

所以正确的实现是：

allTreesN :: Int -> a -> [Tree a]
allTreesN 0 _ = [Leaf]
allTreesN n v = [Node l v r | i <- [0..n-1],
                              l <- allTreesN i v,
                              r <- allTreesN (n-1-i) v]

例如：

Prelude> allTreesN 0 'a'
[Leaf]
Prelude> allTreesN 1 'a'
[Node Leaf 'a' Leaf]
Prelude> allTreesN 2 'a'
[Node Leaf 'a' (Node Leaf 'a' Leaf),Node (Node Leaf 'a' Leaf) 'a' Leaf]
Prelude> allTreesN 3 'a'
[Node Leaf 'a' (Node Leaf 'a' (Node Leaf 'a' Leaf)),Node Leaf 'a' (Node (Node Leaf 'a' Leaf) 'a' Leaf),Node (Node Leaf 'a' Leaf) 'a' (Node Leaf 'a' Leaf),Node (Node Leaf 'a' (Node Leaf 'a' Leaf)) 'a' Leaf,Node (Node (Node Leaf 'a' Leaf) 'a' Leaf) 'a' Leaf]