修复二叉树有序性检查函数的编译错误及优化咨询

定义的代数数据类型 #

data Tree a = Empty | Node a (Tree a) (Tree a)
  deriving (Show, Eq)

编写的代码片段 #

fromJust :: Maybe a -> a
fromJust (Just val) = val
fromJust Nothing = error "Cannot unpack Nothing."

getTreeMinimum :: Ord a => Tree a -> Maybe a
getTreeMaximum :: Ord a => Tree a -> Maybe a

getTreeMaximum Empty = Nothing
getTreeMaximum (Node value l r) =
  if l == Empty && r == Empty then Just value else
  if l == Empty && r /= Empty then if value < fromJust (getTreeMinimum r) then (getTreeMaximum r) else
  if l /= Empty && r == Empty then if fromJust (getTreeMaximum l) < value then Just (value) else
  if l /= Empty && r /= Empty then if fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r) then (getTreeMaximum r) else Nothing

getTreeMinimum Empty = Nothing
getTreeMinimum (Node value l r) = 
  if l == Empty && r == Empty then Just value else
  if l == Empty && r /= Empty then if value < fromJust (getTreeMinimum r) then Just (value) else
  if l /= Empty && r == Empty then if fromJust (getTreeMaximum l) < value then (getTreeMinimum l)
  if l /= Empty && r /= Empty then if fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r) then (getTreeMinimum l) else Nothing

isOrderedHelper :: Ord a => Tree a -> Bool
isOrderedHelper Empty = True

isOrderedHelper (Node nodeValue leftChild Empty) = if isOrderedHelper leftChild == False then False else (fromJust (getTreeMaximum leftChild)) < nodeValue

isOrderedHelper (Node nodeValue Empty rightChild) = if isOrderedHelper rightChild == False then False else nodeValue < fromJust ((getTreeMinimum rightChild))

isOrderedHelper (Node nodeValue leftChild rightChild) =
  if isOrderedHelper leftChild == False || isOrderedHelper rightChild == False
  then False 
  else fromJust (getTreeMaximum leftChild) < nodeValue && nodeValue < fromJust (getTreeMinimum rightChild)

isOrdered :: Ord a => Tree a -> Bool
isOrdered Empty = True
isOrdered tree = isOrderedHelper tree

编译错误信息 #

error: parse error on input 'getTreeMinimum'
getTreeMinimum Empty = Nothing
^^^^^^^^^^^^^^
Failed, no modules loaded.

问题 #

1. 如何修复该编译错误？
2. 是否可以提升该函数的执行效率？

1. 修复编译错误 #

编译错误的核心原因是**getTreeMaximum和getTreeMinimum的定义中存在不完整的if表达式**：Haskell要求所有if必须配套else分支，不能省略。

具体来看：

• getTreeMaximum里第三个if分支的内层if只写了then逻辑，没有else分支，导致编译器无法识别后续的getTreeMinimum定义。
• getTreeMinimum里第三个if分支同样缺少else分支，进一步加剧语法解析失败。

修复方式是给每个不满足条件的分支补充明确的返回值（这里统一返回Nothing，表示当前树不符合有序结构，无有效最大/最小值）：

修复后的getTreeMaximum：

getTreeMaximum Empty = Nothing
getTreeMaximum (Node value l r) =
  if l == Empty && r == Empty then Just value else
  if l == Empty && r /= Empty then 
    if value < fromJust (getTreeMinimum r) then getTreeMaximum r else Nothing else
  if l /= Empty && r == Empty then 
    if fromJust (getTreeMaximum l) < value then Just value else Nothing else
  if l /= Empty && r /= Empty then 
    if fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r) then getTreeMaximum r else Nothing else
    Nothing

修复后的getTreeMinimum：

getTreeMinimum Empty = Nothing
getTreeMinimum (Node value l r) = 
  if l == Empty && r == Empty then Just value else
  if l == Empty && r /= Empty then 
    if value < fromJust (getTreeMinimum r) then Just value else Nothing else
  if l /= Empty && r == Empty then 
    if fromJust (getTreeMaximum l) < value then getTreeMinimum l else Nothing else
  if l /= Empty && r /= Empty then 
    if fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r) then getTreeMinimum l else Nothing else
    Nothing

补全所有else分支后，编译器即可正常解析代码。

2. 提升执行效率 #

当前实现的效率极低，主要问题包括：

• 重复遍历：isOrderedHelper调用getTreeMaximum/getTreeMinimum，这两个函数又会递归遍历树，导致同一节点被多次访问，时间复杂度达O(n²)。
• 崩溃风险：使用自定义的fromJust，若树无序则会抛出错误直接崩溃。

优化方案：单次遍历完成验证 #

核心思路是定义一个辅助函数，在遍历树的同时完成有序性验证，并记录子树的最小/最大值，一次遍历即可完成所有逻辑，时间复杂度降为O(n)，同时避免崩溃风险：

isOrdered :: Ord a => Tree a -> Bool
isOrdered tree = case checkOrdered tree of
  Just _ -> True
  Nothing -> False
  where
    checkOrdered :: Ord a => Tree a -> Maybe (a, a)
    -- 空树视为有序，返回Nothing区分叶子节点
    checkOrdered Empty = Nothing
    -- 叶子节点的最小/最大值都是自身值
    checkOrdered (Node val Empty Empty) = Just (val, val)
    -- 只有左子树的情况
    checkOrdered (Node val left Empty) = do
      (leftMin, leftMax) <- checkOrdered left
      if leftMax < val then Just (leftMin, val) else Nothing
    -- 只有右子树的情况
    checkOrdered (Node val Empty right) = do
      (rightMin, rightMax) <- checkOrdered right
      if val < rightMin then Just (val, rightMax) else Nothing
    -- 左右子树都存在的情况
    checkOrdered (Node val left right) = do
      (leftMin, leftMax) <- checkOrdered left
      (rightMin, rightMax) <- checkOrdered right
      if leftMax < val && val < rightMin then Just (leftMin, rightMax) else Nothing

优化优势 #

1. 单次遍历：每个节点仅被访问一次，时间复杂度从O(n²)降至O(n)。
2. 安全可靠：用Maybe的绑定操作自动处理无序分支，避免fromJust导致的崩溃。
3. 逻辑简洁：验证与最值计算合并，无需单独维护最大/最小值函数。

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