Purposes:

• To give you some experience with general trees
• To give you more experience with writing ADTs
• To give you more practice with recursion
• To create a class you can use in later assignments

General Idea:

Write a general-purpose API for trees.

Details:

Constructors:

public Tree(Object obj)

Constructs a Tree consisting of a single tree node, with obj as its value.

public Tree (Object obj, Tree child)

Constructs a Tree consisting of a new tree node with obj as its value, and child as its single child.

Accessors:

public boolean isBinaryTree( )

Returns true if no node in this tree has more than two children.

public boolean isLeaf( )

Returns true if this tree node has no children.

public boolean equals(Object obj)

Returns true if this tree node and the given parameter are equal (equal values, equal subtrees in same order).

 

public int getLevel( )

Returns the level at which this tree node occurs (root has level 0).

public int getNumberOfChildren( )

Returns the number of children of this tree node.

 

public Object getValue( )

Returns the value in this tree node.

public Tree[ ] getChildren()

Returns an array of children of this tree node.

public String toString( )

Returns a one-line representation of the tree rooted at this tree node.

Transformers (applicative):

public Tree getParent( )

Returns the parent of this tree node, or null if this tree node is the root.

public Tree getSubtree(Object value)

Returns the first subtree of this tree node whose value is equal to value.

Transformers (mutative):

public void setValue(Object value)

Sets the value of this tree node to value.

public void addChild(Tree child)

Adds child as a new (last) child of this tree node.

public void addChildren(Object[ ] children)

For each value in the array children, creates a new tree node with that value and add it as a new child of this tree node.

public Tree deleteChild(Tree subtree)

Removes subtree as a child of this tree node, and returns it (or returns null if subtree was not a child of this tree node).

Miscellaneous:

public void print( )

Prints the tree rooted at this tree node.

Supplied code:

TreeTest.java

Due date:

Tuesday, February 22, before midnight. Note that the JUnit tests have been done for you, so this assignment should be significantly less work than usual.