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 -> -- ...