如何在haskell中查找二叉树中的节点级别

Question

我试图找到某个节点的级别，例如，如果二叉树是:

(Node (Node (Node) Leaf 9) Leaf 8) Leaf 7) Leaf 6)

9级为3
8级为2
7级为1
6级为0

在这方面有人能帮我吗?函数应该是这样的:

path:: Tree a ->一个→Int

Answer 1

您应该创建一个帮助函数来跟踪树的级别。因此，您创建了一个签名为:

的辅助函数path'。

path' ::Int-> Tree a -> a -> Int
path'level(Node left right x) query
| … = …
| … = …
| otherwise = …
path' _ Leaf _ = …

，其中需要填写…部分。您将需要进行递归调用来访问left和right子树，这可以通过调用path'来完成，其中您将(level+1)作为第一个参数来调用它。

如果你实现了path',path只是:

path :: Tree a -> a -> Int
path =path' 0

如果没有找到项目，则必须返回一个类似-1的值，因为树的级别总是大于或等于零。然而，正如@dfeuer所说，使用Maybe Int更习惯，并且在没有找到元素的情况下返回Nothing:

path' :: Int -> Tree a -> a ->Maybe Int
path'level(Node left right x) query
| … = …
| … = …
| otherwise = …
path' _ Leaf _ = …
path :: Tree a -> a ->Maybe Int
path = path' 0

在这种情况下，您还可以使用(<|>) :: Alternative f => f a -> f a -> f a组合递归调用的结果，从而删除path'实现中的一行:

import Control.Applicative((<|>))
path' :: Int -> Tree a -> a -> Maybe Int
path'level(Node left right x) query
| … = …
| otherwise = …<|>…
path' _ Leaf _ = …