建立树中所有分支的列表

Question

我需要使函数以这种形式从树中返回所有可能的分支：

data Tree a = EmptyT | NodeT a ( Tree a ) ( Tree a ) deriving (Show)

everyBranch :: Tree a -> [[a]]

我不确定如何解决这个问题……xD我还是Haskell的新手。

假设我有：

            1
           / \
          2   3
         /\  / \
        4  5 7  8

我想得到： [[1,2,4], [1,2,5], [1,3,8], [1,3,7]]

Answer 1

我们将使用递归方法。让我们从一个粗略的骨架开始：

everyBranch :: Tree a -> [[a]]
everyBranch EmptyT = _something
everyBranch (NodeT v (Tree l) (Tree r)) = _somethingElse

现在，我们将填补漏洞。（此语法称为“类型化的孔”：如果您通过GHC运行上述程序，则会向您显示一条错误消息，其中应包含该孔中的值的类型。）现在，我不确定第一种情况：根据您的需要，它可能是[]（无分支）或[[]]（无元素的一个分支），所以我们稍后再讲。对于第二种情况，我们需要一种方法来构造给定value以及left和right子树的分支列表。我们该怎么做？我们将递归地找到left树中的每个分支，以及right树中的每个分支，然后我们将v两者都放在前面：

everyBranch :: Tree a -> [[a]]
everyBranch EmptyT = _something
everyBranch (NodeT v l r) = map (v:) $ everyBranch l ++ everyBranch r

现在，让我们回到EmptyT。考虑一棵非常简单的树：NodeT 1 EmptyT EmptyT。在这种情况下，everyBranch应返回[[1]]。让我们everyBranch在这棵树上手动调用：

（我的??意思是“递归评估子表达式”，=>意思是“表达式评估为”）

everyBranch (NodeT 1 EmptyT EmptyT)
=> map (1:) $ everyBranch EmptyT ++ everyBranch EmptyT
   ?? everyBranch EmptyT
      => _something
=> map (1:) $ _something ++ _something

所以在这里，我们想map (1:) $ _something ++ _something等于[[1]]。什么_something啊 好吧，事实证明，如果_somethingis []，则map (1:) $ [] ++ []is []，这不是我们想要的。另一方面，如果_something为[[]]，map (1:) $ [[]] ++ [[]]则为[[1], [1]]-也不是我们想要的。看来我们需要稍微不同的方法。我们要做的是，我们将专门为此类树添加另一种情况：

everyBranch :: Tree a -> [[a]]
everyBranch EmptyT = _something
everyBranch (NodeT v EmptyT EmptyT) = [[v]]
everyBranch (NodeT v l r) = map (v:) $ everyBranch l ++ everyBranch r

现在，如果我们对此进行一点测试（尽管使用了一些随机值_something来阻止它给我们带来错误），我们会发现它适用于所有二叉树。如上所述，我们仍然需要弄清楚该_something值。该值仅在两种情况下起作用：空树（在这种情况下将微不足道地匹配EmptyT）和仅具有一个子树的树（在这种情况下，将匹配l或r将匹配EmptyT）。我将把它作为练习，让您确定放置在其中的值，它将如何影响结果以及为什么会以这种方式影响结果。