判断二叉树是否为BSThaskell

Question

我正在尝试编写一个布尔函数 return 如果二叉树是使用递归的 bst 则为真，我需要一些关于 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

但此代码导致错误：

Couldn't match expected type ‘Bool’ with actual type ‘Int’

具体指< h和> h部分。我的 haskell 格式有问题吗？提前致谢

Answer 1

我喜欢 Willem Van Onsem 在他的回答中的教学方法。

我本来打算删除我的答案，但我打算 post 改成 "correction"，冒着再次出错的风险：

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 的定义，

the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.

Answer 2

Is it something wrong with my haskell formatting?

不对，这是语义错误。你写：

(isBST l) < h

所以这意味着你问Haskell判断l是二叉搜索树，是True还是False，但是你不能比较True 或 False 与 h。即使你可以（某些语言将 True 视为 1，将 False 视为 0），它仍然是不正确的，因为我们想知道所有个左子树中的节点都小于h.

所以我们需要以某种方式定义界限。一种方法是通过递归传递参数并执行检查。这样做的一个问题是，例如树的根没有边界。我们可以通过使用 Maybe Int 是一个边界来解决这个问题：如果它是 Nothing，边界就是 "inactive" 可以这么说，如果它是 Just b，那么边界就是"active" 值为 b.

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

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

所以现在我们可以制作一个"sandwich check"：

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

所以 sandwich 被赋予一个下限和一个上限（都是 Maybe as）和一个值，并检查下限和上限。

所以我们可以写一个函数isBST'：

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

我们需要考虑两种情况：Leaf x 情况，"sandwich constraint" 应该满足，Node h l r 情况，h 应该满足 "sandwich constraint" 而且 l 和 r 应该满足不同的三明治约束。对于 Leaf x 它就像：

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

对于节点情况，我们首先检查相同的约束，然后在low和h之间对左侧部分l实施三明治，在[=]之间实施三明治22=] 和 upp 右边的部分 r，所以：

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

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

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

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

Answer 3

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

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

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

采用您对 BST 的定义：

I understand that for a binary tree to be a bst, the left subtree must always contain only nodes less than the head. and the right subtree must always contain only nodes greater than the head.

我要补充一点，节点的子树也应该是 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 -> Int，因为您可能知道该怎么做。

判断二叉树是否为BSThaskell

Determine if binary tree is BST haskell

binary-tree

haskell

binary-search-tree