Árvore binária

http://www.google.com.br
Pesquisa por binary tree java / árvore binária java ou remove node from binary tree java

Vai haver muitos resultados lá.

Se não entender algum, posta aqui o código que tentaremos ajudar.

Vocês podem me dizer quais são as operações de uma árvore binária?

Uma função recursiva é quando ela chama a si mesma, certo?

Inserir e, se preciso, balancear. Remover e, se preciso, balancear. Basicamente, isto.

Sim, recursividade é a ação de chamar a si mesmo.

Como assim balancear?

Amigo, uma árvore binária precisa, a cada inserção, verificar se os elementos estão balanceados. Simples, pense que você inseriu 5 elementos, vamos representá-los por valores 1, 5, 3, 10 e 8. Como a árvore ordena os elementos à maneira que chegam, respeitando o “valor” maior para direita e menor à esquerda, teríamos algo

1
      5
    3  8
          10

//ou

                1
           3
              5
           8
        10

Certo?
A árvore está errada, pendendo para o lado direito (há mais níveis no lado direito que no esquerdo do nó principal, o 1).
Para isto, a árvore terá de se reordenar ou seja, balancear.
Ela fará rotações dos nós até ter o formato mais equilibrado

5
  3   8
1      10
//ou

 1
   3
     5
   8
10

Percebeu?
O nó 1 é o menor, portanto, ele será deslocado para a posição mais à esquerda. O elemento 5 é o mais equilibrado, fica como nó principal. O elemento 10 é o maior, fica como último, à direita. 3 e 8 são intermediários.
Caso você adicione 2

5
    2    8
  1 3    10
//ou

  1
     2
  3     5
     8
  10

Entendeu?

Essa é a estrutura básica de uma árvore binária.

Sugiro ler um pouco sobre ela.

Então se a árvore não tiver balanceada eu faço o que chamam de heap sort? Um algoritmo de ordenação…

Não.
Heap sort, bobble sort ou afins não se aplicam diretamente à árvores.
Você até pode criar uma árvore binária sem balanceamento, mas ela perde a “funcionalidade”. Haja visto o exemplo que dei.
O que você precisa fazer, ao implementar a árvore binária é “prever” estas condições.
Ela pode ter rotação simples ou dupla à direita ou à esquerda, ou ainda, rotação simples direita-esquerda, dependendo do que for inserido nela.
Sempre haverá a verificação, para o nó principal, sendo o valor inserido maior que o nó principal, este elemento será colocado à sua esquerda. No próximo nível, a comparação é refeita, se for maior, vai para à direita, até encontrar um nó ao qual possa se encaixar.
Se menor, vai para à esquerda. Assim sucessivamente.
Quando um lado possui profundidade (diferença entre o nível que possui os últimos nós até o principal) maior que o outro, é preciso fazer o balanceamento.

Tem muita coisa na net, eu vi isto em C, mas é fácil compreender como funciona.

Então o heap sort é outro tipo de estrutura de dados, certo?

Sort = organizar. Ele serve para ordenar determinadas estruturas (eu usava com vetores e matrizes)