Fala guido! Tudo bom?

Respondendo as suas perguntas em ordem:

1- Árvore Binária é uma estrutura de dados, ela pode ser uma árvore vazia, uma árvore com um nó raiz, a sub-arvore da direita (que pode não existir) e a sub-arvore da esquerda (que pode não existir). Seguindo essa definição, uma folha de uma árvore é um nó com 0 sub-árvores

É importante frisar que a forma mais natural de definir uma estrutura de árvores é a recursividade!

2- Segue abaixo uma implementação de árvore binária utilizando generics do java, deixei o código todo comentado para facilitar seu entendimento.

ArvBin

public class Arvbin<T extends Comparable<T>>
{
    private T val;   /* Valor armazenado na raiz. */

    /* Referências para sub-árvores. */
    private Arvbin<T> esq, dir;

    /* Construtor de árvore sem sub-ávores (dir = esq = null). É fornecido apenas o valor da raiz. */
    public Arvbin(T valor)
    {
        val = valor;
        esq = null;
        dir = null;
    }

    /* Construtor de árvore com sub-ávores. São fornecidos
    o valor da raiz e as sub-árvores, que devem ter sido 
    construídas previamente.*/
    public Arvbin(T valor, Arvbin<T> arvEsq, Arvbin<T> arvDir)
    {
        val = valor;
        esq = arvEsq;
        dir = arvDir;
    }

    /* Retorna o valor armazenado na raiz. */
    public T retornaVal()
    {
        return val;
    }

    /* Retorna a sub-árvore esquerda 
       (ou null se não houver). */
    public Arvbin<T> retornaEsq()
    {
        return esq;
    }

    /* Retorna a sub-árvore direita 
    (ou null se não houver). */
    public Arvbin<T> retornaDir()
    {
        return dir;
    }

    /* Modifica o valor armazenado na raiz. */
    public void defineVal(T valor)
    {
        val = valor;
    }

    /* Redefine a sub-árvore esquerda, apagando a antiga se houver. */
    public void defineEsq(Arvbin<T> filho)
    {
        esq = filho;
    } 

    /* Redefine a sub-árvore direita, apagando a antiga se houver. */
    public void defineDir(Arvbin<T> filho)
    {
        dir = filho;
    }

    /* Imprime o conteúdo da árvore em pré-ordem */
    public void mostra()
    {
        System.out.print("(" + val);
        if (esq != null)
            esq.mostra();
        if (dir != null)
            dir.mostra();
        System.out.print(")");
    }

    /* Calcula e retorna a altura da árvore. */
    public int calculaAltura()
    {
        if((esq == null) && (dir == null))
            return 0;

        int altEsq = 0, altDir = 0;

        if(esq != null)
            altEsq = esq.calculaAltura();

        if(dir != null)
            altDir = dir.calculaAltura();

        return 1 + Math.max(altEsq, altDir);
    }

    /* Calcula e retorna o maior valor contido na árvore. */
    public T calculaMaximo()
    {
        if((esq == null) && (dir == null))
            return val;

        T maiorGeral, maiorEsq, maiorDir; 

        if((esq != null) && (dir == null))
        {
            maiorGeral = esq.calculaMaximo();
        }
        else if((esq == null) && (dir != null))
        {
            maiorGeral = dir.calculaMaximo();
        }
        else
        {
            maiorEsq = esq.calculaMaximo();
            maiorDir = dir.calculaMaximo();

            if(maiorEsq.compareTo(maiorDir) > 0)
                maiorGeral = maiorEsq;
            else
                maiorGeral = maiorDir;
        }

        if(maiorGeral.compareTo(val) > 0)
            return maiorGeral;

        return val;
    }

    /* Verifica se um valor está na árvore. Se estiver, retorna um ponteiro para o
       o nó que tem esse valor. Caso contrário, retorna null. */
    public Arvbin<T> busca(T valor)
    {

        Arvbin<T> ret;

        /* Se é igual ao valor armazenado, não precisa procurar mais. O nó é a raiz. */
        if (valor.compareTo(val) == 0)
        {
            return this;
        }

        /* Senão, começa procurando na sub-árvore esquerda. */
        if (esq != null){
            ret = esq.busca(valor);
            if (ret != null)
                return ret;
        }

        /* Se chega a esse ponto, estará na árvore se, e somente se, 
         estiver na sub-árvore direita */
        if (dir != null) 
            return dir.busca(valor);
        return null;
    }
}

Main

public class Main
{
    public static void main(String[] args)
    {
        Arvbin<Integer> a1 = new Arvbin<Integer>(1),
                a2 = new Arvbin<Integer>(2),
                a3 = new Arvbin<Integer>(3,a1,a2),
                a4 = new Arvbin<Integer>(4),
                a5 = new Arvbin<Integer>(5),
                a6 = new Arvbin<Integer>(6),
                a7 = new Arvbin<Integer>(7,a5,a6),
                a8 = new Arvbin<Integer>(8),
                a9 = new Arvbin<Integer>(9),
                a10 = new Arvbin<Integer>(10,a8,a9);

                a4.defineEsq(a3);
                a4.defineDir(a7);
                a4.mostra();
                System.out.println();

                Arvbin<Integer> a11 = a4.busca(3);
                if (a11 != null)
                {
                    a11.defineVal(11);
                    a11.defineEsq(a10);
                }
                a4.mostra();
                System.out.println();
    }
}

3- A estrutura do Java TreeMap representa uma red-black tree, a melhor forma que eu conheço seria seguir a implementação padrão de uma olhada no código!

Espero ter ajudado!

Abraços e bons estudos!

Valeu! Consegui entender o código! Clareou bastante. Abração!