在Haskell中转换一棵树

Question

  data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
             deriving Show
  data RoseTree a = RoseNode a [RoseTree a]
     deriving Show
  binaryTreeToRose :: BinaryTree a -> RoseTree a
         binaryTreeToRose btree = case btree of
         Node Null a Null -> RoseNode a []
         Node left a Null -> RoseNode a [binaryTreeToRose left]
         Node Null a right -> RoseNode a [binaryTreeToRose right]
         Node left a right -> RoseNode a [binaryTreeToRose left]++[binaryTreeToRose right]

我尝试编写一个在Haskell中将二叉树转换为玫瑰树的函数。但是我不知道如何使用递归解决这个问题。

- Jayyyyyy

---

但是你已经在使用递归了。 - Willem Van Onsem

Answer 1

你已经在使用递归来解决这个问题了。确实，你调用了left和right的binaryTreeToRose。因此，你是按照自身的定义来定义binaryTreeToRose。

然而，你的函数并非完全总体有效。因为对于binaryTreeToRose Null，它会出现错误。我们可以将返回类型设为Maybe (RoseTree a)：

import Data.Maybe(catMaybes)

binaryTreeToRose :: BinaryTree a -> <b>Maybe</b> (RoseTree a)
binaryTreeToRose Null = Nothing
binaryTreeToRose (Node l a r) = Just (RoseNode a (<b>catMaybes</b> (map binaryTreeToRose [l, r])))

甚至更短:

import Data.Maybe(mapMaybe)

binaryTreeToRose :: BinaryTree a -> Maybe (RoseTree a)
binaryTreeToRose Null = Nothing
binaryTreeToRose (Node l a r) = Just (RoseNode a (<b>mapMaybe</b> binaryTreeToRose [l, r]))

- Willem Van Onsem

Answer 2

变更

           [binaryTreeToRose left]++[binaryTreeToRose right]

在你最后一行的代码中出现了一个错误，无论如何。

           (binaryTreeToRose left ++ binaryTreeToRose right)

将该函数的类型更改为

binaryTreeToRose :: BinaryTree a -> [RoseTree a]

并相应地修改其他情况（还要添加一个新条款，用于 Null 情况）。

您的 BinaryTree 可以为空（由 Null 表示），但RoseTree不能。这意味着我们不能将前者转换为后者，而是转换为它们的列表。

Haskell库将类型 [RoseTree a] 称为“ Forest”。因此，转换的结果将是一组玫瑰树的森林，其中包含一个或零个它们（代表空二叉树案例）。

拥有空树就像根本没有树一样。无论哪种方式，都没有果实。

- Will Ness

Answer 3

如果你想要玩得开心，可以使用递归方案来进行递归。在这种情况下，递归方案通过提供一层推导来提供自动递归。

例如：

data BT a = BNil | BN (BT a) a (BT a)
             deriving Show
data RT a = RN a [RT a]
             deriving Show

-- data BTF a f = BNilF | BNF f a f deriving Functor
makeBaseFunctor ''BT   --BinaryTree

-- binaryTreeToRose :: BinaryTree a -> Maybe (RoseTree a)
binaryTreeToRose :: BT a -> Maybe (RT a)
binaryTreeToRose = cata alg where
  alg BNilF = Nothing
  alg BNF l a r = Just $ RN a $ catMaybes (l ++ r)

- Zhu Jinxuan