确定二叉树是否是BST haskell(Determine if binary tree is BST haskell)

确定二叉树是否是BST haskell(Determine if binary tree is BST haskell)

我试图编写一个bool函数来返回True，如果二叉树是一个使用递归的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

但是这个代码导致错误：

无法与实际类型'Int'匹配的预期类型'Bool'

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

I'm trying to write a bool function to return True if a binary tree is a bst using recursion, and I need a little guidance on haskell syntax.

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. I was structuring my function as such:

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

But this code results in the error:

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

Referring to the < h and > h parts specifically. Is it something wrong with my haskell formatting? Thanks in advance

最满意答案

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

另一件事，你也可以使用你在上一个问题中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 -> Int ，因为你可能知道如何做到这一点。

Martin, I'd recommend you to look at Willem's answer.

Another thing, you could also use your maxInt function that you asked in a previous question to define this function:

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

Taking your definition of BSTs:

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.

I'll add that also the subtrees of a node should be BSTs as well.

So we can define this requirement with:

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

Recall that you might need to define minInt :: Tree -> Int, as you probably know how to do that.