Binary Search Tree Assignment
We will build some of the Higher Order Function Hall of Fame inductees but for a tree datatype.
datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree
Contents
Code To Implement
- binary_tree/binary_tree.sml
- binary_tree/apps_using_binary_tree.sml
BinaryTree
datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree
insert
fun insert (compare_function:(('a * 'a) -> order)) (t:'a tree) (item:'a) : 'a tree
map
reference: List.map
fun map(f : 'a -> 'b, t : 'a tree) : 'b tree = raise NotYetImplemented
filter
reference: List.filter
fun filter(predicate : 'a -> bool, t : 'a tree) : 'a tree = raise NotYetImplemented
find_lnr
reference: List.find
reference: In-order traversal
fun find_lnr(predicate : 'a -> bool, t : 'a tree) : 'a option = raise NotYetImplemented
fold_lnr
reference: List.foldl
reference: In-order traversal
fun fold_lnr(f : 'a * 'b -> 'b, init : 'b, t : 'a tree ) : 'b = raise NotYetImplemented
Application
max_height
fun max_height(t : 'a BinaryTree.tree) : int = raise NotYetImplemented
sum_int_tree
fun sum_int_tree(t : int BinaryTree.tree) : int = raise NotYetImplemented
Testing
studioTree/unittest_tree.sml