验证二进制搜索树 - Haskell的初学者

Question

所以基本上我想从一个节点开始,它必须大于左子树但小于右...等等.在我的工作表上,它说它将它分成两个功能,以使其更容易.使用'也许'.(它无法匹配类型'可能是'到'a',这完全阻止了我.

这就是我所拥有的,我看到了一个类似的问题但却无法理解它.提前致谢.

is_valid_binary_search_tree :: Ord a => BSTree a -> Bool
is_valid_binary_search_tree tree = case tree of 
    Null                               -> True
    Node element t1 t2
        | element > get_element t1 -> is_valid_binary_search_tree t1
        | element < get_element t2 -> is_valid_binary_search_tree t2
        | otherwise                -> False 

get_element :: BSTree a -> Maybe a
get_element tree = case tree of
    Null               -> Nothing
    Node element t1 t2 -> Just element

如果我删除Null - > Nothing,它可以编译但是在get_element中说详尽的模式.is_valid_binary_search_tree也不比较子树的右子树是否小于主节点.(这真的是我的大问题)

Answer 1

你描述的解决方案的问题是,它是不是足够简单地检查当前树元素比左侧,分别比右子小大.例如,以下不是有效的二叉树:

Node 3 (Node 1 (Node 0 Null Null) (Node 2 Null Null)) 
       (Node 10 (Node (-1) Null Null) (Node 12 Null Null))

实际上有一个简单的解决方案:对树进行有序遍历(即将其转换为列表),然后检查列表是否为升序:

inOrder Null = [] 
inOrder (Node a t1 t2) = inOrder t1 ++ [a] ++ inOrder t2