Java Data Structures - Contents
A D V E R T I S E M E N T
I've talked about tree traversals before in this
document, but lets review what I've said. Tree's are created for the sole purpose of
traversing them. There are two major traversal algorithms, the depth-first, and
breadth-first.
So far, we've only looked at depth-first.
Pre-traversal, in-traversal, and post-traversal are subsets of depth-first traversals. The
reason it's named depth-first, is because we eventually end up going to the deepest node
inside the tree, while still having unseen nodes closer to the root (it's hard to explain,
and even harder to understand). Tracing a traversal surely helps; and you can trace that
traversal from the previous section (it's only ten numbers!).
The other type of traversal is more intuitive; more
"human like." Breadth-first traversal goes through the tree top to bottom, left
to right. Lets say you were given a tree to read (sorry, don't have a non-copyrighted
picture I can include), you'd surely read it top to bottom, left to right (just like a
page of text, or something).
Think of a way you visualize a tree... With the root
node on top, and all the rest extending downward. What Breadth-First allows us to
do is to trace the tree from top to bottom as you see it. It will visit each node at a
given tree depth, before moving onto the the next depth.
A lot of the algorithms are centered around Breadth-First
method. Like the search tree for a Chess game. In chess, the tree can be very deep,
so, doing a Depth-First traversal (search) would be costly, if not impossible. With
Breadth-First as applied in Chess, the program only looks at several moves
ahead, without looking too many moves ahead.
The Breadth-First traversal is usually from left to
right, but that's usually personal preference. Because the standard consul does not
allow graphics, the output may be hard to correlate to the actual tree, but I will show
how it's done.
As with previous examples, I will provide some
modified source that will show you how it's done. An extended pBinarySearchTree
is shown below:
import pTwoChildNode;
import pBinarySearchTree;
import pEasyQueue;
public class pBreadthFirstTraversal extends pBinarySearchTree{
public void breadth_first(){
pEasyQueue q = new pEasyQueue();
pTwoChildNode tmp;
q.insert(getRoot());
while(!q.isEmpty()){
tmp = (pTwoChildNode)q.remove();
if(tmp.getLeft() != null)
q.insert(tmp.getLeft());
if(tmp.getRight() != null)
q.insert(tmp.getRight());
System.out.print(tmp.getData()+" ");
}
}
}
As you can see, the class is pretty simple (only one
function). In this demo, we're also using pEasyQueue, developed earlier in
this document. Since breadth first traversal is not like depth first, we can't use
recursion, or stack based methods, we need a queue. Any recursive method can be easily
simulated using a stack, not so with breadth first, here, we definitely need a queue.
As you can see, we start by first inserting the root
node on to the queue, and loop while the queue is not isEmpty(). If we have a
left node in the node being examined, we insert it in to the queue, etc. (same goes for
the right node). Eventually, the nodes inserted in to the queue, get removed, and
subsequently, have their left children examined. The process continues until we've
traversed the entire tree, from top to bottom, left to right order.
Now, lets test it. The code below is pretty much the
same code used to test the tree, with one minor addition; the one to test the
breadth-first traversal!
import java.io.*;
import pInteger;
import pBinarySearchTree;
class pBreadthFirstTraversalTest{
public static void main(String[] args){
pBreadthFirstTraversal tree = new pBreadthFirstTraversal();
pInteger n;
int i;
System.out.println("Numbers inserted:");
for(i=0;i<10;i++){
tree.insert(n=new pInteger((int)(Math.random()*1000)));
System.out.print(n+" ");
}
System.out.println("\nPre-order:");
tree.print(1);
System.out.println("\nIn-order:");
tree.print();
System.out.println("\nPost-order:");
tree.print(3);
System.out.println("\nBreadth-First:");
tree.breadth_first();
}
}
As you can see, nothing too hard. Next, goes the
output of the above program, and you and I will have to spend some time on the output.
Numbers inserted:
890 474 296 425 433 555 42 286 724 88
Pre-order:
890 474 296 42 286 88 425 433 555 724
In-order:
42 88 286 296 425 433 474 555 724 890
Post-order:
88 286 42 433 425 296 724 555 474 890
Breadth-First:
890 474 296 555 42 425 724 286 433 88
Looking at the output in this format is very
abstract and is not very intuitive. Lets just say we have some sort of a tree, containing
these numbers above. We were looking at the root node. Now, looking at the output of this
program, can you guess what the root node is? Well, it's the first number in
breadth-first: 890. The left child of the root is: 474.
Basically, the tree looks like:
|--[890]
|
|--[474]--|
| |
|--[296]--| [555]--|
| | |
[ 42]--| [425]--| [724]
| |
|--[286] [433]
|
[ 88]
As is evident from this picture, I'm a terrible
ASCII artist! (If it's screwed up, sorry).
What you can also see is that if you read the tree
form left to right, top to bottom, you end up with the breadth first traversal. Actually,
this is a good opportunity for you to go over all traversals, and see how they do it, and
if they make sense.
There are many variations to these traversals (and
I'll show a few in subsequent sections), for now, however, try to understand these four
basic ones.
Well, see you again in the next section, where we
examine some ways you can speed up your code and take a look at JDK 1.2 features, which
will simplify our life a LOT!
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
