Binary Search Tree

[paco33]

Hola buenas noches,soy nuevo en el foro y me han pedido un trabajo de árbol binario y no se como empezarlo o hacerlo. Si me pudieseis decir como se hace os lo agradecería.
Me han dado una clase Diccionario, una clase BST y una clase Nodo.
La clase Diccionario es la siguiente:

Código [Seleccionar] Expandir


public interface Diccionario {

/**
     * Mete un valor nuevo.
     * Si ya existe uno con misma clave, reemplaza el valor.
     *
     * @param clave
     * @param valor
     * @throws IllegalArgumentException Si clave es null.
     * @throws IllegalArgumentException Si clave es la cadena vacia.
     * @throws RuntimeException Si no cabe la clave.
     */
    void put(String clave, String valor);
       
   

    /**
     * Saca el valor asociado a la clave.
     *
     * @param clave
     * @return null si no está la clave.
     * @throws IllegalArgumentException Si clave es null.
     * @throws IllegalArgumentException Si clave es la cadena vacia.
     */
    String get(String clave);

    /**
     * Elimina el objeto asociado a la clave, si está.
     *
     * @param clave
     * @return devuelve el valor asociado si estaba la clave; devuelve null si no está la clave
     * @throws IllegalArgumentException Si clave es null.
     * @throws IllegalArgumentException Si clave es la cadena vacia.
     */
    String remove(String clave);

    /**
     * @return número de elementos almacenados.
     */
    int size();

    /**
     * Elimina todas las claves.
     */
    void clear();
}


Esta clase no hace falta hacer nada con ella solo sirve para que la clase BST la implemente.

La clase BST es la siguiente:

Código [Seleccionar] Expandir


public class BST implements Diccionario {

private Nodo root;
private int nDatos;

    public BST(){
    root = null;
    nDatos = 0;
}

Esta es la clase que hay que hacer

Y finalmente la clase nodo que tampoco hay que completarla:

Código [Seleccionar] Expandir


public class Nodo {
String clave;
String valor;
Nodo izq;
Nodo der;

public Nodo (String clave,String valor){
this.clave = clave;
this.valor = valor;
}

}


Si me pudierais ayudar con la realización de la misma os lo agradecería mucho.
Gracias de antemano.