Difference between revisions of "Binary Int Tree Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
 
(7 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
Prepare for the [[Binary_Search_Tree_Assignment|Binary Search Tree]] Exercise with a simpler warm up.
 
Prepare for the [[Binary_Search_Tree_Assignment|Binary Search Tree]] Exercise with a simpler warm up.
  
=Code to Implement=
+
=int_tree=
{{SMLToImplement|warmup_binary_int_tree|sum|binary_int_tree}}
+
  datatype int_tree = NODE of (int_tree * int * int_tree) | EMPTY
 +
 
 +
=Examples=
 +
==EMPTY==
 +
EMPTY
 +
==1==
 +
[[File:Binary int tree 1.svg]]
 +
==3==
 +
NODE(NODE(EMPTY, 1, EMPTY), 2, NODE(EMPTY, 3, EMPTY)))
  
==datatype==
+
[[File:Binary int tree 3.svg]]
  datatype int_tree = NODE of (int_tree * int * int_tree) | EMPTY
+
==7==
 +
NODE(NODE(NODE(EMPTY, 1, EMPTY), 2, NODE(EMPTY, 3, EMPTY)), 4, NODE(NODE(EMPTY, 5, EMPTY), 6, NODE(EMPTY, 7, EMPTY))))
  
<!--
+
[[File:Binary int tree 7.svg]]
[[File:Sorted binary tree inorder.svg|Sorted binary tree inorder|frame|LNR would produce: ABCDEFGHI<br>RNL would produce: IHGFEDCBA]]
+
 
-->
+
=Code to Implement=
 +
{{SMLToImplement|binary_int_tree|sum<br/>sum_accumulate<br/>fold_rnl|warmup_binary_int_tree}}
  
 
==sum==
 
==sum==
 +
Traverse the tree and produce the sum.
 +
 
  <nowiki>fun sum(node : int_tree) : int =
 
  <nowiki>fun sum(node : int_tree) : int =
 
raise Fail("NotYetImplemented")</nowiki>
 
raise Fail("NotYetImplemented")</nowiki>
  
 
==sum_accumulate==
 
==sum_accumulate==
 +
Traverse the tree and produce the sum, but this time perform the operation in a more fold like manner with an accumulated value.
 +
 
  <nowiki>fun sum_accumulate(init : int, node : int_tree) : int =  
 
  <nowiki>fun sum_accumulate(init : int, node : int_tree) : int =  
 
raise Fail("NotYetImplemented")</nowiki>
 
raise Fail("NotYetImplemented")</nowiki>
  
 
==fold_rnl==
 
==fold_rnl==
[https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in-order_(RNL) reverse order tree traversal]
+
Fold the tree with a [https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in-order,_RNL reverse order traversal] invoking <code>f</code> with each element and the accumulated value, using the evaluation as the updated accumulated value.
 +
 
 
  <nowiki>(*
 
  <nowiki>(*
 
  * depth-first, reverse in-order traversal
 
  * depth-first, reverse in-order traversal
  * https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in-order_(RNL)
+
  * https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in-order,_RNL
 
  *)
 
  *)
 
fun fold_rnl(f : (int * 'a) -> 'a, init : 'a, node : int_tree) : 'a =  
 
fun fold_rnl(f : (int * 'a) -> 'a, init : 'a, node : int_tree) : 'a =  

Latest revision as of 04:14, 21 October 2022

Motivation

Prepare for the Binary Search Tree Exercise with a simpler warm up.

int_tree

 datatype int_tree = NODE of (int_tree * int * int_tree) | EMPTY

Examples

EMPTY

EMPTY

1

Binary int tree 1.svg

3

NODE(NODE(EMPTY, 1, EMPTY), 2, NODE(EMPTY, 3, EMPTY)))

Binary int tree 3.svg

7

NODE(NODE(NODE(EMPTY, 1, EMPTY), 2, NODE(EMPTY, 3, EMPTY)), 4, NODE(NODE(EMPTY, 5, EMPTY), 6, NODE(EMPTY, 7, EMPTY))))

Binary int tree 7.svg

Code to Implement

file: src/main/sml/warmup_binary_int_tree/binary_int_tree.sml Smlnj-logo.png
functions: sum
sum_accumulate
fold_rnl

sum

Traverse the tree and produce the sum.

fun sum(node : int_tree) : int =
	raise Fail("NotYetImplemented")

sum_accumulate

Traverse the tree and produce the sum, but this time perform the operation in a more fold like manner with an accumulated value.

fun sum_accumulate(init : int, node : int_tree) : int = 
	raise Fail("NotYetImplemented")

fold_rnl

Fold the tree with a reverse order traversal invoking f with each element and the accumulated value, using the evaluation as the updated accumulated value.

(*
 * depth-first, reverse in-order traversal
 * https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in-order,_RNL
 *)
fun fold_rnl(f : (int * 'a) -> 'a, init : 'a, node : int_tree) : 'a = 
	raise Fail("NotYetImplemented")

Testing

source folder: src/test/sml/warmup_binary_int_tree
how to run with CM.make verbosity off: sml -Ccm.verbose=false run_binary_int_tree_testing.sml
how to run with CM.make verbosity on: sml run_binary_int_tree_testing.sml

note: ensure that you have removed all printing to receive credit for any assignment.

SML Error Messages