Class Tree

java.lang.Object

Tree

public class Tree
extends java.lang.Object

A class that implements a basic binary tree storing integers.

You need to complete this class by adding methods to insert values, compute the minimum and maximum, search for a value, and compute a value's depth in the tree and number of descendants. You will also need to complete several constructors used during tree creation and value insertion.

Our binary tree is an example of a recursive data structure, since each tree instance refers to several other tree instances to complete the entire structure. As you might expect, recursive algorithms are particularly useful on recursive data structures.

See Also:

MP5 Documentation, Binary Tree

Constructor Summary

Constructors

Constructor	Description
Tree(int setValue)	Initialize a new binary tree.
Tree(int setValue, Tree setParent)	Initialize a new binary tree node for an existing tree.

Method Summary

Modifier and Type	Method	Description
int	depth()	Return the depth of this node from the root of the tree.
int	descendants()	Return the number of nodes below this node in the tree.
boolean	insert(int newValue)	Insert a new value into the binary tree.
int	maximum()	Return the maximum value stored in this binary tree.
int	minimum()	Return the minimum value stored in this binary tree.
Tree	search(int searchValue)	Search the binary tree for a specific value.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Tree

public Tree(int setValue)

Initialize a new binary tree.

Parameters:

setValue - value for the root of the tree

Tree

public Tree(int setValue,
            Tree setParent)

Initialize a new binary tree node for an existing tree.

Parameters:

setValue - value for the new node

setParent - the parent of this node

Method Detail

insert

public boolean insert(int newValue)

Insert a new value into the binary tree.

Insertion should follow the algorithm described in the MP5 writeup. Do not rebalance the tree or otherwise modify it between insertions. Otherwise the depth and descendants tests will fail. Insertion should fail and return false if the value already exists in the tree.

Parameters:

newValue - the new value to insert

Returns:

true if the value does not already exist and is successfully inserted, false otherwise

See Also:

MP5 Insertion Algorithm

minimum

public int minimum()

Return the minimum value stored in this binary tree.

This function can assume it is called on the root node.

Returns:

the minimum value stored in the tree.

maximum

public int maximum()

Return the maximum value stored in this binary tree.

This function can assume it is called on the root node.

Returns:

the maximum value stored in the tree.

search

public Tree search(int searchValue)

Search the binary tree for a specific value.

Parameters:

searchValue - the value to search for

Returns:

the node containing the specified value, or null if the value is not present in the tree

depth

public int depth()

Return the depth of this node from the root of the tree.

Returns:

the depth of this node relative to the root

descendants

public int descendants()

Return the number of nodes below this node in the tree.

Returns:

the number of nodes below this node in the tree