[ ^ CSE 341, Winter 2004 home page ]

Homework 5

Due: Fri 27 Feb 2004

Turn in hard copy in class, and an electronic copy as an email attachment sent to Sandra with the subject line [cse341-hw5-lastname-firstname].

All your Smalltalk classes for this assignment should reside in their own class category. To make the hard copy and electronic copy, fileOut your class category and use the resulting .st file.

Binary Trees in Smalltalk

• Write a TreeNode class with the subclasses EmptyNode and ValueNode. EmptyNodes are leaves of the tree that contain no value. ValueNodes contain a value and a left and a right subchild.

• Create a BinaryTree class that wraps TreeNode values. Like the binary tree from your ML assignment, this class should have two fields: root, which will contain the TreeNode that is the root of the tree; and a greaterThan function value which takes two arguments and returns a boolean.

• Unlike the ML binary tree you wrote, the Smalltalk binary tree's add: method will update values in place (using side effects) rather than returning fresh trees. Write the following methods for BinaryTree:

  add:

  Takes a value and adds it to the binary tree.

  do:

  Takes a block and applies it to each value in the tree, in sorted order.

  base:foldWith:

  Takes a base value and a fold function, and performs "tree fold" of each node with the fold function, analogously to tree fold from the ML assignment. The fold function parameter will take three arguments: the current value, and the results for the left and right subtrees.

  find:ifAbsent:

  Takes a predicate function and a "what-to-do-if-absent" function. Applies the predicate function to each value in the tree in order. If any value matches, returns it immediately. If no value matches, evaluates the ifAbsent: function and returns its value.

  You must implement these BinaryTree methods by delegating most of the responsibility to the nodes. For example, your BinaryTree add: method should not have a lot of complicated logic; instead, you should write addition methods for the node classes, and BinaryTree add: should simply send a message to the root node.

  Notice that EmptyNode's add method and TreeNode's add method will have to return the new node value --- which may be the same object as the old node value, but will not always be. Question to guide your thinking: when will a node's add: method not return the same node as itself?

• Write a short English paragraph (perhaps 4-5 sentences) comparing and contrasting this binary tree with your ML binary tree. How is code organized in each version? Which code gets "grouped together" in each language? What are the similarities?

• Write an alternative version of binary trees, as follows:

  • Name the class BinaryTree2. It should have root and greaterThan members, like BinaryTree.

  • However, for nodes, this class should use a single node class, TreeNode2, which has instance variables for the value and left and right children.

  • The empty case will be represented by nil (i.e., the UndefinedObject) instead of an explicit empty node class.

  Write add: and do: for BinaryTree2. Rather than delegating responsibilities to your TreeNode2 class, these methods should encapsulate all the logic of add: and do:.

  You may want to read the code for the following classes to help you do this one:

  • UndefinedObject (evaluate Browser newOnClass: nil class in a Workspace, or browse in category Kernel-Objects). The ifNil: method and others in the "testing" method category will probably be useful.

  • LinkedList (in category Collections-Sequenceable) and Link (in category Collections-Support). Notice that Link does not define a "payload" value --- this is because it is meant to be subclassed by clients! The client will define the payload and add links manually.