You may work individually or in pairs.
For this problem assume that given trees are binary (i.e. each node has at most two children, left and right), but not necessarily binary search trees, i.e. there is not relation between values of a parent and a child node. There is enough information given in each item to uniquely determine all nodes in the tree corresponding to that item.
equals
method
Add an equals
method to the BinarySearchTree class.
According to Java specification, equals method
takes any object. It then checks if the parameter object is of the same type
as this object (see instanceof
check below).
If the object passes the instanceof check, it is then typecast to BinarySearchTree<K,V>. See more on instanceof here: http://www.java2s.com/Tutorial/Java/0060__Operators/TheinstanceofKeyword.htm.
The method is declared and starts as follows:
public boolean equals(Object obj) {
// checking that obj is an OurLinkedList
if (!(obj instanceof BinarySearchTree) ) return false;
// typecasting obj to BinarySearchTree
BinarySearchTree<K,V> otherTree = (BinarySearchTree<K,V>) obj;
// the rest of your code goes here, use otherTree variable:
}
Two binary search trees are considered equal if all nodes of one tree
correspond to nodes with equal keys, values, and position in the
tree, and vice versa. Use equals
method on values and on
keys to check that they are equal.
Note that it is also the case that two trees are equal if and only if one has exactly the same in-order and post-order traversal as the other, but you are not allowed to use this property as a way to establish tree equality.
Test your method extensively using JUnit, submit all your test cases.
Submit the java file(s) with your testing code by e-mail to me. Make sure to CC your group partner (if any).
The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.