Java Data Structures - Contents
A D V E R T I S E M E N T
A node-pool tree is not that much different from a
regular tree. The only key differences is that it has to maintain a linked list (more or
less a "stack") of free nodes, and allocate them when needed.
Another tricky thing is that now, the node's
children are pointed to by integers, which are references into a node-pool array; so,
watch out. You'll notice that a lot of the "tree stuff" has been re-used from
the previous version, and you're right! It makes it a lot easier to understand on your
part, and a lot easier to write on mine! (oh, I just ran out of coffee...)
import pNodePoolTreeNode;
import java.io.*;
public abstract class pNodePoolArrayTree{
private int numNodes,nextAvail;
private pNodePoolTreeNode[] arrayNodes;
protected int root;
private void init(){
int i;
root = -1;
arrayNodes = new pNodePoolTreeNode[numNodes];
nextAvail = 0;
for(i=0;i<numNodes;i++)
arrayNodes[i] = new pNodePoolTreeNode(-1,i+1);
getNode(i-1).setRight(-1);
}
public pNodePoolArrayTree(){
numNodes = 500;
init();
}
public pNodePoolArrayTree(int n){
numNodes = n;
init();
}
protected int getNode(){
int i = nextAvail;
nextAvail = getNode(nextAvail).getRight();
if(nextAvail == -1){
nextAvail = i;
return -1;
}
return i;
}
protected void freeNode(int n){
getNode(n).setRight(nextAvail);
nextAvail = n;
}
public boolean isEmpty(){
return getRoot() == -1;
}
public boolean isFull(){
int i = getNode();
if(i != -1){
freeNode(i);
return false;
}
return true;
}
protected Object getData(){
if(isEmpty())
return null;
return getNode(getRoot()).getData();
}
protected void setData(Object o){
if(isEmpty())
root = getNode();
getNode(root).setData(o);
getNode(root).setLeft(-1);
getNode(root).setRight(-1);
}
protected int getLeft(){
if(isEmpty())
return -1;
return getNode(getRoot()).getLeft();
}
protected void setLeft(int n){
if(isFull())
return;
if(isEmpty()){
root = getNode();
getNode(getRoot()).setRight(-1);
}
getNode(getRoot()).setLeft(n);
}
protected void setRight(int n){
if(isFull())
return;
if(isEmpty()){
root = getNode();
getNode(getRoot()).setLeft(-1);
}
getNode(getRoot()).setRight(n);
}
protected int getRight(){
if(isEmpty())
return -1;
return getNode(root).getRight();
}
protected int getRoot(){
return root;
}
protected pNodePoolTreeNode getNode(int n){
if(n != -1)
return arrayNodes[n];
else return null;
}
protected void insertLeft(int node,Object o){
if((node != -1) && (getNode(node).getLeft() == -1)
&& !isFull()){
int i = getNode();
getNode(i).setData(o);
getNode(i).setRight(-1);
getNode(node).setLeft(i);
}
}
protected void insertRight(int node,Object o){
if((node != -1) && (getNode(node).getRight() == -1)
&& !isFull()){
int i = getNode();
getNode(i).setData(o);
getNode(i).setRight(-1);
getNode(node).setRight(i);
}
}
public void print(int mode){
switch(mode){
case 1:
pretrav();
break;
case 2:
intrav();
break;
case 3:
postrav();
break;
}
}
public void pretrav(){
pretrav(getRoot());
}
private void pretrav(int p){
if(p == -1)
return;
System.out.print(getNode(p).getData()+" ");
pretrav(getNode(p).getLeft());
pretrav(getNode(p).getRight());
}
public void intrav(){
intrav(getRoot());
}
private void intrav(int p){
if(p == -1)
return;
intrav(getNode(p).getLeft());
System.out.print(getNode(p).getData()+" ");
intrav(getNode(p).getRight());
}
public void postrav(){
postrav(getRoot());
}
private void postrav(int p){
if(p == -1)
return;
postrav(getNode(p).getLeft());
postrav(getNode(p).getRight());
System.out.print(getNode(p).getData()+" ");
}
}
There are not that many hard methods in this one;
so, lets focus in on the hard ones, and I'll leave you to figure out the "easy"
ones yourself.
One thing I'd like to mention of the top so that it
causes as little confusion as possible: now that we're not using objects, but integers, we
still have to note the "null node" somehow, so, in our example, I'm
using -1 as the "null node" indicator.
Data members numNodes, nextAvail,
and arrayNodes are there to keep track of the linked list of free and
occupied nodes. It's not exactly a linked list (although many people like to think of it
that way), it's more or less a simple array stack we've implemented at the beginning of
this document. The numNodes is the maximum number of nodes inside this tree;
we could just as well substitute it for arrayNodes.length, but I think this
"separation" is more convenient.
The nextAvail member is the one that
points to the next available node. Our allocation methods, getNode() and freeNode(int
n), uses this particular pointer to allocate and release nodes. And arrayNodes
is just an array holding the node-pool. All of the integer child references are into this arrayNodes
array; which we allocate dynamically during instantiation (creation) of the object.
Inside the init() function, we allocate
the arrayNodes array to hold the node-pool. We later loop through all the
nodes inside of it, and turn them into a linked list (with right child pointing to the
next available node and left child being -1). The last node in the list is
apparently marked -1; since it's last!
I suggest you go over the source for getNode()
and freeNode(int n); try to understand what it's doing. Which is nothing more
complex than what we've already done! (look over the linked list description if you find
it confusing)
The rest of the functions are pretty much self
explanatory (you should be able to figure them out). Most of them are just a port of the
old tree functions to use integer children with node-pool nodes. Well, are you ready for a
binary sort tree implementing a node-pool (ready or not, we're going there)!
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
