CIT 594 Tree Traversals and Searches
Spring 2003, David Matuszek

I've written some (pretty simple) methods to demonstrate tree traversals and searches.

There are three classes:

Tree
This is an absolutely minimal implementation of trees, providing only the methods necessary for the rest of the program. Every Tree has a String value and a Vector children, which are available to the other classes; a constructor that takes a value as an argument; and methods to create and add a single node (given its value), and to add a subtree.

Queue
An inefficient implementation of a queue (using a Vector), with a default constructor and methods add(Object), get(), addAll(Collection), and isEmpty().

TreeTraversals
This class builds a (hardwired) tree, then calls the following methods to do something with it:

static void preorderPrint(Tree node)
Prints the node values on a single line, in preorder.

static void preorderPrint(Tree node, String indent)
Prints the node values on multiple lines, indented to show structure, in preorder.

static void postorderPrint(Tree node)
Prints the node values on a single line, in postorder.

static void postorderPrint(Tree node, String indent)
Prints the node values on multiple lines, indented to show structure, in preorder. I can decipher the result, but find it very confusing.

static boolean dfs(Tree root)
Searches the tree in depth-first order for a (predefined) goal node.

static boolean recursiveDfs(Tree node)
Searches the tree in depth-first order for a (predefined) goal node, and prints the resultant path (in reverse order).

static boolean bfs(Tree root)
Searches the tree in breadth-first order for a (predefined) goal node.

The only interesting class is available as TreeTraversals.java. (There are also minimal Tree.java and Queue.java classes.) The whole thing, as a BlueJ package, is available as a zip file.