创建所有大小为 n 的布尔二叉树

Question

我正在尝试创建所有大小为 n 的二叉树，但想不出办法。

树是这样定义的

> data Tree :: * -> * where
>     Tip :: a -> Tree a
>     Bin :: Tree a -> Tree a -> Tree a  
>     deriving (Eq,Show)

一棵树的大小是它拥有的 Tips 和 Bins 的数量。

我需要创建一个函数来获取 Int n 和 returns 一个包含该大小所有树的列表。

> getTrees :: Int -> [Tree Bool]

例如 getTrees 1 我应该得到 [Tip True, Tip False] 因为这是所有可能的大小为 1 的树。

我想不出一种方法来生成所有大小为 n 的树。

Answer 1

好吧，我想有些人不喜欢我试图引导解决方案的方式，所以没有进一步到期：这里是 one:

getTrees :: Int -> [Tree Bool]
getTrees 1 = [Tip True, Tip False]
getTrees n = do
  leftSize <- [0..n-2]
  let rightSize = (n-1) - leftSize
  left <- getTrees leftSize
  right <- getTrees rightSize
  return $ Bin left right

注意：

你可以在这里看到，你会遇到偶数大小的树的问题，因为它们有时会达到 getTrees 0，这将拉 leftSize <- [0..(-2)] 并在那里以空列表结束

Answer 2

让我们先从简单的开始：一号树：

> getTrees :: Int -> [Tree Bool]
> genTrees 1 = [Tip True, Tip False]

现在，我们必须考虑更大的 Ints。那么 2 呢？事实证明，如果 Bin 和 Tip 都增加大小，则不存在任何大小为二的树。任何 Bin 都会导致额外的大小 1 + k + j，其中 k 和 j 必须是有效的树大小。可以看出，这只会产生奇数大小的树。

因此，我们可以在继续之前丢弃任何无效的 Ints：

> genTrees n | even n || n <= 0 = []
> genTrees n =

现在我们知道我们的n是奇数，而且至少是三个。因此，我们真的必须使用 Bin 作为我们其他树的根。其他树？好吧，还记得上面的公式吗？我们需要生成两棵大小为 j 和 k 的新树，使得 1 + j + k = n。幸运的是，我们有一个函数可以生成这些树，称为 genTrees。我们可以将所有内容组合在一个列表理解中：

>   [Bin l r | i <- [1,3..n-1], l <- genTrees i, r <- genTrees (n - 1 - i)]

练习

证明列表理解中使用的所有大小都是有效的，包括生成的树大小以及中间树大小。
虽然第二段提供了一些动机，但它没有提供有效树必须具有奇数大小的完整证据。证明那个说法。
现在只计算 Tip 个大小。现在有效的树尺寸是多少？
重写上面的算法以生成树，其中只有 Tip 对大小有贡献（毕竟，只有它们有有效负载）。

创建所有大小为 n 的布尔二叉树

Creating all Bool binary trees of size n

binary-tree

haskell

functional-programming

注意：

练习