Árvore Binária

Árvores binárias são estruturas de dados adequadas para a representação de hierarquias. Composta por um conjunto de nós, onde existe um nó R (raiz) que contém zero ou mais subárvores, cujas ráizes são ligadas diretamente a R.

A raiz se liga a um ou mais elementos e cada um destes forma uma nova subárvore. Esses elementos são seus galhos ou filhos.

Representação:

Implementação:

package arvoreBinariaDeBusca;

public class Arvore {

private No raiz;

public Arvore()
{
raiz = null;
}

void inserir (int dado)
{
raiz = insere(raiz, dado);
}

private No insere (No r, int x)
{
if (r == null)
{
No novo = new No(x);
return novo;
} else if (r.dado < x)
{
r.esq = insere (r.esq, x);
}
else if (r.dado > x)
{
r.dir = insere(r.dir, x);
}
return r;
}

public void mostrar() //Recursivo está no caderno
{
System.out.println("Pre Ordem");
mostrarPreOrdem(raiz);
System.out.println("\nIn Ordem");
mostrarInOrdem(raiz);
System.out.println("\nPos Ordem");
mostrarPosOrdem(raiz);
}

private void mostrarPreOrdem(No no)//Exibe os elementos da direita e depois os da esquerda
{
if (no != null)
{
System.out.print(no.dado + " ");
mostrarPreOrdem(no.dir);
mostrarPreOrdem(no.esq);
}
}

private void mostrarInOrdem(No no)//Exibe os elementos da direita da raiz, volta para a raiz, exibe os elementos da esquerda dela, exibindo o da direita de cada folha
{
if (no != null)
{
mostrarPreOrdem(no.esq);
System.out.print(no.dado + " ");
mostrarPreOrdem(no.dir);
}
}

private void mostrarPosOrdem(No no)//Exibe os elementos da direita e depois os da esquerda
{
if (no != null)
{
mostrarPreOrdem(no.esq);
mostrarPreOrdem(no.dir);
System.out.print(no.dado + " ");
}
}

}

Lista duplamente ligada circular

Uma lista duplamente encadeada é uma representação de uma sequência de objetos na memória do computador. Cada elemento da sequência é armazenado em um nó da lista, com dois ponteiros, um que aponta para o nó anterior e o outro para o seguinte.

Representação:

Implementação:

package listaDuplamenteLigada;

public class ListaDupla {

private No primeira;
private No ultima;
private int totalDeElementos;

public void adicionaNoComeco(int dado) {
if (this.totalDeElementos == 0) {
No novo = new No(dado);
this.primeira = novo;
this.ultima = novo;
novo.setAnterior(novo);
novo.setProxima(novo);

} else {
No novo = new No(this.primeira, dado);
novo.setAnterior(ultima);
ultima.setProxima(novo);
ultima = novo;
primeira.setAnterior(ultima);
}
this.totalDeElementos++;
}

void mostrar() {
if (primeira != null) {
No p = primeira;

do {
System.out.println(p.getDado());
p = p.getProxima();
} while (p != primeira);
}
}

}

Lista simples encadeada

Uma lista encadeada é uma representação de uma sequência de objetos na memória do computador. Cada elemento da sequência é armazenado em um nó da lista, com um ponteiro referenciando ao próximo nó.

Implementação :

package lista;


public class Lista {
 
 private No inicio;
 
 public Lista ()
 {
  inicio = null;
 }
 
 void mostrar ()
 {
  for (No p = inicio; p != null; p = p.prox)
  {
   System.out.println(p.dado);
  }
 }
 
 void inserir (int n)
 {
  inserirFim(n);
 }
 
 @SuppressWarnings("unused")
 private void inserirInicio(int n)
 {
  No novo = new No(n);
  novo.prox = inicio;
  inicio = novo;
 }
 
 private void inserirFim (int n)
 {
  No novo = new No(n);
  if (inicio == null)
  {
   inicio = novo;
  }else{
   No p = inicio;
   while (p.prox != null)
   {
    p = p.prox;
   }
   p.prox = novo;
  }
 }
 
 void remover (int n)
 {
  if (inicio != null)
  {
   No ant, p;
   p = inicio;
   ant = null;
   
   while(p != null && p.dado != n)
   {
    ant = p;
    p = p.prox;
   }
   
   if (p != null)
   {
    if (ant == null)
    {
     inicio = p.prox;
    }else{
     ant.prox = p.prox;
    }
    p = null;
   }
  }
 }
 
 void inverter()
 {
  
 }

}