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:
Note that you will in general need various list-processing functions (maps, etc.) when dealing with
data BTree a = Tip | BNode a (BTree a) (BTree a) deriving Show data Rose a = Branch a [Rose a] deriving Show
Rosetrees, 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
with letters, is not a search tree, just a plain binary tree ...
samplebst tree, using numbers, is a (binary)
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).
postordfunction 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
samplebinbinary tree from above, you should have:
Trees> postord samplebin "CDBGFJIKHEA"
maxt. These functions should use the
Maybetype 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
pathwhich 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:
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
data Dir = L | R deriving Show
Dirvalues. You may use either an error message or the
Maybetype to handle missing values.
OR (just one!)
path :: Ord a => a -> BTree a -> [Dir]
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)
rsize :: Rose a -> Integer, to count the number of node values in a rose tree;
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);
rmap :: (a -> b) -> Rose a -> Rose b, to map a function across the node values in a rose tree
rzip :: Rose a -> Rose b -> Rose (a,b), to zip together two rose trees into a tree of pairs; just as with the usual
zipfunction on lists, you should trim the results to the minimum available structure between the two input trees.
rmirror :: Rose a -> Rose a, to return the "symmetric opposite" of a rose tree, as if it were mirrored down the middle.