Class 49: Traversing Trees

Held Monday, November 29, 1999

Overview

Today, we conclude our discussion on trees by considering the ways in which one might iterate the elements of a tree. We may also consider some alternate designs of trees.

Notes

• Are there any questions on exam 3?
  • In A:
    • You should design, document, and implement a reasonable comparison metric for lists.
    • You are not allowed to change the iterated list interface.
    • You should not use the Node class explicitly.
• Remember that the due date is a week from today.
  • Because of the delayed deadline, we probably won't discuss the exam in class.
  • If you expect to need an extension, talk to me immediately after class today, and have a very good reason.
  • I'll distribute the final after I grade the exam (I hope to distribute it a week from Wednesday).

Contents

• Introduction: Coding the Conversion from Expression Tree to String
• Reverse Polish Notation
• Iterating Trees, Revisited
• Iterators, Formalized
  • Iterators in Java
  • Writing Our Own

Handouts

• Don't forget that the current versions of the project files can be found at http://www.math.grin.edu/~rebelsky/Courses/CS152/99F/Project/22November1999

Summary

• Reverse polish notation
• How do you visit, iterate, or list the elements of the tree?
• Preorder vs. postorder
• Depth-first vs. breadth first
• Iterators in Java

Introduction: Coding the Conversion from Expression Tree to String

• Of course, we want to do more with trees than build them. Often, we want to iterate their elements (look at them one by one).
  • For example, we might want to convert an expression tree back into an expression, as we did in the last class.
• We came up with a fairly simple and clear algorithm

  If the tree contains only a number,
    Return the string that corresponds to that number
  Otherwise
    Convert the left subtree to a string
    Convert the right subtree to a string
    Return left paren, converted left subtree, operator,
      converted right subtree, right paren
  

• But how do we code that given our current implementation of trees?

Reverse Polish Notation

• We might also want to convert the tree into a different form, one commonly used on older HP calculators (and some newer calculators of other brands).
• In reverse Polish notation (RPN), you write the operator after the operands, rather than before.
  • (3+4)*5 could be written 3 4 + 5 *
  • 3+(4*5) could be written 3 4 5 * +
• What are the advantages of reverse Polish notation?
  • It's unambiguous
  • It's easy to compute using a stack
• The stack-based algorithm

  Read the next thing
  If the next thing is a number
    Push it on the stack
  If the next thing is an operator
    Pop its operands
    Apply the operator
    Push the result on the stack
  

• Is there a way to convert an expression tree to RPN?

Iterating Trees, Revisited

• Is there a natural way to list all the elements in a tree?
  • We saw two for expressions.
  • It turns out that there are many.
• If you recall our consideration of puzzles, we built trees to represent all possible states of the puzzles
  • The children of a ``state'' are the different states you can reach after making a single move from that state.
• We then wanted to examine the states in the tree to see if any were solved.
• There are two basic strategies we considered:
  • We looked across each level before moving on to the next level.
  • We looked down as deeply as possible before moving accross the current level.
• These same strategies can be employed in any tree.
  • The first is breadth-first traversal.
  • The second is depth-first traversal.
• Yet there are other considerations. Do you visit a node before or after you visit its children (or between, as in a binary tree)?
  • In prefix traveral, you visit the node first (like Polish notation).
  • In suffix traversal, you visit the node last (like reverse Polish notation).
  • In infix traversal, you visit the node between its subtrees (like traditional arithmetic notation ).
• If a node has multiple children (as it typically does), do you visit them
  • Left-to-right
  • Right-to-left
• We have two typical ways of traversing binary expression trees:
  • We traverse them in left-to-right, depth-first, infix order when "printing" them for the standard output. (We do have to parenthesize.)
  • We traverse them in left-to-right, depth-first, postfix order to get ``reverse polish notation''.
• Why might you want other orders for other kinds of trees?

Iterators, Formalized

• We've seen that it's possible to iterate a tree by writing an algorithm that uses the tree appropriately.
  • However, that algorithm left out many details, and we needed to work hard to deal with those details.
• What if we want to generalize the idea of iteration, so that we can simply present appropriate methods?
• That is, what are the basic operations that we might use to iterate any collection, whether that collection is in a list, tree, or other data structure?

Iterators in Java

• In Java, iterators are often separate objects that you build from collections.
• The use of objects fits within the object-oriented paradigm.
• It's also useful to be able to iterate the collection "simultaneously", as it were.
• Java presents iterators as interfaces. Consider Java's java.util.Enumeration interface.
• If you look at Java's java.util.Hashtable class, you'll note that there are a few methods that return enumerations.

Writing Our Own

• When you write your own iterators, you typically take advantage of some knowledge of the internal structure of the thing you're iterating.
• How might we write our own iterators for trees?
• One solution: Shove everything in the tree into a list and then iterate the list.
• Another solution: Keep careful track of where you are in the tree and where you've been.