| /Users/adelaide/Public/Netbeans - All JSR Projects/Binary Tree ITDegrees/src/binarytreepackage/ITDegreeSearchTree.java |
12
13 private ITDegreeNode root = null; 14 15 public ITDegreeSearchTree() { 16 root = new ITDegreeNode(null); 17 } 18 19 public void addNode(ITDegree degree) { 20 if (root.getValue() == null) { 21 root.setValue(degree); 22 } else { 23 ITDegreeNode nodeToAdd, travellerNode, travellerBackup = null; 24 travellerNode = travellerBackup = root; 25 nodeToAdd = new ITDegreeNode(degree); 26 while (travellerNode != null) { 27 travellerBackup = travellerNode; 28 if (nodeToAdd.getValue().getDegreeType().compareTo(travellerNode.getValue().getDegreeType()) > 0) { 29 travellerNode = travellerNode.getRight(); 30 } else { 31 travellerNode = travellerNode.getLeft(); 32 } 33 } 34 if (nodeToAdd.getValue().getDegreeType().compareTo(travellerBackup.getValue().getDegreeType()) > 0) { 35 travellerBackup.setRight(nodeToAdd); 36 } else { 37 travellerBackup.setLeft(nodeToAdd); 38 } 39 } 40 }
41
The best way to understand the way the adding to a binary search tree works is to take your time, one step at a time, with the animation. But here's a narrative explanation of the process, with a bit of embellishment and emphasis on a few things.
Generally, adding a node involves traversing through the tree, one node at a time, "asking the question" "Is the data I am adding greater than, or less than the node that I am presently at?" At each node, if the answer is "greater than", then you move down the right hand branch of that node. And if the answer is "less than", then you move down the left branch of that node. There-by, each step, you move down one (horizontal) level of the tree, getting closer and closer to a free node. Eventually, you will reach a node which is presently null, and that is where you will connect your new node.
In the code above, what I call the "travellerNode" is the temporary node where we are at any given step in our path. So it is the data of the "travellerNode" which gets compared to the data of our "nodeToAdd". So it is, in effect, the travellerNode, which travels through the tree, seeking the proper end point to add the node to.
The "travelling" just referred makes up the bulk of the steps that will be needed with each addition, but you'll note that there are two general steps to the overall method (along with the compulsory check for an empty tree in lines 20 to 22). The two general steps to the method are:
1. From lines 26 o 33 above, is the traversal to the correct place to add the node.
2. From lines 34 to 37 is the actual addition of the node in that correct place.
When you look at those two steps, it may occur to you that there seems to be unnecessary repetition of the determination of "right" or "left". But the thing to keep in mind here is that in the while loop, this is done over and over again to determine the step-by-step "turns" through the tree to reach the destination. But once you reach the destination, you still have to determine which branch you will add to, the left or the right. So the comparison step does indeed have to be made one more time.
Another curious thing to note is the presence of a "travellerBackup" Node. It is needed since the travellerNode will have become null once it reaches the "end of the line", so we will need a copy of it (before it became null) to which we can add our new node.