CS151 Lab 10:   Iterating the Night Away

Due 11:59 PM, Sunday April 22, 2001

In this lab we will explore how we can make a binary tree appear as a linear entity.     This process is called "iterating".   Iterators are different than a lot of what we have been doing since the "order" of the elements in a binary tree extrinsic to the tree, that is, it is dependent on an external insertion algorithm to determine how new elements are added the tree.

Iterators are used when the elements of a tree need to be processed in a very specific order, not necessarily directly related to their position in the tree.   An example is the very important usage of binary trees in compiler design where the code written in a particular programming language is parsed into an "abstract syntax tree".   This abstact syntax tree is an equivalent representation of the code where the parenthesis have been eliminated and variables stored in leaf nodes, while the interior nodes contain the operators the user specified for use on those variables.  

In this lab we will use the BSTInsertAlgo and other Binary Search Tree capabilities developed in class to provide a consistent way of inserting and removing nodes from the tree

Different Types of Iterators (non-exhaustive list)

Note:  In all the iterations described below, "left" can be interchanged with "right", so the iteration progresses in the opposite horizontal direction across the tree, with no loss of generality.

The following descriptions will give iteration results for the following two examples:

An example of a binary tree:

A
B		C
	D	E	F

An example of an abstract syntax tree with operators and variables:

+
-		*
W	X	Y	Z

Depth first/Pre-fix order :

The elements of the tree are retrieved starting at the top element and progressing node by node down the left-most side as far it will go.   Then the nearest right side path is chosen and that sub-tree is traversed in the same maximal left-side depth algorithm.   For an abstract syntax tree, the data will be retrieved in an order that always places the operator just before the data it is to work upon ("pre-fix" or "Polish" notation).

Results   A B D C E F   and + - W X * Y Z

Breadth first

The elements of the tree are retrieved starting at the top element and progressing node by node by retrieving the node's root data across all the siblings first.   Then the children's root data is retrieved  from left to right. 

Results: A B C D E F  and + - * W X Y Z 

In order/in-fix order :

This iteration starts at the bottom left corner of the tree (the "smallest" element of a BST) and retrieves its root data.   Then the parent's root data is retrieved and then finally the parent's right child's root data (the left node's sibling's data) is retrieved.   The process is recursively repeated with the grandparent.   For a BST, this will cause the elements to be retrieved in their logical order ("in order").   For an abstract syntax tree, the data will retrieved in the "normal" mathematical order that puts the operator in-between ("in-fix") the data it is to operate upon.

Results:  B D A E C F and W - X + Y * Z

 Post-fix order :

This iteration starts at the bottom left corner of the tree (the "smallest" element of a BST) and retrieves its root data.   Then the parent's right child's root data (the left node's sibling's data) is retrieved and then finally the parent's root data is retrieved.   The process is repeated recursively with the grandparent.   For an abstract syntax tree, the data will be retrieved in an order that always places the operator just after  the data it is supposed to operate upon ("post-fix" or "reverse Polish" notation).    Users of HP calculators will recognize this as how their stack-based architectures work.

Results: D B E F C A and W X - Y Z * +

The Use of a Stack and Queues as a Pending-State Storage Devices

Recursion is a wonderful thing, but it has one serious drawback:  it can't be stopped in the middle and restarted some arbitrary time later (single threading assumed here).    Contrast this to a for-loop that could be stopped in the middle, save the main counter value, and then be restarted at the saved counter value at any time later.

The problem is all those pending operations in a recursive process.   The problem manifests itself here because we'd like to do a recursive process to iterate through the list, but unless we want to pre-process the entire tree by saving every element in its proper order in a list, we cannot restart the recursion at the place it left off every time nextElement() is called. 

We can cheat a little here and not try to save the entire state of the recursion.   We need only find a way of storing all the pending nodes that we have recurred through and are going to return to and continue their processing at a later time.   If we were retrieving data grom the leaf nodes before the parents, this storage mechanism would save each node as we recurred down to the next level, seeking the leaf node.   The leaf node's data would be returned with the subsquent nextElement() call.    Having done that, the iterator would pull the nearest parent node from the storage mechanism as the next node to process.   This is "First-In, Last-Out" (FILO) behavior and maps perfectly over to a Stack implementation.   On the other hand, if the parents are all retrieved before the children ever are, a "First-In, First-Out" behavior, then a Queue is more warranted. 

Note that this method is far superior to pre-processing the whole tree because only a temporary storage of size O(log(n)) is needed instead of the O(n) size needed if the tree were completely pre-processed. 

So, all we have to do is to figure out clever ways to store nodes of the tree in a Stack or Queue so that we can retrieve them when they are needed.   Sure, no problem....uh, huh.....

Doing It Order

Complete this lab in this order:

1. Create a test program for the BST, Iterators and File I/O with a menu bar (see below).   Just make sure that your menu items work at this point.  We'll add more stuff to the test program below.
2. Download the BSTree package code and get it working.  
3. Add factory methods to the Dictionary class to create different types of iterators.    Why do we do this?   Think about the encapsulation issues.
4. Implement the iterators.   Save the pre-fix order iterator for last.   Focus on understanding why the iteration algorithms work.
5. Without connecting it to the BST or iterators, get the code to save/retrieve an object to/from a file working.
6. In combination with an iterator, save the entire tree to the disk and then retrieve it.    Is the tree the same tree when you read it back in?   Does it depend on which iterator you used?   In particular, check the difference between using an in-order vs. breadth-first iterator.

Adding MenuBars in JBuilder

1.  When creating a new Application, click on "Next" in the wizard to get to the options for creating the JFrame.
2. Select "Generate menu bar".
3. Click on "Finish".
4. After the application is built by the wizard,  select the frame class and go to the GUI design tab.
5. Go to the class browser window (the one on the lower left) and right click on the "Menu" folder.
6. Select "Activate Designer".     The menu bar should now appear in the GUI designer.  
7. Sub-menus can be pulled down and menu items inserted and deleted.  (Right click for options).
8. To attach an event listener to a menu item, select it as you would any other object and attach a listener as normal.
9. Switching back and forth between the "Menu" folder and the "UI" folder will cause the  GUI designer to switch what it displays.   Double click the desired folder to force the change if iit doesn't occur fast enough.   

Tip:  Clearing the JPanel

All containers have a "removeAll()" method that removes all the sub-Components they contain.