CS 254 Lab 6: The Botany Lab (trees!)

In this lab, we'll be using three kinds of trees: binary trees, binary search trees and general or rose trees. Recall from lecture that a binary search tree is structurally the same as a binary tree (and we'll use empty tips for each of them), but with the extra ordering property that every node value to the left of a given node is less than the value in that node, and vice versa every node value to the right is greater.

You can use the following definitions from lecture to implement the various kinds of trees: 

data BTree a = Tip | BNode a (BTree a) (BTree a)  deriving Show

data Rose a = Branch a [Rose a]  deriving Show
Note that you will in general need various list-processing functions (maps, etc.) when dealing with Rose trees, since lists are part of their definition.

Here are some sample trees you might want to use for testing, development and demo (notice also the leaf function, a little shorthand that makes entering tree data easier): 

leaf x = BNode x Tip Tip

samplebin = BNode 'A' (BNode 'B' (leaf 'C')
                                 (leaf 'D'))
                      (BNode 'E' (BNode 'F' (leaf 'G') Tip)
                                 (BNode 'H' (BNode 'I' Tip (leaf 'J'))
                                            (leaf 'K')))
                                            
samplebst = BNode 37 (BNode 25 (leaf 12) (BNode 28 Tip (leaf 32)))
                     (BNode 51 (BNode 42 (leaf 39) (BNode 47 (leaf 43) (leaf 49)))
                               (BNode 69 Tip (BNode 81 (BNode 72 (leaf 71) Tip) Tip)))

sampler = Branch "Amarantha"
            [ Branch "Bethesda" [Branch "Edna" []],
              Branch "Callipygia"
                [ Branch "Flegma" [Branch "Indicia"[],
                                   Branch "Jaundice" [],
                                   Branch "Kalahari" []
                                  ],
                  Branch "Ganache" []],
              Branch "Depilitoria" [Branch "Hildegarde" [Branch "Ludmilla" [],
                                                         Branch "Miasma" []]]
            ]

NOTE: of the three sample trees given above, the samplebin tree, with letters, is not a search tree, just a plain binary tree ... whereas the samplebst tree, using numbers, is a (binary) search tree.

You can see pictures of the two binary trees below; the general or rose tree sampler is a family tree from a lab exercise in my Data Structures course (the names are supposed to be those of the princesses of some far-away fantasy realm).

The exercises

  1. Write the postord function we left out in lecture; it should return the postorder traversal of a BTree, where the left and right sub-trees are traversed first, and the node value is "visited" last.

    For example, using the samplebin binary tree from above, you should have: 
    Trees> postord samplebin
"CDBGFJIKHEA"

  2. Write two functions (discussed in lecture!) to find the minimum and maximum values from a binary search tree; call them mint and maxt. These functions should use the Maybe type in the result in order to allow for empty trees (which don't have a minimum or maximum value). 
    Trees> mint samplebst
Just 12
Trees> maxt samplebst
Just 81

  3. Write a function called path which will return a list of "directions" to take to get to a particular value in a binary search tree. For the directions you may use the following data type: 
    data Dir = L | R  deriving Show
    Your function should accept a value that might be an item in a binary search tree, plus a tree itself, and return a path as a list of Dir values. You may use either an error message or the Maybe type to handle missing values. 
    path :: Ord a => a -> BTree a -> [Dir]
    OR   (just one!) 
    path :: Ord a => a -> BTree a -> Maybe [Dir]

    If you try the Maybe-fied version, you may want to use the following utility function to "push" a function "inside" a Maybe value (technically, this is really just the fmap function from the Maybe instance of the Functor type class, but you needn't worry too much about that): 

    push :: (a -> b) -> Maybe a -> Maybe b
push f  Nothing = Nothing
push f (Just x) = Just (f x)

  4. Write each of the following functions for general trees (a.k.a. rose trees):

    1. rsize :: Rose a -> Integer, to count the number of node values in a rose tree;

    2. rheight :: Rose a -> Integer, to measure the height, or longest path from the root to a child (count the height of a leaf as one);

    3. rmap :: (a -> b) -> Rose a -> Rose b, to map a function across the node values in a rose tree

    4. rzip :: Rose a -> Rose b -> Rose (a,b), to zip together two rose trees into a tree of pairs; just as with the usual zip function on lists, you should trim the results to the minimum available structure between the two input trees.

    5. rmirror :: Rose a -> Rose a, to return the "symmetric opposite" of a rose tree, as if it were mirrored down the middle.