I need some help with a class assignment. I have a binary tree that I am supposed to do, the requirements for the assignment are listed below.
Quote: 1.
Given an interface defining methods for manipulating an ordered, binary tree, write an implementation of an ordered, binary tree that matches the interface.
The ordered, binary tree class you will be building has the following features:
* Each node in the tree can hold one and only one Object associated with the node.
* Each node has a unique integer identifier and can have a left child node and a right child node.
* The unique identifiers are sequentially assigned as nodes are added to the tree.
* The binary tree constructor method should create an initial, empty tree and should initialize the sequential integer identifier to zero.
Since you are coding an ordered tree, the objects stored in each node should implement the Comparable interface so that they can be ordered.
The algorithm to add nodes to an ordered, binary tree can be found in many different textbooks, including books on Discrete Mathematics or Algorithms.
Your professor will provide you with the interface you will implement in the form of a JAR file. The interface contains the following methods:
* void add(Object o) throws Exception - Add the supplied object to the tree. If the object is already present in the tree (the object "equals" another object), throw an appropriate exception, defined by you.
* boolean isPresent(Object o) - Returns true if the passed object is already present in the tree. In other words, the passed object "equals" one already in the tree. Returns false otherwise.
* Object get(int i) throws Exception - Returns the object that appears in position i when the tree is traversed in order. This method should throw an appropriate exception if i is out of range.
* Object[] getAllOrdered() - Returns an array containing the objects in the tree in the correct order (Hint: See "in-order traversal of binary trees" in algorithm textbooks).
* Object[] getAll() - Returns an array containing the objects in the tree in the order in which they were originally added to the tree (Hint: Make use of the sequential, unique identifier for producing this array).
When implementing this interface, your class should throw the exceptions you have defined, not the generic Exception class.
2. Your code represents a library or set of classes and interfaces that can be used by others. To test your coding, write a separate driver class that thoroughly tests the interface. You do not have to turn in this driver class, however, with your assignment. A separate driver class will be used by your professor to thoroughly test your code.
What would the output look like for a correct implementation?
I will have a driver program that will test your implementation of the interface. My driver will create a binary tree object and call each of the methods. For example, I will call the add method to make sure that I can add an object. I will then attempt to add the same object again to verify that you throw an appropriate exception.
When I call the getAllOrdered method, I expect to receive an array that contains the “in-order traversal of the binary tree.” As the assignment suggests, you should look this up online or in an algorithms/data structures text book. My driver will then print out the array to verify that it is correct. (Of course, you will also have to develop a driver of your own to verify that your implementation is correct.)
When I call the getAll method, I expect to receive an array of the objects in ascending order starting from the first object that I entered and ending with the last object I entered.
The write-up on the assignment says that the add method accepts an Object as an argument, but the interface has Comparable as an argument. I am not sure what is going on here.
void add(Object o) throws Exception .....
I could use the comparable Interface to do object comparison, but I am not sure if this is what you are going for. Can you explain why you are passing the Comparable o to the method, and what we are supposed to do with this?
The assignment states: “Since you are coding an ordered tree, the objects stored in each node should implement the Comparable interface so that they can be ordered.” So yes, I would like for you to use the compareTo method in your implementation. The interface provided in the assignment description specified that add should accept an object:
void add(Object o) throws Exception .....
However, what happens if in my driver I try to pass an object to your add method that does NOT implement Comparable? I modified the interface I provided to
void add(Comparable o) throws Exception .....
only to underscore the point that your program can and should only add objects that implement Comparable. As a general rule of thumb in my personal programming style, if a data structure should only accept Comparable objects, I want to advertise that fact.
Since only Comparable objects are accepted by our Add method, why would the interface allow Objects to be passed to the "isPresent" method...shouldn't this have a Comparable argument as well? My plan is to Cast the object to a comparable, and return false if there is an exception. Is this the right way to handle it?
The binary tree you create should only contain Comparable objects. That is why the add method accepts only Comparable objects rather than just objects. The isPresent method doesn’t need to accept only Comparable objects because it is not adding anything to the tree. If the object is present in the binary tree, we know for a fact that it is Comparable. If the object is not present in the tree, we don’t care whether it is Comparable or not. If you want to do a pre-check on Comparable before searching the tree for the object, that is fine. However, it isn’t necessary.
How do I Create a Comparable Object and what data members and methods should it have?
Your implementation should not care what specific object you are using. As long as the object added to your binary tree is a Comparable Object, your program should do the right thing. You can create any sort of object you would like.
However, if you look up Comparable in the API (http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Comparable.html), you will see, right at the top, that there are a number of classes that implement Comparable already (for example, Character, Float, Integer, Double, Date).
That means you could, in your test driver, add Integers to your binary tree. (Please note that you need to add an Integer, which means calling the Integer constructor, rather than passing in a primitive int.) This would save you the trouble of creating your own object for the purposes of testing. It also may help simplify your testing effort.
For example, if I were a student, and I wanted to make sure that my in-order traversal algorithm worked correctly, I would (1) look for an example online that tells you what the correct in-order traversal output should be for a given set of input (like integers), (2) add each member of the input set to the tree as a new Integer, and (3) verify that the array returned by my getAllOrdered() function matches the order given in the example.
Should we be creating our own exception classes for this assignment? Or can we use/throw existing exception classes?
You can use existing exception classes, as long as they are specific and appropriate to the problem. You can also create your own if you'd rather.
Does my driver have to be interactive?
No, it doesn’t. You can hardcode the whole thing, and it will save you a lot of work if you do. However, make sure your driver covers all of the functionality, including exception triggers.
My driver is not interactive. I add values in a particular order, I call each of the functions, I delete certain values, I trigger exceptions, etc. My driver is organized in such a way that it is very easy for me to see exactly what is going on. Before I call functionA, for example, I have a print statement that tells me what the output should be. Something like this:
functionA should be: 1, 2, 3, 4, 5, 6
Calling functionA: 1, 2, 3, 4, 4, 4, 5, 6
I am lost on this assignment, and it is due in 2 days. I need a lot of help if anyone is willing to help, I am trying to understand binary trees but I can't seem to figure out how to implement what I have read in the context she wants. The interface she gave us and the little bit of the class that I built are below
Interface
public interface BinaryTree {
void add(Comparable o) throws Exception;
boolean isPresent(Object o);
Object get(int i) throws Exception;
Object [] getAllOrdered();
Object [] getAll();
}
TreeNode class
public class TreeNode implements BinaryTree {
/** Creates a new instance of TreeNode */
public TreeNode(String str) {
}
public void add(Comparable o) throws Exception {
}
public boolean isPresent(Object o) {
}
public Object get(int i) throws Exception {
}
public Object[] getAllOrdered() {
}
public Object[] getAll() {
}
Object item;
TreeNode left;
TreeNode right;
}
