Binary Search Tree Assignment

From CSE425S Wiki
Revision as of 16:57, 21 February 2020 by Dennis.cosgrove (talk | contribs) (Created page with "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 File:Sorted bin...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

Sorted binary tree inorder

Code To Implement

studioTree/tree.sml

Utilities

max_height

fun max_height(t : 'a tree) : int = 
    raise NotYetImplemented

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

sum_int_tree

fun sum_int_tree(t : int tree) : int =
    raise NotYetImplemented

Testing

studioTree/unittest_tree.sml