(C) Samuel Marateck, 2004
Given the class
class Node
{ Object data ;
Node left;
Node right;
}
These are the steps you follow to write a recursive tree method.
1.Write the heading, e.g., public void test( Node t)
2 If a general traversal is needed in which all the nodes are visited,
type the if statement as if( t != null). In addition, if you want to
visit all the nodes except the leaves, type: if( ! isLeaf(t) ),
where
private boolean isLeaf( Node t)
{ return t.left == null && t.right == null;
}
You must make sure, however, when you use isLeaf the value of t is not null;
otherwise you will dereference the null pointer. For instance, if your method
is traversing a tree that is not full, e.g.,
1
/ \
2 3
/ \ /
4 5 6
and your method is:
private boolean inOrder( Node t)
{
if( !isLeaf(t) )
{
inOrder(t.left);
System.out.println(t);
inOrder(t.right);
}
}
when the execution backtracks from node 6 to node 3, executes
System.out.println(t), and then executes inOrder(t.right), the value of t.right
will be null. Then when isLeaf(t) is executed, t will be null and the Java
Virtual Machine will throw a nullPointerException. So in general, you cannot
substitute if( ! isLeaf(t) ) for if( t != null).
We now see why your method should be written as:
private void inOrder( Node t)
{
if( t != null )
{
inOrder(t.left);
System.out.println(t);
inOrder(t.right);
}
}
3. Depending on whether a preorder, inorder or postorder traversal, write
test(t.left), test(t.right) and place what should be done at the node either
before, in the middle, or after the recursive calls, respectively.
4. End the if statement.
5. If you want to test a value at a node and have that value passed
back to the calling program, write the heading as:
public int test(Node t) and finish the method with a return.
6. If you write a recursive tree that returns a value,
the left and right branching should be done in an assignment statement, e.g.,
height = 1 + max( height(t.left), height(t.right) )
The entire method is
private int height(Node t)
{
if(t == null)
{
return -1;
}
else
{
int height = 1 + max( height(t.left), height(t.right) );
return height;
}
}
Test this for a tree that contains just the root.
root x
/ \
/ \
null null
the height = 1 + max(null, null); or height = 1 + max(-1, -1); or
height = 0 as it should.
7. Let's now look at the method to count the leaves in a tree.
private int countLeaves(Node t)
{
if(t != null)
{
if(isLeaf(t))
{
return 1;
}
else
return countLeaves(t.left) +countLeaves( t.right);
}
return 0;
}
If the node is a leaf return 1; else recurse to the left and count the leaves
and recurse to the right and count the leaves and add the results. Does it
make sense to return 0 if the node is null? If the tree consists of only a null
pointer, then there are no leaves, so the method should return 0.