Recursion III, using Java


Here’s a Java example of the classic recursion/tree/web traversal. Note that this uses an array of other nodes, not just Left and Right, so you can make n-link webs as well as proper trees using this example.

The method interMed() is used to avoid having to make the data structures static- there is much I have yet to learn about Java! But I can manage this, and that feels pretty good!

/*
recurse.java

Recursive tree/web traversal, in Java. No explicit pointers, so I state that
the array of pointers to nodes is an array of nodes, and treat it as such.
Is it really pointers if I believe it is but can't see them? Its like String
Theory...

Original 11:58am 4/21 Bill4

*/

import java.util.ArrayList;

public class recurse {

public class node { String name; ArrayList kids; };
public class leveledName { String name; int level; };

ArrayList nLs = new ArrayList ();

public void recur ( node n, int level ) {

// System.out.println( "recur " + n + " level " + level );
leveledName lN = new leveledName();
lN.name = n.name;
lN.level= level;
nLs.add( lN );

for ( int i = 0; i < n.kids.size(); i++ ) { // better way to do this?

recur( n.kids.get(i), level + 1 );

} // for int i...

} // recur function

public void interMed() {

node Q = new node(); Q.name = "Q";
Q.kids = new ArrayList ();
// System.out.println( Q );

node S = new node(); S.name = "S";
S.kids = new ArrayList ();
// System.out.println( S );

node T = new node(); T.name = "T";
T.kids = new ArrayList ();
// System.out.println( T );

node N = new node(); N.name = "N";
N.kids = new ArrayList (); N.kids.add(Q);
// System.out.println( N );

node P = new node(); P.name = "P";
P.kids = new ArrayList (); P.kids.add(S); P.kids.add(T);
// System.out.println( P );

node M = new node(); M.name="M";
M.kids = new ArrayList (); M.kids.add(N); M.kids.add(P);
// System.out.println( M );

recur( M, 0 );

int maxLevel = 0;
for ( int i = 0; i maxLevel) {
maxLevel = ((nLs.get(i)).level );
} // if ...
} // for ...

for (int j = maxLevel; j > -1; j-- ) {
// System.out.println( "j " + j );
for ( int i = 0; i < nLs.size(); i++ ) {
// System.out.println( "j " + j + " i " + i );
if ( j == (nLs.get(i)).level ) {
System.out.printf( "%s %d \n", (nLs.get(i)).name,
(nLs.get(i)).level );
}
} // for i...
} // for j...

} // fn interMed

public static void main ( String args[] ) {

recurse r = new recurse();
r.interMed();

} // main

} // class recurse

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s