确定二叉树是否为BST haskell

Question

如果二叉树是使用递归的bst，我正在尝试编写一个bool函数来返回true，我需要一些关于haskell语法的指导。

我知道要使二叉树成为 bst，左侧子树必须始终仅包含小于头部的节点。并且右侧子树必须始终仅包含大于头部的节点。我正在这样构建我的函数：

isBST :: Tree -> Bool       --recieve Tree, return bool
isBST (Lead i) = True       --return true if its only one leaf in tree
isBST (Node h l r) = if (((isBST l) < h) && ((isBST r) > h)) then True else False   
--return true if left subtree < head AND right subtree > head

但是此代码会导致错误：

无法将预期类型“Bool”与实际类型“Int”匹配

参考




Answer 1

我喜欢威廉·范·昂塞姆在回答中的教学方法。

我本打算删除我的答案，但我打算贴一个“更正”来代替，冒着再次出错的风险:

data Tree = Empty | Node Int Tree Tree deriving show

isBST :: Tree -> Bool

isBST Empty = True
isBST (Node h l r) = f (<=h) l && f (>=h) r && isBST l && isBST r
   where
     f _ Empty = True
     f c (Node h l r) = c h && f c l && f c r

请注意，我使用的是维基百科对BST的定义，即

每个节点中的密钥必须大于或等于存储在左子树中的任何密钥，并且小于或等于存储在右子树中的任何密钥。

Answer 2

马丁，我建议你看看威廉的答案。

另外，您还可以使用您在上一个问题中提出的maxInt函数来定义此函数：

isBST (Node h l r) = ... (maxInt l) ... -- at some point we will need to use this

拿起你对BST的定义：

我知道，对于一棵要成为bst的二叉树来说，左子树必须总是只包含小于头部的节点。并且右边的子树必须总是只包含大于头部的节点。

我还要补充一点，节点的子树也应该是BST。

因此，我们可以这样定义这一要求:

isBST (Node h l r) =
  ((maxInt l) < h) -- the left subtree must contain nodes less than the head
  && ((minInt r) > h) -- the right must contain nodes greater than the head
  && (...) -- the left subtree should be a BST
  && (...) -- the right subtree should be a BST

回想一下，您可能需要定义minInt:：Tree-

Answer 3

匿名用户

我的haskell格式有问题吗？

不，这是一个语义错误。你写道:

(isBST l) < h

所以这意味着你要求Haskell确定l是二叉搜索树，这是真还是假，但你不能将真或假与h进行比较。即使可以（某些语言将 True 视为 1，将 False 视为 0），那么它仍然是不正确的，因为我们想知道左侧子树中的所有节点是否都小于 h。

所以我们需要定义边界。一种方法是通过递归传递参数并执行检查。这样做的一个问题是，例如，树的根没有边界。我们可以通过使用来解决这个问题。也许Int是一个边界：如果它是Nothing，那么边界可以说是“非活动的”，如果它是，那么它只是b，那么边界是“活动的”并且值为 。

为了让这个检查更方便，我们可以先写一个方法来检查这个：

checkBound :: (a -> a -> Bool) -> Maybe a -> a -> Bool
checkBound _ Nothing _ = True
checkBound f (Just b) x = f b x

因此，现在我们可以用以下方式进行“三明治支票”：

sandwich :: Ord a => Maybe a -> Maybe a -> a -> Bool
sandwich low upp x = checkBound (<) low x && checkBound (>) upp x

因此，给三明治一个下界和一个上界（Maybes）和一个值，并检查下界和上界。

因此，我们可以用以下代码编写函数isBST'：

isBST' :: Maybe Int -> Maybe Int -> Tree -> Bool
isBST' low upp ... = ....

我们需要考虑两种情况:< code>Leaf x情况，其中应满足“三明治约束”；以及< code>Node h l r情况，其中< code>h应满足“三明治约束”，此外< code>l和< code>r应满足不同的三明治约束。对于< code>Leaf x，它是这样的:

isBST' low upp (Leaf x) = sandwich low upp x

对于节点情况，我们首先检查相同的约束，然后对左侧部分 l 强制执行低和 h 之间的三明治，对右部分 r 强制执行 h 和 upp 之间的三明治，因此：

isBST' low upp (Node h l r) = sandwich low upp h &&
                              isBST' low jh l &&
                              isBST' jh upp r
    where jh = Just h

现在我们仍然遇到的唯一问题是使用根元素调用isBST'：这里我们使用0作为初始边界，所以：

isBST :: Tree -> Bool
isBST = isBST' Nothing Nothing

当然，还有其他方法来强制约束，比如传递和更新函数，或者通过实现isBST'函数的四个变体来检查约束的子集。