haskell - 如何在 Haskell 中找到二叉树的所有可能子树？

Question

我需要在二叉树中找到所有可能的子树:

allSubtrees :: BinaryT a -> [BinaryT a]
allSubtrees = undefined

这棵树是:

data BinaryT a =
    Empty
  | Node (BinaryT a) a (BinaryT a)
  deriving (Eq, Show)

我是 Haskell 的新手，我知道没有 while ⁄ for在 Haskell 中循环。 Haskell 是关于递归的。我的问题是，如何在没有无限递归的情况下获得树的所有可能子树？

Answer 1

bheklilr 给了您对问题的一种解释的答案，但这是我作为初学者要告诉您的，他们将从自己解决问题中受益:

首先确保你已经清楚地定义了你想要你的函数做什么。我假设您希望它像 tails 一样工作.

然后声明式地思考，您的 = 在哪里-sign 表示"is"，写两个语句。第一个应该是“allSubtrees 树的Empty 是......”(这是你的基本情况):

allSubtrees Empty = ...

然后你的递归案例，阅读“ allSubtrees 的 Node 是......”:

allSubtrees (Node l a r) = ...something combining the subTrees of l and the subtrees of r

如果您无法解决这个问题，请尝试编写一个适用于 Node Empty 1 Empty 的递归函数。 ，然后概括它。