Haskell实现判断二叉树是否为BST的递归函数语法问题求助

嘿，我来帮你搞定这个Haskell的BST判断问题～

首先，咱们先明确你代码报错的核心原因：你的isBST函数返回的是布尔值（Bool），但你却在isBST l < h这里试图把布尔值和整数类型的根节点h做大小比较——Haskell是强类型语言，不同类型的值不能直接进行这类操作，这就触发了类型不匹配的错误。

而且，你对BST判断的逻辑理解有一点偏差：BST的规则不只是“左右子树本身是BST”，更关键的是左子树的所有节点值都必须小于根节点，右子树的所有节点值都必须大于根节点。你的代码只检查了左右子树是否是BST，却没有验证子树的节点值和当前根的大小关系，就算逻辑没报错，结果也会不正确。

那正确的做法是什么呢？我们需要一个辅助函数，跟踪当前子树允许的数值范围（最小值和最大值），递归检查每个节点是否在这个范围内，同时更新左右子树的范围。

首先，先确认你的Tree类型定义（如果没写的话，需要补上）：

data Tree = Leaf Int | Node Int Tree Tree

然后，我们来实现正确的isBST函数：

isBST :: Tree -> Bool
isBST tree = isBSTHelper tree Nothing Nothing
  where
    -- 辅助函数：接收树、允许的最小值（Maybe表示可能无下限）、允许的最大值（Maybe表示可能无上限）
    isBSTHelper :: Tree -> Maybe Int -> Maybe Int -> Bool
    -- 叶子节点的情况：检查是否在允许范围内
    isBSTHelper (Leaf val) minVal maxVal =
      case (minVal, maxVal) of
        (Nothing, Nothing) -> True  -- 没有范围限制，直接合法
        (Just m, Nothing) -> val > m  -- 只有下限，必须大于下限
        (Nothing, Just n) -> val < n  -- 只有上限，必须小于上限
        (Just m, Just n) -> val > m && val < n  -- 有上下限，必须在中间
    -- 节点的情况：先检查当前根节点是否合法，再递归检查左右子树
    isBSTHelper (Node root left right) minVal maxVal =
      -- 先验证当前根节点是否在允许的范围内
      let rootValid = case (minVal, maxVal) of
                        (Nothing, Nothing) -> True
                        (Just m, Nothing) -> root > m
                        (Nothing, Just n) -> root < n
                        (Just m, Just n) -> root > m && root < n
      in rootValid &&
         -- 左子树的上限是当前根节点，下限继承父节点的下限
         isBSTHelper left minVal (Just root) &&
         -- 右子树的下限是当前根节点，上限继承父节点的上限
         isBSTHelper right (Just root) maxVal

咱们来拆解一下这个逻辑：

• 根节点没有上下限，所以初始调用辅助函数时传入Nothing Nothing
• 处理左子树时，所有节点必须小于当前根节点，所以把上限设为当前根的值，下限保持不变
• 处理右子树时，所有节点必须大于当前根节点，所以把下限设为当前根的值，上限保持不变
• 每个节点都要先检查自己是否在规定的范围内，再递归检查子树，这样就能保证整个树符合BST的规则啦

这样修改后，不仅解决了类型不匹配的问题，还能正确判断二叉搜索树。

内容的提问来源于stack exchange，提问作者Martin