search - Haskell中二叉搜索树中的元素？

Question

如何在 Haskell 中搜索二叉搜索树中的元素？我定义了我的树：

 data Tree a = 
     Null | 
     L a | 
     N (Tree a) a (Tree a) 
     deriving Show 

我想创建一个在 BST 中搜索元素的函数：

 findElem :: Tree a -> a -> Maybe a
 findElem tree n = ...

我怎样才能做到？

Answer 1

正如评论中所建议的，您应该摆脱L构造函数并N Null x Null改用它。它将让您避免为叶节点编写不必要的特殊情况。

findElem然后应该看起来像这样：

findElem :: Ord a => Tree a -> a -> Maybe a
findElem Null _ = -- ...
findElem (N l x r) y =
    case compare x y of
        LT -> -- ...
        EQ -> -- ...
        GT -> -- ...