Java Data Structures - Contents
A D V E R T I S E M E N T
As I've mentioned before, node-pool implementations
are fairly similar to the regular ones, so, our old sort tree will not change much. The
only things that will change however, are the node handling methods. Since we already know
what needs to be done (review the binary sort example described previously in this
document), we can just go ahead and write the source.
import pNodePoolTreeNode;
import pNodePoolArrayTree;
import java.lang.*;
public class pNodePoolSortArrayTree extends pNodePoolArrayTree{
public pNodePoolSortArrayTree(){
super();
}
public pNodePoolSortArrayTree(int n){
super(n);
}
public void print(){
print(2);
}
public void insert(Comparable obj){
int t,q = -1;
t = getRoot();
while(t != -1 && !(obj.equals(getNode(t).getData()))){
q = t;
if(obj.compareTo(getNode(t).getData()) < 0)
t = getNode(t).getLeft();
else
t = getNode(t).getRight();
}
if(t != -1)
return;
if(q == -1){
setData(obj);
return;
}
if(obj.compareTo(getNode(q).getData()) < 0)
insertLeft(q,obj);
else
insertRight(q,obj);
}
}
Now, the following only makes sense inside a JDK 1.2
(or above) context. Earlier version of the JDK do not support the Comparable interface.
I just though it would be nice to show how to use all these cool interfaces introduced
with JDK 1.2!
The code does nothing special, and chances are, you
can figure it out on your own. The only seeming difference between this source and the one
presented earlier, is that in this one, whenever we test for a null node, we're not
testing the node, we're testing whether if it has value of -1. Other than
that, the code looks almost identical.
This code is pretty bad, however, in illustrating
the beauty of Object Oriented programming. With our approach, we needed to change the
whole thing just to implement node-pools. Ideally, we should strive to only have to change
one part of the system. For example, we could have only changed the abstract
parent class, and leave everything else as it was. Or we could have changed the node a
little, and make the node itself support stuff, but I just thought this was a clearer
approach, without dragging all that Object Oriented stuff into the issue.
I think I've made this Node Pool section longer than
it should be; so, let me quickly wrap it up by getting right to the point. Lets write a
test driver (which will be an almost identical copy of the old test driver).
import java.io.*;
import pNodePoolSortArrayTree;
public class pNodePoolSortArrayTreeTest{
public static void main(String[] args){
pNodePoolSortArrayTree tree =
new pNodePoolSortArrayTree(100);
int i,n;
System.out.println("Numbers inserted:");
for(i=0;i<10;i++){
tree.insert(new Integer(n=(int)(Math.random()*1000)));
System.out.print(n+" ");
}
System.out.println("\nPre-order:");
tree.print(1);
System.out.println("\nIn-order:");
tree.print(2);
System.out.println("\nPost-order:");
tree.print(3);
}
}
You'll notice that the code above uses java.lang.Integer
object, instead of our own pInteger one. That's because in JDK 1.2, an Integer
is implementing Comparable interface, simplifying a whole lot of stuff. Other
than that, the code works identically to the one shown earlier in the document. Just to be
complete, however, lets include the output from the above program.
Numbers inserted:
103 82 165 295 397 828 847 545 766 384
Pre-order:
103 82 165 295 397 384 828 545 766 847
In-order:
82 103 165 295 384 397 545 766 828 847
Post-order:
82 165 295 397 384 828 545 766 847 103
I guess that wraps it up. (finally!) Now, I'm gonna
take a little break, and try to come up with some cool programs that use these data
structures. The only way to actually learn what they are, and how to use them, is to see
them in action. And some of these can be VERY useful in a wide variety of applications,
ranging form databases, to graphics programming.
So, now that you know all the basics of everything
about data structures, the remainder of this document will mostly concentrate on
interesting approaches, and algorithms using these. (You'll be surprised how far a binary
sort tree can go when it comes to creating virtual 3D worlds!)
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
