There are two situations in which we will be searching through a binary search tree. In the first case, we are searching in terms of the key way the tree is organized - in the case of a primitives tree, then the primitive itself is the key, and in the case of "template class" objects, the tree will have been organized by one of the attributes, the key field. In this case, the key may or may not be a unique record. For unique records, a pure binary search is all we need. And for multiple record results, it will be a binary search with a few more steps added on.
The second general situation is if we have a tree of "template class" objects, and we are looking for something which was not the key organizational field. And in this case, it is (almost) always possible that there can be more than one instance of what we are searching for. So one way or the other, we will have to (at least start) traverse(ing) the entire tree.
I'll leave this for you to implement, but keep in mind that this should be little different from the add method of the tree. There are only two differences. In the "traversal" part, the while will have an extra else - if what we are looking for is equal to where we are. In that case, if it is a tree of primitives, we will just return true, indicating that what we were looking for is indeed there. Or if it is objects we have been looking through, we will return the object, so it can be used to access other specific attributes of it. The other difference between this searching method and our add method is that there is no need for the adding part.
| /Users/adelaide/Public/Netbeans - All JSR Projects/Binary Tree ITDegrees/src/binarytreepackage/ITDegreeSearchTree.java |
41 42 private ITDegree [] foundObjectArray = new ITDegree[10]; 43 private int counter = 0; 44 private ITDegree foundObjectElement; 45 46 public ITDegree [] findElement(String s) { 47 for(int i = 0; i < foundObjectArray.length; i++){ 48 foundObjectArray[i] = new ITDegree(); 49 } 50 foundObjectElement = new ITDegree("not found", "not found", -999); 51 findElementHelper(root, s); 52 return foundObjectArray; 53 } 54 55 private void findElementHelper(ITDegreeNode p, String city) { 56 if (p != null) { 57 findElementHelper(p.getRight(), city); 58 findElementHelper(p.getLeft(), city); 59 if (p.getValue().getCity().equals(city)) { 60 foundObjectElement = p.getValue(); 61 foundObjectArray[counter] = foundObjectElement; 62 counter++; 63 } 64 } 65 } 66
Basically, in this algorithm, we traverse through the tree looking for when the find field data matches what we are looking for. The way it moves through the tree is very similar to the way the traversal. So, though there is no animation per-se of this searching algorithm, referring to the "traversal" animations will help a great deal in your understanding of this.
Before looking at the main traversal method above (the "findElementHelper"), you may wonder why do we have both the "findElement" and "findElementHelper" methods? The reason here is the same as in the traversal methods: we simply want to make the calling of the method easier and more straight-forward for the user of our method. We do not want them to have to remember to send both what they are looking for and also "root". Rather, it is much more intuitive for them to send just what they are looking for as a parameter. Thus, with our "findElement" method that's all we take in, but behind the scenes, we then send both root and the thing to be found to the findElementHelper - which will need both, as it sends progressive Nodes to recursive findElementHelper calls.
So, now to the real action, which are the findElementHelper method instances themselves.
Our goal is to move efficiently through the entire binary search tree, trying to locate all of what we are looking for. This will involve as many steps as there are nodes in the tree, given non-unique results. (And do note here, once again, that this "Situation 2" implementation is not a log2n kind of a search. This implementation assumes that we will be looking for data that is not of the "key" field which was used to create the binary search tree, and assumes that there can be more than one instance of what we are looking for.)
So we get to each node, and every time we find what we are looking for, we add it to an array, which we will return when we are finished. The complete traversal through the tree is accomplished becasue each call (given that it is not at the end of a line - i.e. p == null) will call two other instances of the method, which will continue the search left and right. Each instance of the findElementHelper will eventually finish when it gets to an "end of the line", when the p is null. When all of those calls are finished, i.e., when all of the recursive calls to findElementHelper are popped off the recusrive call stack, we end up back to the first method called in this procedure, the one and only findElement method itself, which as its last line returns the foundObjectArray.
Ta da!