BSTplus.hs

BSTplus.hs

module BSTplus ( module BST, insert, numNodes, sameShape,
    numLeaves, minValue, maxValue, height, occurs, mirror, treeSort) where

import BST

--------------------------------------------------------------------------------
-- I N T E R F A C E  :  P U B L I C  :  all exports of module 'BST', plus :
--------------------------------------------------------------------------------

-- insert v bst : the BST formed by inserting value 'v' into BST 'bst'

insert :: Ord a => a -> BST a -> BST a

--------------------------------------------------------------------------------

-- numNodes bst : the number of nodes in BST 'bst'

numNodes :: BST a -> Int

--------------------------------------------------------------------------------

-- sameShape bst1 bst2 : do BSTs 'bst1' and 'bst2' have the same shape ?

sameShape :: BST a -> BST b -> Bool

--------------------------------------------------------------------------------

-- numLeaves bst : The number of leaves in the BST 'bst'.

numLeaves :: BST a -> Int

--------------------------------------------------------------------------------

-- minValue bst : The minimum value stored in the non-empty BST 'bst'.

minValue :: BST a -> a

--------------------------------------------------------------------------------

-- maxValue bst : The maximum value stored in the non-empty BST 'bst'.

maxValue :: BST a -> a 

--------------------------------------------------------------------------------

-- height bst : The height of the BST 'bst'.

height :: BST a -> Int 

--------------------------------------------------------------------------------

-- occurs v bst :  Is the value 'v' stored at any node of the BST 'bst'?

occurs :: Ord a => a -> BST a -> Bool

--------------------------------------------------------------------------------

-- mirror bst : The mirror image of the BST 'bst', in which all left and right
-- subtrees have been swapped.

mirror :: BST a -> BST a 

--------------------------------------------------------------------------------

-- treeSort list : A copy of the list 'list', with its items arranged into 
-- ascending order.

treeSort :: Ord a => [a]->[a]

--------------------------------------------------------------------------------
-- I M P L E M E N T A T I O N  :  P R I V A T E
--------------------------------------------------------------------------------

insert v bst = if isEmptyBST bst then
                  node emptyBST v emptyBST
               else
               if v < rootval then
                  node ( insert v lsub ) rootval rsub
               else
                  node lsub rootval ( insert v rsub )
               where
                  rootval = rootVal bst
                  lsub    = lSub bst
                  rsub    = rSub bst

--------------------------------------------------------------------------------

numNodes bst = if isEmptyBST bst then
                  0
               else
                  numNodes ( lSub bst ) + 1 + numNodes ( rSub bst )

--------------------------------------------------------------------------------

sameShape bst1 bst2 = ( isEmptyBST bst1 && isEmptyBST bst2 )
                      ||
                      ( not ( isEmptyBST bst1 ) && not ( isEmptyBST bst2 )
                        &&
                        sameShape ( lSub bst1 ) ( lSub bst2 )
                        &&
                        sameShape ( rSub bst1 ) ( rSub bst2 ) )

--------------------------------------------------------------------------------

numLeaves bst 
  | isEmptyBST bst                     = 0
  | isEmptyBST lsub && isEmptyBST rsub = 1
  | otherwise                          = numLeaves lsub + numLeaves rsub 
  where
    lsub = lSub bst
    rsub = rSub bst

--------------------------------------------------------------------------------

minValue bst 
  | isEmptyBST $ lSub bst = rootVal bst
  | otherwise             = minValue $ lSub bst

--------------------------------------------------------------------------------

maxValue bst
  | isEmptyBST $ rSub bst = rootVal bst
  | otherwise             = maxValue $ rSub bst

--------------------------------------------------------------------------------

height bst
  | isEmptyBST bst = 0
  | otherwise = max (height (lSub bst)) (height (lSub bst)) + 1

--------------------------------------------------------------------------------

occurs v bst
    | isEmptyBST bst = False
    | v == rootval   = True 
    | v < rootval    = occurs v lsub 
    | v > rootval    = occurs v rsub
    where
      rootval = rootVal bst
      lsub    = lSub bst
      rsub    = rSub bst

--------------------------------------------------------------------------------

mirror bst
  | isEmptyBST bst = bst
  | otherwise      = node ( mirror rsub ) rootval ( mirror lsub )
  where
    rootval = rootVal bst
    lsub    = lSub bst
    rsub    = rSub bst

--------------------------------------------------------------------------------

treeSort list = treeToList ( listToTree list )

--------------------------------------------------------------------------------

-- listToTree xs 
-- build a BST from the items in 'list'
listToTree :: Ord a => [a] -> BST a
listToTree = foldr insert emptyBST

--------------------------------------------------------------------------------

-- treeToList tree
-- traverse BST to a list
treeToList :: BST a -> [a]
treeToList bst 
  | isEmptyBST bst = []
  | otherwise = treeToList (lSub bst) ++ (rootVal bst) : treeToList (rSub bst)

--------------------------------------------------------------------------------
t1 = insert 8 $ insert 4 $ insert 5 $ insert 6 emptyBST
t2 = insert 1 $ insert 9 $ insert 8 $ insert 4 $ insert 5 $ insert 6 emptyBST
t3 = listToTree [1,2,4,5,6,7,8,3]
t4 = treeSort [1,4,5,7,2,4,3,9,0]