haskell - 在 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 中的玫瑰树。但我不知道如何用递归解决这个问题。

Answer 1

您已经在递归地解决这个问题。确实你打电话binaryTreeToRose关于 child left和 right .所以你定义 binaryTreeToRose就其本身而言。

然而，您的功能并不全面。自为 binaryTreeToRose Null它会出错。我们可以将返回类型设为 Maybe (RoseTree a) :

import Data.Maybe(catMaybes)

binaryTreeToRose :: BinaryTree a -> Maybe (RoseTree a)
binaryTreeToRose Null = Nothing
binaryTreeToRose (Node l a r) = Just (RoseNode a (catMaybes (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 (mapMaybe binaryTreeToRose [l, r]))