Consider the following implementation of a tree node, which can be used to build a tree (a fundamental data structure in Computer Science):
Each TreeNode can store an arbitrary object, which is called a key.
The type of the key is passed to TreeNode as a generic parameter E. Note
that the TreeNode class allows the key and the children to be null.
Such an implementation of TreeNode is quite flexible as it allows each node in a tree
to have an arbitrary number of children, as determined at the time of the node's creation.
The problem, however, is that such an implementation might be quite inefficient. In particular,
each leaf node of the tree will contain an empty children array.
If there are many leaf nodes in a tree, the memory
overhead introduced by the empty children array can become quite significant and
limit the applicability of the TreeNode data structure.
Furthermore, binary nodes (i.e., nodes with two children) are a
quite common type of node. Since binary nodes only require two
references to child nodes, storing an array (for only two references)
becomes a significant overhead.
In order to correct this problem, create a set of classes/interfaces that allow for an efficient
representation of leaf and binary nodes. In particular, leaf nodes should not contain the children
array, and binary nodes should contain just two pointers instead of a pointer to the children
array. Your classes should still allow a tree to contain nodes with different numbers of children. For
example, a node with three children should be able to have a binary node as its first child.
See the end for a hint on how to structure this.
Write a demonstration program that builds a tree with a key type of your choice, containing a variety of types of nodes.
Extension: Extend your classes with an implementation of toString().
The toString() method should represent a node as: the string representation of the key, an opening `(',
comma-separated string representations of each child, followed by a closing ')'.
Can you manage to do this by implementing toString() in a single place? See the end
for a hint.
Extend your demonstration to display the tree that you have built.
Hints: Think about what field of the original TreeNode class
is common to all tree nodes, whether they are leaves, binary nodes, or other nodes. It would make sense to place this field
in an abstract superclass, from which the specific tree node classes will derive. You may wish to go further and write an interface
for tree nodes, which your abstract class can implement.
Hint for extension: You should be able to implement toString() in your abstract tree node class, using the
abstract methods getChild and getNumberOfChildren to navigate the structure of a tree node without knowing its
actual type.