CSC 148H: INTRODUCTION TO COMPUTER SCIENCE

Hints for Assignment 4

• More hints from Jeremy
  
  
• Many people are confusing the idea of a type/record with a class. A class is like a record in that it has fields, and it is like a type because you define it once, and can use it many times to instantiate individual objects. Do not use a class and a type to do the same thing. Look at the BST example to see how the fields of a node are declared. We never define a type for the node; the class takes care of that. Each node object that you instantiate will have the variables that are defined in the class and they will be like global variables inside the object.
  We have always told you to never use global variables, but things are a bit different in classes and modules. Here, any variables that you declare outside of a subprogram are global within the class, and that is a good thing. It fits with the object-oriented view of the world. An object has some data (stored in variables) and some operations that act on the data (written as subprograms).
  
  
• To think about the inheritance hierarchy of nodes, first think about what each of the specific node objects must do. So, what data does the digit node object have? What operations are possible on that data. What about the letter node? And the leaf node? Now, what parts of the data and operations are common to all nodes? Put those common parts into the generic node so that you only have to write it once. If something is similar between two types of node, then maybe you can massage it a bit and make it the same, and then put that into the generic node. Anything that is left must be specific to the type of node in question, and that belongs in the definition of that node's class.
  
  
• Some people are wondering why their classes for nodes are so simple and short, and whether that is right. The classes seem to have only some code to initialize a node. Well, this is because there isn't much else that a node can do.
  Now, we could put more operations into a node, such as print and insert, or we could put most of the work in the tree module. For example, in the BST example, insert is something that a node does, whereas print is something that the tree module does. See if you can make the nodes do the printing instead. In the assignment, you have to decide who does the work: each of the nodes, or the tree module. Either way will get you full marks as long as you do it recursively. (Of course, doing the work in the nodes is the only truly object-oriented way.)