将玫瑰树转换为不同的二叉树类型

Question

我完全不知道如何在Haskell中进行一些树转换。我需要从一棵玫瑰树开始，定义为：

data Rose a = Node a [Rose a] deriving (Eq, Show, Ord)

到二叉树，它被定义为：

data Btree a = Empty | Fork a (Btree a) (Btree a) deriving (Eq, Show, Ord)

在我的课上，我得到了一个类似的函数，但使用了不同的二叉树定义。对于该函数，玫瑰树的定义相同，而二叉树的定义如下：

Btree a = Leaf a | Fork (Btree a) (Btree a)

其中从玫瑰树到二叉树的函数定义如下：

toB :: Rose a -> Btree a
toB (Node x xts) = foldl Fork (Leaf x) (map toB xts)
toB (Node x []) = foldl Fork (Leaf x) []

我有答案，但我不知道如何转换它，以便它与Btree的新定义一起工作。

Answer 1

当我这样做时，我认为“左”子树是第一个子节点，而“右”子树是节点的兄弟节点。这意味着您可以像这样转换树：

     h                 h
    /|\               /
   / | \             /
  b  d  e     ==>   b->d->e
 / \   / \         /     /
a   c f   g       a->c  f->g

h仍然是根，但在第二张图中，/是左子树，->是右子树。叶子没有左子树，但可能有兄弟(右子树)。根没有右子树，但可能有子树(左子树)。内部节点两者都有。

这有帮助吗？

Answer 2

尝试编写一个从二叉树的第一个定义到第二个定义的转换函数。然后是convB。toB是你的新函数！现在，系统地创建一个新函数，通过将一个函数内联到另一个函数中，直接充当两者的融合，您将获得一个简单而优雅的解决方案。