2

所以本质上我想从一个节点开始，它必须大于左子树但小于右子树......等等。在我的工作表上，它说将其分成两个功能以使其更容易。使用“也许是”。（它无法将类型“也许 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 中显示详尽的模式。is_valid_binary_search_tree 也不会比较子树的右子树是否小于主节点。（这真的是我的大问题）

4

2 回答 2

5

您所描述的解决方案的问题在于，仅检查当前树元素是否大于左侧，分别小于右侧子元素是不够的。例如，以下不是有效的二叉树：

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
于 2012-05-12T04:07:54.880 回答
0

我以彼得的回答为基础提供了一个可行的解决方案

inOrder :: Tree a -> [a]
inOrder Nil = []
inOrder (Node y l r) = inOrder l ++ [y] ++ inOrder r

isAscending :: [Int] -> Bool
isAscending [x] = True
isAscending (x:xs) = x <= head (xs) && isAscending xs

is_valid_binary_search_tree :: Tree Int -> Bool
is_valid_binary_search_tree = isAscending . inOrder
于 2017-05-12T11:54:08.710 回答