时间戳

首页 > 解决方案 > 在 Haskell 中变换一棵树

haskell - 在 Haskell 中变换一棵树

问题描述

  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 中编写一个将二叉树转换为玫瑰树的函数。但我不知道如何用递归解决这个问题。

标签： haskellrecursiontreebinary-tree

解决方案

您已经在递归地解决这个问题。的确，你呼吁binaryTreeToRose孩子们left和right。所以你binaryTreeToRose根据自己来定义。

但是，您的功能不是全部。因为binaryTreeToRose Null它会出错。我们可以将返回类型设为 a 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]))

推荐阅读