Add to Favorites    Make Home Page 2141 Online
 Language Categories
 Source Codes Home Project Ideas New! Interview Questions FAQs Home ASP Home ASP Source Codes ASP Script Directory New! ASP .Net Script Directory New! ASP Interview Questions ASP FAQs ASP How Tos C Home C Source Codes C Script Directory New! C Interview Questions C FAQs C How Tos C++ Home C++ Source Codes C++ Script Directory New! C++ Interview Questions C++ FAQs C++ How Tos Java Home Java Source Codes Java Directory New! Java Interview Questions Java FAQs Java How Tos JavaScript Home JavaScript Directory New! JavaScript Source Codes JavaScript FAQs JavaScript How Tos COBOL Home COBOL Source Codes COBOL FAQs COBOL How Tos Pascal Home Pascal Source Codes Pascal FAQs Pascal How Tos PHP Script Directory New! Python Script Directory New! Perl & CGI Script Directory New! Flash Script Directory New! CFML Script Directory New! Remotely Hosted Scripts New! Tools & Utilities Directory New! XML Script Directory New! Best Programmers Amit Mathur Vishal Bhardwaj Deepesh Jain Vyom NetWork
 Our Services

Java Data Structures - Contents

## Generic Tree...

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

Search Projects & Source Codes:

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.

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

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.