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