(*tsearch*) (* Tree search data structures and traversal and insertion fns *) (* An 'a tree has (1) a left branch (which is an 'a Node of a tree or is a leaf) (2) an 'a value (3) a right branch (which is an 'a Node of a tree or is a leaf) *) datatype 'a tree = Lf|Node of ('a tree * 'a * 'a tree); fun leaf x = Node(Lf,x,Lf); (* A terminal node is called a leaf and is created as above *) fun leafp (Node(Lf,_,Lf)) = true |leafp anything_else = false; (* Given a node within a tree, is it a leaf node? *) exception Out_of_Bounds; fun get Lf k = raise Out_of_Bounds |get (Node(l,a,r)) k = if k=1 then a else if k mod 2 = 0 then get l (k div 2) else get r (k div 2); fun put Lf k data = raise Out_of_Bounds |put (Node(l,a,r)) k data = if k=1 then Node(l,data,r) else if k mod 2 = 0 then Node((put l (k div 2) data),a,r) else Node(l,a,(put r (k div 2) data)); fun add_element_to Lf k data = if k=1 then Node(Lf,data,Lf) else raise Out_of_Bounds |add_element_to (Node(l,a,r)) k data = if k mod 2 = 0 then Node((add_element_to l (k div 2) data),a,r) else Node(l,a,(add_element_to r (k div 2) data)); fun make_vector n init_value = if n = 0 then raise Out_of_Bounds else if n=1 then Node(Lf,init_value,Lf) else add_element_to (make_vector (n-1) init_value) n init_value; fun preorder Lf = [] |preorder (Node(l,x,r)) = [x] @ preorder l @ preorder r; fun inorder Lf = [] |inorder (Node(l,x,r)) = (inorder l)@[x]@(inorder r); fun postorder Lf = [] |postorder (Node(l,x,r)) = postorder l @ postorder r @ [x]; fun get2 x i j = get (get x i) j; fun put2 x i j data = let val y = get x i in put x i (put y j data) end; fun get3 x i j k = get (get2 x i j) k; fun put3 x i j k data = let val z = get2 x i j in put2 x i j (put z k data) end;