我的 isElement 函数（二叉树）有什么问题？

Question

我正在开发一个函数来检查元素是否是二叉树的一部分。我为我的树定义了一个名为 Tree 的类型，用于获取根元素和左右子树的函数，以及一个名为 isElement 的函数，用于检查一个值是否在我的树中。不幸的是，该函数仅适用于根元素。

以下示例说明了我从 isElement 函数中得到的错误结果：

*Main>let tree = Node 1 Empty (Node 2 Empty (Node 3 Empty Empty))
*Main> isElement  tree 2
False
*Main> isElement  tree 3
False
*Main> isElement  tree 1
True

这是我的代码：

data Tree a = Node a (Tree a) (Tree a) 
        |Empty
        deriving (Show)

nodeValue :: Tree t -> t
nodeValue (Node x _ _) = x

rightTree :: Tree t -> Tree t
rightTree (Node _ _ x) = x

leftTree :: Tree t -> Tree t
leftTree (Node _ x _) = x

isNode ::  Tree t -> Bool 
isNode (Node _ _ _) = True
isNode _ = False

isElement :: (Eq t) => Tree t -> t -> Bool
isElement tree t
    |isNode tree == False = False 
    | nodeValue(tree) == t = True
    | otherwise = (isElement (leftTree(tree)) t) || (isElement (leftTree(tree)) t)

Answer 1

您的 isElement 函数定义有误：您调用了 leftTree 两次，而不是同时调用 leftTree 和 rightTree。结果，永远不会探索右子树。相应地修改代码，

isElement tree t
    |isNode tree == False = False 
    | nodeValue(tree) == t = True
    | otherwise = (isElement (leftTree(tree)) t) || (isElement (rightTree(tree))

然后 isElement 如广告所示工作：

λ> let tree = Node 1 Empty (Node 2 Empty (Node 3 Empty Empty))
λ> isElement tree 2
True
λ> isElement tree 3
True
λ> isElement tree 1
True

不过，还有改进的余地。您实际上并不需要所有这些函数（isNode、nodeValue 等）来定义 isElement。相反，您可以通过将定义分解为两个等式来完成所有与模式匹配的拆包：一个对应于树为空的情况，另一个对应于树为节点的情况：

isElement :: (Eq a) => Tree a -> a -> Bool
isElement Empty        _ = False
isElement (Node v l r) x = v == x || isElement l x || isElement r x

编辑：正如 Luis Casillas 在中指出的那样，这个替代定义的另一个好处是它（比原始定义）更适合于编译器的穷尽性检查。

我的 isElement 函数（二叉树）有什么问题？

What's wrong with my isElement function (binary tree)?

binary-tree

haskell