Java Data Structures - Contents
A D V E R T I S E M E N T
The next major set of data structures belongs to
what's called Trees. They are called that, because if you try to visualize the structure,
it kind of looks like a tree (root, branches, and leafs). Trees are node based data
structures, meaning that they're made out of small parts called nodes. You already know
what a node is, and used one to build a linked list. Tree Nodes have two or more child
nodes; unlike our list node, which only had one child.
Trees are named by the number of children their
nodes have. For example, if a tree node has two children, it is called a binary tree. If
it has three children, it is called tertiary tree. If it has four children, it is called a
quad tree, and so on. Fortunately, to simplify things, we only need binary trees. With
binary trees, we can simulate any tree; so the need for other types of trees only becomes
a matter of simplicity for visualization.
Since we'll be working with binary trees, lets write
a binary tree node. It's not going to be much different from our pOneChildNode
class; actually, it's going to be quite the same, only added support for one more pointer.
The source for the follows:
public class pTwoChildNode{
protected Object data;
protected pTwoChildNode left,right;
public pTwoChildNode(){
data = null;
left = right = null;
}
public pTwoChildNode(Object d){
data = d;
left = right = null;
}
public void setLeft(pTwoChildNode l){
left = l;
}
public void setRight(pTwoChildNode r){
right = r;
}
public void setData(Object d){
data = d;
}
public pTwoChildNode getLeft(){
return left;
}
public pTwoChildNode getRight(){
return right;
}
public Object getData(){
return data;
}
public String toString(){
return ""+data;
}
}
This node is so much similar to the previous node we
did, that I'm not even going to cover this one. (I assume you'll figure it out by simply
looking at the source) The children of the node are named left and right;
these will be the left branch of the node and a right branch. If a node has no children,
it is called a leaf node. If a node has no parent (it's the father of every node), it is
called the root of the tree. This weird terminology comes from the tree analogy, and from
the family tree analogy.
Some implementations of the tree node, might also
have a back pointer to the parent node, but for what we'll be doing with the nodes, it's
not necessary. The next section will talk about a generic binary tree which will be later
used to create something cool.
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
