The tree package contains our initial code for the BinaryTree datatype.
tree2 implements traversals with the interpreter pattern.
tree3 implements traversals with the visitor pattern.
The interpreter & visitor patterns are an excellent opportunity to check your understanding:
- Are you comfortable with all the syntax used in these patterns? Use the links at the bottom of R04, the Java tutorial, and lectures on exceptions, inheritance, etc.
- Can you explain why these patterns are useful for manipulating recursive datatypes?
- Can you step away from the code and think about ADTs & operations regardless of what pattern is used to implement them? Can you write their specifications?
- Would you be comfortable with a visitor that changed its own state? Could you model it as a state machine?
- Could you write tests for programs that use these structures?