Предикат дерева двоичного поиска с вспомогательными функциями - PullRequest
Новая
       14

Предикат дерева двоичного поиска с вспомогательными функциями

0 голосов
/ 10 октября 2019 
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, чтобы определить, является ли дерево двоичным деревом поиска?

1 Ответ

1 голос
/ 10 октября 2019

Чтобы использовать их в качестве вспомогательных функций, вам необходимо сначала удалить partiality из вашего кода с помощью 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

Конечно, это неэффективно. ( почему оставлено в качестве упражнения)

...