As in COMP 210, we can define binary trees of the form
AList, or an mutable version, akin to
LRStruct. In class, we introduced the mutable version
and called it
BiTree.
Be aware of a confusing overlap in terminology. A tree is a collection of nodes, including the root node (or simply "root"), the interior nodes, and the leaf nodes (or simply "leaves"). Also, when using the state pattern, we have sometimes used the term node to refer to the class with a state field. So, for mutable lists, each tree-node really consists of a tree-classed object and a state-pattern-node-classed object. Confused yet?
By default, a binary tree is not necessarily balanced. I.e., all the paths from the root to leaves may be of arbitrary length.
As in COMP 210, we can consider a special kind of binary tree, called
the binary search tree. It is organized such that, for each node,
all the nodes to the left have lower-ordered data, and all the nodes
to the right have high-ordered data. Again, binary search trees
can be immutable or mutable. In class, we introduced the mutable
version and called it BSTree.
Also as in COMP 210, there are many other variants of trees. One that we won't use in COMP 212 is worth at least a mention. If we want a tree with arbitrary branching, each tree node can have a list of child trees. Thus, we could have a tree class that also used a list class. If we chose mutable versions of each, we get two uses of the state pattern, and thus two distinct state-pattern-node-classes. Exercise: List the fields needed for these two classes in order to see that they are indeed different, and thus can't be combined.
Write the following visitors on binary trees. (You probably won't have time for all of them.) Make any helper visitors be inner classes.
LeftmostTreeFinder returns the leftmost
non-empty subtree of the host (if any). If the host is
empty, it returns the empty tree.
InOrderEnumeration, which also implements
Enumeration.
As a reminder(?), an in-order enumeration of a binary tree first enumerates everything to the left, then enumerates the current node, then enumerates everything to the right.
The only real "trick" is for your
enumeration to remember what it has left to enumerate.
E.g., you want to first enumerate the left branch, but
how do you remember to enumerate the right branch when you're
done with that?
Hint: Let InorderEnumeration
have a local stack field.
PostOrderEnumeration, which also implements
Enumeration.
As a reminder(?), a post-order enumeration of a binary tree first enumerates everything to the left, then everything to the right, then the current node.
Note that if you had a tree representing arithmetic expressions, a post-order listing of its contents would be a post-fix (RPN) expression.
LeafCounter returns the count of the number
of leaves in the tree.
In this implementation, a leaf is a tree with empty left
and right subtrees.