Java Data Structures - Contents
A D V E R T I S E M E N T
And now, back to the show, or shall I say Binary
Trees! A binary tree we'll be designing in this section will be what's known as binary
search tree. The reason it's called this is that it can be used to sort numbers (or
objects) in a way, that makes it very easy to search them; traverse them. Remember how
I've said that traversals only make sense in some specific context, well, in binary search
tree, only the in-traversal makes sense; in which numbers (objects) are printed in a
sorted fashion. Although I'll show all traversals just for the fun of it.
A binary search tree will extend our pGenericBinaryTree,
and will add on a few methods. One that we definitely need is the insert()
method; to insert objects into a tree with binary search in mind. Well,
instead of just talking about it, lets write the source!
import pComparable;
public class pBinarySearchTree extends pGenericBinaryTree{
public pBinarySearchTree(){
super();
}
public pBinarySearchTree(Object o){
super(o);
}
public void print(){
print(2);
}
public void insert(pComparable o){
pTwoChildNode t,q;
for(q = null, t = getRoot();
t != null && o.compareTo(t.getData()) != 0;
q = t,t = o.compareTo(t.getData()) < 0
? t.getLeft():t.getRight());
if(t != null)
return;
else if(q == null)
setRoot(new pTwoChildNode(o));
else if(o.compareTo(q.getData()) < 0)
insertLeft(q,o);
else
insertRight(q,o);
}
}
As you can obviously see, the insert(pComparable)
method is definitely the key to the whole thing. The method starts out by declaring two
variables, 't', and 'q'. It then falls into a for
loop. The condition inside the for loop is that 't' does not
equal to null (since it was initially set to getRoot(), which
effectively returns the value of root), and while the object we're trying to insert
does not equal to the object already inside the tree.
Usually, a binary search tree does not allow
duplicate insertions, since they're kind of useless; that's why we're attempting to catch
the case where we're trying to insert a duplicate. Inside the for
loop, we set 'q' to the value of the next node to be examined. We do this by
first comparing the data we're inserting with the data in the current node, if it's
greater, we set 't' to the right node, if less, we set it to the left node
(all this is cleverly disguised inside that for statement).
We later check the value of 't' to make
sure we've gotten to the end (or leaf) of the tree. If 't' is not null,
that means we've encountered a duplicate, and we simply return. We then check
to see if the tree is empty (didn't have a root), if it didn't, we create a new
root by calling setRoot() with a newly created node holding the
inserted data.
If all else fails, simply insert the
object into the left or the right child of the leaf node depending on the value of the
data. And that's that!
Understanding binary search trees is not easy, but
it is the key to some very interesting algorithms. So, if you miss out on the main point
here, I suggest you read it again, or get a more formal reference (where I doubt you'll
learn more).
Anyway, as it was with our stacks and queues, we
always had to test everything, so, lets test it! Below, I give you the test module for the
tree.
import java.io.*;
import pInteger;
import pBinarySearchTree;
class pBinarySearchTreeTest{
public static void main(String[] args){
pBinarySearchTree tree = new pBinarySearchTree();
pInteger n;
int i;
System.out.println("Numbers inserted:");
for(i=0;i<10;i++){
tree.insert(n=new pInteger((int)(Math.random()*1000)));
System.out.print(n+" ");
}
System.out.println("\nPre-order:");
tree.print(1);
System.out.println("\nIn-order:");
tree.print();
System.out.println("\nPost-order:");
tree.print(3);
}
}
As you can see, it's pretty simple (and similar to
our previous tests). It first inserts ten pInteger (pComparable)
objects in to the tree, and then traverses the tree in different orders. These different
orders print out the whole tree. Since we know it's a binary search tree, the in-order
traversal should produce an ordered output. So, lets take a look at the output!
Numbers inserted:
500 315 219 359 259 816 304 902 681 334
Pre-order:
500 315 219 259 304 359 334 816 681 902
In-order:
219 259 304 315 334 359 500 681 816 902
Post-order:
304 259 219 334 359 315 681 902 816 500
Well, our prediction is confirmed! The in-order
traversal did produce sorted results. There is really nothing more I can say about this
particular binary search tree, except that it's worth knowing. This is definitely not the
fastest (nor was speed an issue), and not necessarily the most useful class, but it sure
may proof useful in teaching you how to use trees.
And now, onto something completely different! NOT!
We're going to be doing trees for a while... I want to make sure you really understand
what they are, and how to use them. (and to show you several tricks other books try to
avoid <especially Java books>)
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
| 
Add to Favorites
Make Home Page
