生成所有大小为 n 的二叉树

Question

我想写一个函数，returns 任何给定大小的所有可能的二叉树。

不幸的是，我不知道为什么我的解决方案总是 returns 一个空列表，除了大小 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]

Answer 1

你基本上为x和y生成所有棵大小为i的树，然后旨在构建一棵大小为i的树n。这仅在 i = 2 *n 时有效。但是现在出现了第二个问题：我们永远不能在这里生成一棵大小为 1 的树，因为 1 不能被二除。由于我们无法生成大小为 1 的树，因此我们无法生成大小为 2 的树，依此类推。

因此，我们需要确保生成正确大小的树。我们可以通过生成一棵大小为 i 的树和另一棵大小为 n-i-1 的树来做到这一点。如果我们构造一个这样大小的节点，我们肯定知道承载这些子树的节点的大小是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 <b>(n-1-i)</b> 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]

生成所有大小为 n 的二叉树

generate all binary trees with size n

binary-tree

haskell

list-comprehension