Add to Favorites    Make Home Page 21398 Online  
 Language Categories  
 Our Services  

Java Data Structures - Contents


Node Pool Generic Trees...

A D V E R T I S E M E N T

Search Projects & Source Codes:

    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




Google Groups Subscribe to SourceCodesWorld - Techies Talk
Email:

Free eBook - Interview Questions: Get over 1,000 Interview Questions in an eBook for free when you join JobsAssist. Just click on the button below to join JobsAssist and you will immediately receive the Free eBook with thousands of Interview Questions in an ebook when you join.

 Advertisements  

Google Search

Google

Source Codes World.com is a part of Vyom Network.

Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Interview Questions | Jobs, Discussions | Placement Papers | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | Arabic, French, German | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Software Testing | Google Logo Maker | Freshers Jobs

Sitemap | Privacy Policy | Terms and Conditions
Copyright ©2003-2018 SourceCodesWorld.com, All Rights Reserved.
Page URL: http://www.sourcecodesworld.com/articles/java/java-data-structures/Node_Pool_Generic_Trees.asp


Download Yahoo Messenger | Placement Papers | Free SMS | C Interview Questions | C++ Interview Questions | Quick2Host Review