haskell - 验证二叉搜索树 - Haskell 初学者

Question

所以基本上我想从一个节点开始，它必须大于左子树但小于右子树......等等。在我的工作表上，它说将它分成两个函数以使其更容易。使用“也许是”。 (它无法将类型 'maybe a' 与 '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 中说出 in-exhaustive patterns。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