| A binary tree node.
Structure.
BTreeNodes and the BinaryTree enumeration are designed to
allow for binary trees to be treated as though they
had left-right children or next-child children.
Relevant methods for each are visible;
internally,
left is treated as being equivalent to next and
right is treated as being equivalent to child.
Visibility.
A CLOSED node is visible to enumeration but it's
children aren't.
A node that is OPEN is fully visible to BinaryTree enumeration
and the node's children are accessible,
though they themselves may not be visible.
LEFT/NEXT/RIGHT/CHILD implies the node itself is OPEN.
BTreeNodes have a sense of their visibility in enumeration.
If the node is LEFTVISIBLE or NEXTVISIBLE,
enumeration will attempt to traverse only it's
left or next child if they are visible.
If the node is RIGHTVISIBLE or CHILDVISIBLE,
enumeration will attempt to traverse only it's
right or child child if they are visible.
The default visibility is OPEN.
Visibility restrictions can be circumvented with the getAll methods.
Terminal Policy.
Terminal policy affects whether a node accepts expansion
and in what way it accepts expansion.
In other words, what kind of terminal it is.
The policy values are the same as the visibility values
and are used similarly.
The default terminal policy is OPEN, meaning that either
a right or left branch can be created.
LEFTVISIBLE and NEXTVISIBLE allow only left (next) branches to
be created.
RIGHTVISIBLE and CHILDVISIBLE allow only right (child) branches to
be created.
CLOSED means no branches can be created.
Currently, rejection based on terminal policy is silent.
Depth.
BTreeNodes maintain a sense of their "depth".
Both binary and unary depth are kept.
Binary depth is the depth a node is in a left-right tree,
unary depth is the depth a node is in a next-child tree,
the difference being that the next reference doesn't cause
depth to increment.
Depth 0 nodes are root nodes.
Management.
All alterations to the structure of a binary tree are expected
to take place through the Enumeration class.
While this class is public (compare with HashtableNode
in the JDK util.Hashtable class) enough to be viewed and referenced,
methods that alter the parent, left and right are restricted to the
BinaryTree enumeration class to ensure the integrity of the
enumeration.
Open Issues
- Certain advanced operations (e.g., the deleting and inserting
operations required by QueryNode) will require methods
that are less or differently deterred by visibility.
- Need to support clone() (done) plus Enumeration/Dictionary
operations like: contains(), containsKey(), get() (done),
keys(). Some maybe in the Enumeration class.
- Need toString() and toStringList().
- Adding children should verify that the tree doesn't loop
back on itself, i.e. no inclusive descendant of a node being
added should point to an inclusive ancestor of the node it is
being added to. If access is restricted to the enumerator,
we can assume this is not necessary, assuming the creator
of the enumerator is not a pinhead.
- There are times when it would be useful for the BTreeNode
to point at it's BinaryTree. Dicey though; then
it'd need to be maintained and everything would
become just slightly more complicated. It would
all be managed w/in the util package though, so
consistency/correctness would be doable.
- getNodeByKey() and getNodeByValue() ignore the enumeration
order, are used by BinaryTree and return only the first
possible value.
Very, very bad.
|
