Java Data Structures - Contents
A D V E R T I S E M E N T
Binary Trees are quite complex, and most of the
time, we'd be writing a unique implementation for every specific program. One thing that
almost never changes though is the general layout of a binary tree. We will first
implement that general layout as an abstract class (a class that can't be used directly),
and later write another class which extends our layout class.
Trees have many different algorithms associated with
them. The most basic ones are the traversal algorithms. Traversals algorithms are
different ways of going through the tree (the order in which you look at it's values). For
example, an in-order traversal first looks at the left child, then the data, and then the
right child. A pre-order traversal, first looks at the data, then the left child, and then
the right; and lastly, the post-order traversal looks at the left child, then right child,
and only then data. Different traversal types mean different things for different
algorithms and different trees. For example, if it's binary search tree (I'll show how to
do one later), then the in-order traversal will print elements in a sorted order.
Well, lets not just talk about the beauties of
trees, and start writing one! The code that follows creates an abstract Generic Binary
Tree.
import pTwoChildNode;
public abstract class pGenericBinaryTree{
private pTwoChildNode root;
protected pTwoChildNode getRoot(){
return root;
}
protected void setRoot(pTwoChildNode r){
root = r;
}
public pGenericBinaryTree(){
setRoot(null);
}
public pGenericBinaryTree(Object o){
setRoot(new pTwoChildNode(o));
}
public boolean isEmpty(){
return getRoot() == null;
}
public Object getData(){
if(!isEmpty())
return getRoot().getData();
return null;
}
public pTwoChildNode getLeft(){
if(!isEmpty())
return getRoot().getLeft();
return null;
}
public pTwoChildNode getRight(){
if(!isEmpty())
return getRoot().getRight();
return null;
}
public void setData(Object o){
if(!isEmpty())
getRoot().setData(o);
}
public void insertLeft(pTwoChildNode p,Object o){
if((p != null) && (p.getLeft() == null))
p.setLeft(new pTwoChildNode(o));
}
public void insertRight(pTwoChildNode p,Object o){
if((p != null) && (p.getRight() == null))
p.setRight(new pTwoChildNode(o));
}
public void print(int mode){
if(mode == 1) pretrav();
else if(mode == 2) intrav();
else if(mode == 3) postrav();
}
public void pretrav(){
pretrav(getRoot());
}
protected void pretrav(pTwoChildNode p){
if(p == null)
return;
System.out.print(p.getData()+" ");
pretrav(p.getLeft());
pretrav(p.getRight());
}
public void intrav(){
intrav(getRoot());
}
protected void intrav(pTwoChildNode p){
if(p == null)
return;
intrav(p.getLeft());
System.out.print(p.getData()+" ");
intrav(p.getRight());
}
public void postrav(){
postrav(getRoot());
}
protected void postrav(pTwoChildNode p){
if(p == null)
return;
postrav(p.getLeft());
postrav(p.getRight());
System.out.print(p.getData()+" ");
}
}
Now, lets go over it. The pGenericBinaryTree
is a fairly large class, with a fair amount of methods. Lets start with the one and only
data member, the root! In this abstract class, root
is a private head of the entire tree. Actually, all we need is root
to access anything (and that's how you'd implement it in other languages). Since we'd like
to have access to root from other places though (from derived classes, but
not from the "outside," we've also added two methods, named getRoot(),
and setRoot() which get and set the value of root respectively.
We have two constructors, one with no arguments
(which only sets root to null), and another with one argument (the first
element to be inserted on to the tree). Then we have a standard isEmpty()
method to find out if the tree is empty. You'll also notice that implementing a counter
for the number of elements inside the tree is not a hard thing to do (very similar to the
way we did it in a linked list).
The getData() method returns the data
of the root node. This may not be particularly useful to us right now, but
may be needed in some derived class (so, we stick it in there just for convenience).
Throughout data structures, and mostly entire programming world, you'll find that certain
things are done solely for convenience. Other "convenient" methods are getLeft(),
getRight() and setData().
The two methods we'll be using later (for something
useful), are: insertLeft(pTwoChildNode,Object), and insertRight(pTwoChildNode,Object).
These provide a nice way to quickly insert something into the left child (sub-tree) of the
given node.
The rest are just print methods. The trick about
trees are that they can be traversed in many different ways, and these print methods print
out the whole tree, in different traversals. All of these are useful, depending on what
you're doing, and what type of tree you have. Sometimes, some of them make absolutely no
sense, depending on what you're doing.
Printing methods are recursive; a lot of the tree
manipulation functions are recursive, since they're described so naturally in recursive
structures. A recursive function is a function that calls itself (kind of like pretrav(),
intrav(), and postrav() does).
Go over the source, make sure you understand what
each function is doing (not a hard task). It's not important for you to understand why we
need all these functions at this point (for now, we "just" need them); you'll
understand why we need some of them in the next few sections, when we extend
this class to create a really cool sorting engine.
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
