Árvores Binárias
Por: mauricio_jr • 30/3/2016 • Pesquisas Acadêmicas • 431 Palavras (2 Páginas) • 322 Visualizações
Árvores Binárias
- Estrutura de dados em que um nó tem apontamentos para, no máximo, dois nós filhos.
Os filhos são definidos como:
- Filho a esquerda
- Filho a direita
- Os elementos são armazenados em ordem de chegada. O primeiro de todos será o nó raiz.
- A ordem dos elementos influencia o desenho (estrutura) da árvore.
- Inserção de elementos:
- Partindo da raiz, compara-se o valor a ser inserido com o valor do nó. Sendo menor vai para o filho à esquerda, sendo maior à direita.[pic 1]
[pic 2][pic 3][pic 4][pic 5]
A RECURSIVIDADE é plenamente utilizada em árvores. Os passos executados em um nó são aplicados/executados nos demais nós.
Exemplo de árvore Binária: (no caderno)
20 – 10 – 30 – 5 – 15
PERCURSOS em uma árvore binária:
Em Ordem (Vai trazer os dados organizados) Exemplo caderno
- Percorre à esquerda
- Lê-se o meio
- Percorre a direita
Pré Ordem: Exemplo caderno
-Lê-se o meio
- Percorre à esquerda
- Percorre à direita
Pós Ordem: Exemplo caderno
- Percorre à esquerda
- Percorre à direita
-Lê-se o meio
Implementação do código da árvore aula dia 12/11/2015
package arvorebinaria;
public class No {
private Comparable valor;
private No filhoEsquerda;
private No filhoDireita;
public No(Comparable valor){
this.valor = valor;
}
public void inserir(Comparable valor){
if (valor.compareTo(this.valor)>0){
if(filhoDireita == null){
filhoDireita= new No(valor);
}else
{
filhoDireita.inserir(valor);
}
}else
{
if (filhoEsquerda == null){
filhoEsquerda = new No(valor);
}else
{
filhoEsquerda.inserir(valor);
}
}
}
}
...