Java Data Structures - Contents
A D V E R T I S E M E N T
Tree related algorithms depend on tree depth being
small (otherwise, they become linked list algorithms ;-). Determining what is the depth of
a tree can sometimes lead to optimizations, and other interesting things like that. How
then, do you determine tree depth?
The task seems rather simple, however, there are a
few tricks involved. Since most trees are defined recursively, our algorithm will also be
recursive. We will need a wrapper method to initialize the maximum depth to zero, and
then, recursively go through the tree determining the depth at each node. We will use a
counter to keep the count of the current depth. Whenever we enter a recursive method, we
will increment the counter, whenever we leave, we will decrement it. If that counter is
greater than the maximum tree depth encountered so far, we will set the maximum tree depth
to the value of that counter.
Once the algorithm completes, the variable holding
the maximum tree depth will hold the max tree depth (sounds logical doesn't it?) Anyway,
talk is cheap, lets go write it!
import java.lang.*;
import java.io.*;
public class pBinTreeDepth{
public pBinTreeDepth left,right;
public Integer data;
private static int tree_depth,curr_depth = 0;
public static int[] numbers = {7,3,11,2,5,9,12,4,6,8,10};
public static pBinTreeDepth add(pBinTreeDepth r,Integer n){
if(r == null){
r = new pBinTreeDepth();
r.left = r.right = null;
r.data = n;
}else if(r.data.compareTo(n) < 0)
r.right = add(r.right,n);
else
r.left = add(r.left,n);
return r;
}
public static void print(pBinTreeDepth r){
if(r != null){
print(r.left);
System.out.print(" "+r.data);
print(r.right);
}
}
public static void _getdepth(pBinTreeDepth r){
if(r != null){
curr_depth++;
if(curr_depth > tree_depth)
tree_depth = curr_depth;
_getdepth(r.left);
_getdepth(r.right);
curr_depth--;
}
}
public static int getdepth(pBinTreeDepth r){
tree_depth = 0;
_getdepth(r);
return tree_depth;
}
public static void main(String[] args){
pBinTreeDepth tree = null;
System.out.print("inserting: ");
for(int i=0;i<numbers.length;i++){
Integer n = new Integer(numbers[i]);
System.out.print(" "+n);
tree = add(tree,n);
}
System.out.print("\ntree: ");
print(tree);
System.out.println("\ndepth: "+getdepth(tree));
System.out.println("done ;-)");
}
}
The code above creates a binary search tree, and
then calls the getdepth(pBinTreeDepth) method to get the tree's depth. This
method in turn calls _getdepth(pBinTreeDepth), which is the actual recursive
procedure. The whole thing is implemented as static methods; this is just to
make quick & simple implementation easier.
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
