时间戳

首页 > 解决方案 > 带有辅助函数的二叉搜索树谓词

haskell - 带有辅助函数的二叉搜索树谓词

问题描述

data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
deriving Show

type BSTree a = BinaryTree a

treeBSMax :: (Ord a) => BSTree a -> a
treeBSMax   btree = case btree of
        Null -> error
        Node _ val Null -> val
        Node _ val right -> treeBSMax right

treeBSMin :: (Ord a) => BSTree a -> a
treeBSMin btree = case btree of
       Null -> error
       Node Null val _ -> val
       Node left val _ -> treeBSMax left

isBSTree :: (Ord a) => BinaryTree a -> Bool
isBSTree btree = case btree of
      Null -> False
      Node Null val Null -> True
      Node lt val rt -> val >  treeBSMin lt && val < treeBSMax rt

如何使用treeBSMin和treeBSMax作为辅助函数isBSTree来查找树是否是二叉搜索树？

标签： haskelltreebinary-treebinary-search-treepredicate

解决方案

要将它们用作辅助函数，您需要首先使用以下方法从代码中删除部分Maybe性：

treeBSMax :: (Ord a) => BSTree a -> Maybe a
treeBSMax   btree = case btree of
        Null -> Nothing
        Node _ val Null -> Just val
        Node _ val right -> treeBSMax right

treeBSMin :: (Ord a) => BSTree a -> Maybe a
treeBSMin btree = case btree of
       Null -> Nothing
       Node Null val _ -> Just val
       Node left val _ -> treeBSMin left

isBSTree :: (Ord a) => BinaryTree a -> Bool
isBSTree btree = case btree of
      Null -> True                       -- changed it!
      Node Null val Null -> True
      Node lt val rt -> isBSTree lt       -- these two lines
                        && isBSTree rt     -- were missing !!
                        && inOrder (treeBSMax lt) val (treeBSMin rt)
                 where
                 inOrder Nothing  _ Nothing   =  True
                 inOrder Nothing  v (Just y)  =  v <= y
                 inOrder (Just x) v Nothing   =  x <= v
                 inOrder (Just x) v (Just y)  =  x <= v && v <= y

这当然效率不高。（为什么留作练习）

推荐阅读