ca.pfv.spmf.datastructures.binarytree

Class BinaryTree<T extends java.lang.Comparable<T>>

java.lang.Object

ca.pfv.spmf.datastructures.binarytree.BinaryTree<T>

public class BinaryTree<T extends java.lang.Comparable<T>>
extends java.lang.Object

This is an implementation of a "binary tree" based on the chapter 12 of the book: "Introductions to algorithms" by Cormen et al. (2001). Most of the code is based on the pseudo-code from this book.

Elements inserted in the tree have to extend the Comparable class.

The tree provides these operations: add, remove, size, contains, minimum, maximum, popMinimum, popMaximum, higher, lower.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	BinaryTree.Node Internal class that represents a node of the binary tree

Constructor Summary

Constructors

Constructor and Description
BinaryTree() Default constructor
BinaryTree(boolean allowSameElementMultipleTimes) Constructor

Method Summary

Modifier and Type	Method and Description
void	add(T element) Add an element to the tree.
boolean	contains(T k) Check if an element is contained in the tree
T	higher(T k) Return the largest element having a value lower than a given element k.
boolean	isEmpty() Check if the tree is empty.
T	lower(T k) Return the largest element having a value lower than a given element k.
T	maximum() Get the maximum element in the tree
T	minimum() Get the minimum element in the tree
T	popMaximum() Get the maximum element in the tree and remove it from the tree
T	popMinimum() Get the minimum element in the tree and remove it from the tree
void	remove(T element) Remove an element from the tree
int	size() Return the number of elements stored in the tree
java.lang.String	toString() Method toString that returns a string with all the elements in the tree according to the ascending order.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

BinaryTree

public BinaryTree(boolean allowSameElementMultipleTimes)

Constructor

Parameters:

allowSameElementMultipleTimes - if set to true, this allows the tree to contains the same element multiple times. To check if an element is the same, this class use the compareTo method

BinaryTree

public BinaryTree()

Default constructor

Method Detail

size

public int size()

Return the number of elements stored in the tree

Returns:

an integer

add

public void add(T element)

Add an element to the tree.

Parameters:

element - the element to be added

isEmpty

public boolean isEmpty()

Check if the tree is empty.

Returns:

true if empty

remove

public void remove(T element)

Remove an element from the tree

Parameters:

element - the element to be removed

popMinimum

public T popMinimum()

Get the minimum element in the tree and remove it from the tree

Returns:

the minimum element in the tree

lower

public T lower(T k)

Return the largest element having a value lower than a given element k.

higher

public T higher(T k)

Return the largest element having a value lower than a given element k.

minimum

public T minimum()

Get the minimum element in the tree

Returns:

the minimum element in the tree

popMaximum

public T popMaximum()

Get the maximum element in the tree and remove it from the tree

Returns:

the maximum element in the tree

maximum

public T maximum()

Get the maximum element in the tree

Returns:

the maximum element in the tree

contains

public boolean contains(T k)

Check if an element is contained in the tree

Parameters:

k - the element.

Returns:

true if the element is in the tree. Otherwise, false.

toString

public java.lang.String toString()

Method toString that returns a string with all the elements in the tree according to the ascending order. NOTE : could be transformed into a non recursive algorithm.

Overrides:

toString in class java.lang.Object