(*tsearch*)

(* Tree search data structures and traversal and insertion fns *)

(*
   An 'a tree has 
    (1) a left branch (which is an 'a tree or tempty)
    (2) an 'a value
    (3) a right branch (which is an 'a tree or tempty)
  
   In addition we have the "constructor" Tree.

*)

datatype 'a tree = tempty|Tree of ('a tree * 'a * 'a tree);

fun leaf x = Tree(tempty,x,tempty);
(* A terminal node is called a leaf and is created as above *)

fun leafp (Tree(tempty,_,tempty)) = true
   |leafp anything_else = false;
(* Given a node within a tree, is it a leaf node? *)

fun tree_insert p x tempty = leaf x
   |tree_insert p x (Tree(l,y,r)) = if p x y
                                    then Tree(tree_insert p x l,y,r)
                                    else Tree(l,y,tree_insert p x r);
(* Given some binary predicate p (that is p is a fn 'a -> 'a -> bool)
   tree_insert inserts x into that tree. If (p x y) is true
   then x is inserted in the left branch, otherwise x is inserted
   into the right branch. 
   Function tree_insert delivers a new 'a tree
*)

fun preorder tempty = []
   |preorder (Tree(l,x,r)) = [x] @ preorder l @ preorder r;
(* A preorder traversal of a tree. Given a node
   get the contents of the node, 
   then preorder left of the node,
   then preorder right of the node*)

fun inorder tempty = []
   |inorder (Tree(l,x,r)) = inorder l @ [x] @ inorder r;
(* An inorder traversal of a tree. Given a node
   inorder left of the node
   then get the contents of the node
   then inorder right of the node *)

fun postorder tempty = []
   |postorder (Tree(l,x,r)) = postorder l @ postorder r @ [x];

(* Functions preorder, inorder and postorder traverse an 'a tree.
   Try them. *)

fun lt (a:int) (b:int) = a<b;
(* Is a less than b? *)

fun make_tree p [] t = t
   |make_tree p (a::x) t = make_tree p x (tree_insert p a t);
(* Given a binary predicate p, list of elements of type 'a and a tree 
   t that is initially tempty, create an 'a tree with these 'a 
   elements inserted. Example call would be as follows: *)

val x = make_tree lt [5,3,7,2,6,8,1,9,4] tempty;

(* Tutorial/Practical 

(1) Traverse x using preorder, inorder, and postorder
(2) Draw (using pen and paper) the tree x
    NOTE: you may have to manually analyse x as follows
          val Tree(l,a,r) = x;  (etc!)
(3) Create a new type of tree, using a different type and predicate
    For example, a dictionary of strings. Hint: you must define
    the appropriate binary predicate.
(4) Write a function that will deliver true if a specific object
    can be found in a tree (think... object is either in the left
    branch, or in the right branch)
(5) Write a function that delivers an integer result n, where n
    is the number of nodes in a tree
(6) Write a function that delivers an integer result n, where n
    is the number of "leaf" nodes in a tree
(7) Write a function that takes two trees as arguments and 
    checks for equality (are 2 trees equal?).
    NOTE: 2 interpretations are possible, 
          (a) T1 is same "shape as" T2
          (b) The contents of the nodes of T1 are the same
              as the contents of the nodes of T2
(8) Write a function to delete a node from a tree

*)