找出树中从根开始的偶数路径

Question

我正在尝试获取一个函数来计算从根到节点数为偶数的叶的所有路径（计算根和叶）我的树看起来像这样：

data Tree = Leaf Int | Node Int Tree Tree

到目前为止我得到的只是一个计算树中所有节点的函数，这很简单：

countNodes (Leaf _) = 1
countNodes (Node _ x y) = 1+ countNodes x + countNodes y

现在我看到了一堆与树木有关的问题，但我觉得没有答案对我有太大帮助，所以我只想问自己。当到达一片叶子时，如何使函数的一部分停止？我知道这与我使用递归思考的问题有关。

我试图做的是从根开始列出所有路径，但我总是以一个函数结束，该函数获取树中的所有元素并以某种方式将它们放在一起。我缺少一些简单的东西，请帮忙。（或者 link 我的答案正是我想要的）

Answer 1

我认为最简单的方法是创建一个可以描述通过树的路径的数据类型：

data Path = L Path | R Path | End deriving (Eq, Show)

这种类型基本上是一个列表，但有两个前置构造函数来告诉您向左走还是向右走。这可以方便地让您按路径查找项目，或者您可以编写一个函数来为您提供树中所有路径的列表。

-- Note that this can fail: lookupNode (Leaf 1) (L End) == Nothing
lookupNode :: Tree -> Path -> Maybe Tree

allPaths :: Tree -> [Path]

如果你能写出allPaths函数，那么你就可以在它上面写出你想要的函数。首先，先列出基本情况：

allPaths (Leaf _) = [End]
allPaths (Node _ left right) = _

要填补这个洞 _，请想一想列出从 Node 开始并向下递归 left 的所有路径意味着什么。您需要在所有这些路径的开头有一个 L，因此您可以将以下内容放在那里

allPaths (Node _ left right) = (map L $ allPaths left)

同样，您需要处理 right 树：

allPaths (Node _ left right) =
    (map L $ allPaths left) ++
    (map R $ allPaths right)

所以现在：

> let tree =
    Node 1
        (Node 2           -- L _
            (Leaf 3)      -- L (L End)
            (Node 4       -- L (R _)
                (Leaf 5)  -- L (R (L End))
                (Leaf 6)  -- L (R (R End))
            )
        )
        (Leaf 7)          -- R End
> allPaths tree
[L (L End),L (R (L End)), L (R (R End)),R End]

现在，要找到上面节点数为偶数的 Leaf，首先编写一个计算路径长度的函数：

pathLength :: Path -> Int
pathLength End = 0
pathLength (L rest) = 1 + pathlength rest
pathLength (R rest) = 1 + pathLength rest

evenNodeCountPaths :: Tree -> [Path]
evenNodeCountPaths tree = filter (even . pathLength) $ allPaths tree

注意：使用

可以做到这一点

data Dir = L | R | End
type Path = [Dir]

但这可能会导致无效路径，例如 [End, End, L, R, End]，这没有任何意义。出于这个原因，我选择了类似列表的 data Path。您必须编写自己的 pathLength 函数，但这种公式使得不可能有无效路径。

Answer 2

可能更容易计算偶数和奇数路径的数量。

evenAndOdd (Leaf _) = (0, 1)
evenAndOdd (Node _ l r) = let
    (el, ol) = evenAndOdd l
    (er, or) = evenAndOdd r
    in (ol+or, el+er)

如果确实需要，您可以根据此定义一个函数来计算偶数路径。

evenOnly = fst . evenAndOdd

找出树中从根开始的偶数路径

Finding out number of even paths from root in a tree

binary-tree

haskell