Haskell 非二叉树

Question

对于一项学校作业，我在 Haskell 中实现了一个二叉树:

data BinTree = L | N BinTree BinTree deriving (Eq, Show)

-- this function creates the full binary tree of size 2^(n+1) -1
makeBinTree 0 = L
makeBinTree n = N (makeBinTree (n-1)) (makeBinTree (n-1))

创建一个二叉树，其中每个父节点都有两个子节点。因此，makeBinTree 3 具有以下输出:N (N (N L L) (N L L)) (N (N L L) (N L L))

根据我自己的理解，我希望制作一棵树，使每个父节点都有任意数量的子节点。我在如何继续的问题上纠结了一段时间。

所以输入是:

生成二进制树 2 3

输出将是:

N(N L L L)(N L L L)(N L L L)

任何有关如何操作的提示都将不胜感激。

Answer 1

您可以像下面的代码一样执行此操作，其中您必须以反向波兰表示法指定树，并且其中的数字是您正在创建的树的奇偶校验。

如果一棵树试图采纳的树数大于树列表中的树数，程序就会崩溃。

如果最后创建的树没有采用树列表中的所有树，程序会生成多棵树。

data Tree = Branch [Tree] deriving Show

make :: [Int] -> [Tree] -> [Tree]
make [] l2 = l2
make (i1 : l1) l2 = make l1 (Branch (take i1 l2) : drop i1 l2)

例子:

make [0, 0, 2, 0, 2] [] = [Branch [Branch [], Branch [Branch [], Branch []]]]