Al taller, implementación de BinaryTree en JAVA

Bien, después de tanto parloteo en mis anteriores intervenciones, voy a hacer un pequeño taller que pienso dividir en varias partes. Quiero que esto sirva de implementación en JAVA para el tipo abstracto de datos BinaryTree que implementa la interface Tree. Estará basada en los TAD usados en la escuela superior de informática de la Universidad de Sevilla.

Primero un poco de teoría:

El árbol binario es una forma de representación de datos que se encuentran en una estructura enraizada. Es una colección de elementos(nodos) que siguen una jerarquía entre ellos de padres e hijos. El primer nodo es la raiz, y si el nodo carece de hijos se llama hoja.

Pequeño esquema de árbol binario:

Siento que la zona en azul apenas se aprecie, porque al pasar a jpg se ha perdido demasiada calidad. Como se ve, en nuestro caso, al ser un árbol binario, cada nodo padre solo puede tener 2 nodos hijos, pero existen otro tipo de árboles n-arios con mas de 2.

La importancia de los BinaryTree, radica en que en ellos se basan los árboles de búsqueda (muy eficientes en este trabajo), también montículos y otros muchos. Son herramientas sumamente útiles.

La forma tan peculiar de estas estructuras, hacen que existan múltiples métodos de recorrerlos. Recorrido inorden, preorden, posorden, busqueda en profundidad, en anchura.

Los métodos que implementaremos serán:

int size()
Devuelve el número de nodos que tiene el árbol.

Iterator iterator()
Devuelve un iterador que recorre el árbol en orden simétrico si es
SearchTree, y en orden previo si es BinaryTree o NAryTree.

boolean equals(Object bt)
Devuelve un booleano indicando si el árbol sobre el que se invoca
tiene la misma estructura y los mismos elementos (en el sentido
del equals() para elementos) en los mismos sitios que bt.
Interfaz

Object getRoot()
Devuelve la raíz del árbol. Si el árbol es vacío eleva la excepción
NoSuchElementException.

BinaryTree left()
Devuelve el subárbol izquierdo del árbol. Si el árbol sobre el que
se aplica es vacío eleva la excepción EmptyTreeException.

BinaryTree right()
Devuelve el subárbol derecho del árbol. Si el árbol sobre el que
se aplica es vacío eleva la excepción EmptyTreeException.

void setRoot(Object root)
Sustituye la raíz del árbol por root. Si el árbol es vacío eleva la
excepción NoSuchElementException.

void remove(boolean left)
Si left es true, elimina el hijo izquierdo del árbol; si es false,
elimina el derecho. Si el árbol sobre el que se aplica es vacío
eleva la excepción EmptyTreeException.

void set(boolean left,BinaryTree t)
Si left es true, sustituye el hijo izquierdo del árbol por t; si es
false, sustituye el derecho. Si el árbol sobre el que se aplica es
vacío eleva la excepción EmptyTreeException.

boolean isLeaf()
Devuelve true si este árbol es una hoja y false en caso
contrario. Eleva la excepción EmptyTreeException si el árbol
con el que se trabaja está vacío.

boolean isEmpty()
Devuelve un booleano indicando si el árbol sobre el que se invoca
es vacío.

Iterator iterator(String it)
Devuelve un iterador que recorre el árbol en función de la cadena
de entrada “PREORDEN”, “INORDEN” o “INORDEN".