Embed Size (px)
Citation preview
Por Ayrton Yagami
SumárioAula 02 - Ordenação pelo método bubble sort.................................................................................2
Aula 03 - Ordenação pelos métodos insertion sort e selection sort.............................................11
Aula 07 - Recursão em JAVA...........................................................................................................17
Aula 09 - Árvore..................................................................................................................................20
- Árvores Multiway......................................................................................................................21
Aula 10 - Árvore Binária em JAVA...................................................................................................25
Aula 11 - Árvore AVL em JAVA........................................................................................................32
Aula 12 - Exclusão de um nó em Árvore Binária e Árvore AVL em JAVA..................................43
Por Ayrton Yagami
Aula 02 - Ordenação pelo método bubble sort
Aula 02 - Ordenação pelo método bubble sort BUBBLE SORT O método de ordenação por bubble sort ou conhecido como bolha consiste em compara dados armazenados em um vetor de tamanho qualquer, comparando cada elemento de uma posição com o próximo elemento do vetor. A ordenação pode ser crescente ou decrescente basta trocar a ordem de comparação. Um laço com a quantidade de elementos do vetor será executado (for(j=1;j<=n;j++)), e dentro deste, outro laço que percorre da primeira à penúltima posição do (for(i=0;i<n−1;i++)). Abaixo é mostrador o processo de ordenação bubble sort:
Por Ayrton Yagami
Por Ayrton Yagami
Exemplos da implementação do algoritmo em java: import java.util.Scanner; public class BubbleSort {
Por Ayrton Yagami
public static void main(String[] args) { Scanner in = new Scanner(System.in); int x[] = new int[5]; int n, i, aux; for (i = 0; i <= 4; i++) { System.out.print("Digite o " + (i + 1) + "° número: "); x[i] = in.nextInt(); } for (n = 1; n <= 5; n++) { for (i = 0; i <= 3; i++) { if (x[i] > x[i + 1]) { aux = x[i]; x[i] = x[i + 1]; x[i + 1] = aux; } } } for (i = 0; i <= 4; i++) { System.out.println((i + 1) + "° número: " + x[i]); } }} BUBBLE SORT melhorado (1ª versão) Abaixo é mostrador o processo de ordenação bubble sort melhorado:
Por Ayrton Yagami
Por Ayrton Yagami
Exemplos da implementação do algoritmo em java: import java.util.Scanner; public class BubbleSortMelhorado01 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int x[] = new int[5]; int i, j, aux; for (i = 0; i <= 4; i++) { System.out.print("Digite o " + (i + 1) + "° número: "); x[i] = in.nextInt(); } for (j = 1; j <= 4; j++) { for (i = 4; i >= j; i--) { if (x[i] < x[i - 1]) { aux = x[i]; x[i] = x[i - 1]; x[i - 1] = aux; } } } for (i = 0; i <= 4; i++) { System.out.println((i + 1) + "° número: " + x[i]); }
Por Ayrton Yagami
}} BUBBLE SORT melhorado (2ª versão) Abaixo é mostrador o processo de ordenação bubble sort melhorado:
Por Ayrton Yagami
Exemplos da implementação do algoritmo em java: import java.util.Scanner; public class BubbleSortMelhorado02 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int x[] = new int[5]; int n, i, aux, troca; for (i = 0; i <= 4; i++) { System.out.print("Digite o " + (i + 1) + "° número: "); x[i] = in.nextInt(); } n = 1; troca = 1; while (n <= 5 && troca == 1) { troca = 0; for (i = 0; i <= 3; i++) {
Por Ayrton Yagami
if (x[i] > x[i + 1]) { troca = 1; aux = x[i]; x[i] = x[i + 1]; x[i + 1] = aux; } } n = n + 1; } for (i = 0; i <= 4; i++) { System.out.println((i + 1) + "° número: " + x[i]); } }} Exercício: 1. Faça um programa que cadastre o nome e o salário de 10 funcionários, liste todos os dados dos funcionários das seguintes formas: a) em ordem crescente de salário;b) em ordem decrescente de salário;c) em ordem alfabética;
Por Ayrton Yagami
Aula 03 - Ordenação pelos métodos insertion sort e selection sort
INSERTION SORT Este método de ordenação por inserção se baseia na comparação do segundo número inserido no vetor, os elementos são ordenados de forma crescente ou decrescente dependendo da forma que o algoritmo é implementado. Um laço com as comparações será executado do segundo elemento ao último, na quantidade de vezes igual ao número de elementos do vetor menos um (for(i=1;i<n;i++)), enquanto existirem elementos à esquerda do número e a posição que atende a ordenação não for encontrada, o laço será executado. Abaixo é mostrador o processo de ordenação insertion sort:
Por Ayrton Yagami
Por Ayrton Yagami
Exemplos da implementação do algoritmo em Java: import java.util.Scanner; public class InsertionSort { public static void main(String[] args) { Scanner in = new Scanner(System.in); int x[] = new int[5]; int i, j, eleito; for (i = 0; i <= 4; i++) { System.out.print("Digite o " + (i + 1) + "° número: "); x[i] = in.nextInt(); } for (i = 1; i <= 4; i++) { eleito = x[i]; j = i - 1; while (j >= 0 && x[j] > eleito) { x[j + 1] = x[j]; j = j - 1; }
Por Ayrton Yagami
x[j + 1] = eleito; } for (i = 0; i <= 4; i++) { System.out.println((i + 1) + "° número: " + x[i]); } }} SELECTION SORT Já neste método cada número do vetor, a partir do primeiro, é eleito e comparado com o menor ou maior, dependendo da ordenação desejada, número dentre os que estão à direita do eleito. Procura-se um número menor (quando crescente) ou um maior (quando decrescente). O número eleito está na posição i. Os números à direita estão nas posições de i+1 a n–1, sendo n o número de elementos do vetor. O laço a ser executado para encontrar o menor elemento à direita do eleito será (for(j=i+2;j<=n−1;j++)). Abaixo é mostrador o processo de ordenação selection sort:
Por Ayrton Yagami
Exemplos da implementação do algoritmo em java: import java.util.Scanner; public class SelectionSort { public static void main(String[] args) { Scanner in = new Scanner(System.in); int x[] = new int[5]; int i, j, eleito, menor, pos; for (i = 0; i <= 4; i++) { System.out.print("Digite o " + (i + 1) + "° número: "); x[i] = in.nextInt(); } for (i = 0; i <= 3; i++) { eleito = x[i]; menor = x[i + 1];
Por Ayrton Yagami
pos = i + 1; for (j = i + 2; j <= 4; j++) { if (x[j] < menor) { menor = x[j]; pos = j; } } if (menor < eleito) { x[i] = x[pos]; x[pos] = eleito; } } for (i = 0; i <= 4; i++) { System.out.println((i + 1) + "° número: " + x[i]); } }} Exercício: 1. Faça um programa que cadastre 15 números inteiros, ordene-os usando o métodos insertion sort e em seguida encontre o menor número e quantas vezes ele apareceu no vetor.R.: 2. Faça um programa que cadastre 10 números reais, ordene-os usando o métodos selection sort e em seguida encontre o maior número e quantas vezes ele apareceu no vetor.R.:
Por Ayrton Yagami
Aula 07 - Recursão em JAVA
Conceito sobre recursão
A recursão é uma forma de programar no qual o método (função) chama ele mesmo, isto
pode parecer estranho ou um erro de programação, mais a recursão é uma das técnicas
mais interessantes em programação. Um exemplo que uso comum para fazer uma recursão
é o uso do algoritmo de fatorial que é mostrado abaixo:
import java.util.Scanner;
public class Fatorial {
static int fatorial(int n){
if(n==0){
return 1;
}else{
return (n * fatorial(n-1));
}
}
public static void main(String[] args) {
Scanner entrada = new Scanner(System.in);
System.out.print("Digite um númeor: ");
int numero = entrada.nextInt();
System.out.printf("O fatorial é %d\n",fatorial(numero));
}
}
Por Ayrton Yagami
Na figura abaixo mostra de forma gráfica a resolução do método fatorial que faz de uso de
recursão
Por Ayrton Yagami
Veja outro exemplo usando recursividade, em nossas aulas anteriores foi passado um
exercício sobre pilha onde deveria ser realizado a solução da Torre de Hanoi usando
conceitos de pilha.
public class TorreHanoi {
static void torrehanoi(int ndisco, char haste1, char haste2, char haste3)
{
if (ndisco == 1) {
System.out.println("Disco 1 de " + haste1 + " para " + haste3);
} else {
torrehanoi(ndisco - 1, haste1, haste3, haste2);
System.out.println("Disco " + ndisco + " de " + haste1 + " para "
+ haste3);
torrehanoi(ndisco - 1, haste2, haste1, haste3);
}
}
public static void main(String[] args) {
torrehanoi(3, 'A', 'B', 'C');
}
}
Exercícios
1) Construa um algoritmo que use recursividade para resolver o problema matemático
da seria de Pitágoras, sabendo que a serie é 1, 3, 6, 10, 15, 21, ...R.:
2) Dado a função para imprimir os termos de uma lista simplesmente encadeada, transforme em um método onde ira usar recursividade para imprimir esta lista.R.:
Por Ayrton Yagami
Aula 09 - Árvore
Conceitos
Árvores são estruturas de dados adequadas para representação de hierarquias, é composta por um conjunto de nós, um destes nós que é denominado raiz quando contém zero ou mais sub-árvores e os nos das sub-árvores são ditos como filhos do nó pai. Os nós com filhos são chamado de nós internos e os nós sem filhos são chamado de nos externos ou folhas.
Podemos classificar as árvores em duas grandes classes: as árvores genéricas (n-área) ou as árvores binárias
Árvores genéricas
São estruturas de dados que não há limites em relação de nós, exemplo:
Em árvores genéricas temos alguns modelos específicos como as árvores digitais, multiway e outras.
- Árvores Digitais
Por Ayrton Yagami
- Árvores Multiway
Árvores binárias
São estruturas de dados baseada em uma lista duplamente encadeada, possuem limites em relação aos nós não ultrapassando dois nós filhos por no pai, exemplo:
Por Ayrton Yagami
Em árvores binárias temos outros modelos específicos, como a árvore PATRICIA que e uma árvore digital binária.
Percurso de Árvores Binárias
Por Ayrton Yagami
Para percorre os nós de uma árvore binária, existem essencialmente três ordens naturais que são:
Pré-ordem: raiz, esquerda, direita
Pós-ordem: esquerda, direita, raiz
In-ordem: esquerda, raiz, direita
Exemplo de caminhamentos:
Pré-ordem: ABDGCEHIF
In-ordem: DGBAHEICF
Pós-ordem: GDBHIEFCA
Exercícios
1) Defina o pré-ordem, em-ordem e pós-ordem da seguinte árvore binária
Por Ayrton Yagami
R.:
2) Dado o pré-ordem, em-ordem e pós-ordem construa as árvores binária abaixo:
a)pré-ordem: 8, 5, 3, 7, 10, 9, 12.
em-ordem: 3, 5, 7, 8, 9, 10, 12,
R.:
b) em-ordem : 2, 3, 4, 5, 6, 7, 8.
pós-ordem : 3, 4, 2, 6, 5, 8, 7.
R.:
Por Ayrton Yagami
Aula 10 - Árvore Binária em JAVA
Árvores são estrutura para representação hierarquia de dados não lineares onde os elementos não estão armazenado em uma forma sequencial e também não estão todos encadeados. Em uma Árvore Binária está dividida em três grupos o primeiro é o nó raiz, o segundo é a sub-árvore à direita e o terceiro é a sub-árvore à esquerda. E elas possuem as seguintes propriedades: 1. Todos os nós de uma sub-árvore direita são maiores que o nó raiz.2. Todos os nós de uma sub-árvore esquerda são menores que o nó raiz.3. Cada sub-árvore é também uma árvore binária.4.O grau de um nó representa o seu número de sub-árvores.
5. Na árvore binária, o grau máximo de um nó é 2.6. O grau de uma árvore é igual ao máximo dos graus de todos os seus nós.7. Uma árvore binária tem grau máximo igual a 2.8.Nó pai: nó acima e com ligação direta a outro nó.9. Nó filho: nó abaixo e com ligação direta a outro nó. São os nós raízes das sub-árvores.10. Nós irmãos: são que possuem o mesmo nó pai.11. Nó folha ou terminal: nó que não possui filhos.12. Nós ancestrais: estão acima de um nó e têm ligação direta ou indireta.
Por Ayrton Yagami
13. Nós descendentes: estão abaixo de um nó e possuem ligação direta ou indireta.
14. Nós descendentes direito: estão abaixo de um nó, possuem ligação direta ou indireta e fazem parte da sub-árvore direita.
Por Ayrton Yagami
15. Nós descendentes esquerdo: estão abaixo de um nó, possuem ligação direta ou indireta e fazem parte da sub-árvore esquerda.
16. Nível de um nó: distância do nó raiz.17. Altura ou profundidade da árvore: nível mais distante da raiz.
Por Ayrton Yagami
18. Expressão que representa o número máximo de nós em um nível da árvore binária = 2n, onde n é o nível em questão.
19. Árvore estritamente binária: árvore em que todos os nós têm 0 ou 2 filhos.20. Expressão que representa o número de nós de uma árvore estritamente binária = 2n−1, onde n é o número de nós folha.
21. Árvore completa: todos os nós com menos de dois filhos ficam no último e no penúltimo nível.
Por Ayrton Yagami
22. Árvore cheia: árvore estritamente binária e completa.
Para construir uma Árvore Binária é utilizado a mesma estrutura de dados de uma lista duplamente encadeada, em vês de haver as referência para o próximo e anterior nó da lista são usadas referenciar a direita e esquerda da Árvore Binária, abaixo é mostrador estrutura da classe ARVORE onde é representado uma Árvore Binária em JAVA. private static class ARVORE { public int num; public ARVORE dir, esq;} Para manipular Árvore Binária devemos ter as seguintes funções: inserção de dados na Árvore, impressão de dados da Árvore, consulta de dados da Árvore e remoção de dado da Árvore. No algoritmo abaixo é representado estas funções: public class ArvoreBinaria { private static class ARVORE { public int num; public ARVORE dir, esq; } public static ARVORE inserir(ARVORE aux, int num) { if (aux == null) { aux = new ARVORE(); aux.num = num;
Por Ayrton Yagami
aux.esq = null; aux.dir = null; } else if (num < aux.num) { aux.esq = inserir(aux.esq, num); } else { aux.dir = inserir(aux.dir, num); } return aux; } public static void imprimir(ARVORE aux) { if (aux != null) { imprimir(aux.esq); System.out.print(aux.num + ", "); imprimir(aux.dir); } } public static void main(String[] args) { ARVORE a = null; a = inserir(a, 5); a = inserir(a, 4); a = inserir(a, 7); a = inserir(a, 8); a = inserir(a, 2); a = inserir(a, 3); a = inserir(a, 9); System.out.print("A : "); imprimir(a); System.out.println(); a = inserir(a, 10); System.out.print("A : "); imprimir(a); System.out.println(); }}
Exercícios
1. Usando conceitos de árvores, construa as funções pré-ordem e pós-ordem para a
seguinte árvore 10, 5, 8, 3, 15, 13, 1, 18, 21.R.:
2. Construa um algoritmo que leia 10 números, armazene-os em uma árvorebinária e, em seguida, liste apenas os números pares.R.:
Por Ayrton Yagami
Por Ayrton Yagami
Aula 11 - Árvore AVL em JAVA
Em 1962 Adelson Velsky e Landis criam o algoritmo para balanceamento de árvores binária obedecendo a seguinte regra, as sub-árvores direita ou esquerda não podem ter diferenças na altura entre o nó, não ultrapassando -1 até 1 conforme é mostrado no figura abaixo.
A árvore ilustrada acima é dita como uma árvore balanceada, para que todas as árvores binárias sejam balanceadas necessito que seja executado as seguintes regras de rotação dos nó que são mostrada na tabela abaixo.
Diferença na altura do nó
Diferença na altura do filho do nó desbalanceado
Tipo de rotação
21 Simples à esquerda0 Simples à esquerda-1 Dupla com filho para a direita é
pai para esquerda
-21 Dupla com filho para a esquerda
e pai para direita0 Simples à direita-1 Simples à direita
Exemplo de rotação simples à esquerda Insira os seguintes termos em uma árvore binária: 6, 8 e 12 na figura abaixo ilustra o balanceamento da árvore.
Por Ayrton Yagami
Insira os seguintes termos em uma árvore binária: 10, 12, 11 e 14 na figura abaixo ilustra o balanceamento da árvore.
Por Ayrton Yagami
Exemplo de rotação simples à direita Insira os seguintes termos em uma árvore binária: 8, 6 e 2 na figura abaixo ilustra o balanceamento da árvore.
Por Ayrton Yagami
Insira os seguintes termos em uma árvore binária: 10, 6, 2 e 8 na figura abaixo ilustra o balanceamento da árvore.
Por Ayrton Yagami
Exemplo de rotação dupla para à direita e pai para esquerda Insira os seguintes termos em uma árvore binária: 6, 8 e 7 na figura abaixo ilustra o balanceamento da árvore.
Por Ayrton Yagami
Exemplo de rotação dupla para à esquerda e pai para direita Insira os seguintes termos em uma árvore binária: 6, 3 e 5 na figura abaixo ilustra o balanceamento da árvore.
Por Ayrton Yagami
Para manipular o algoritmo de Árvore AVL em Java devemos ter as seguintes funções: uma função de inserção dos dados na árvore onde ira chamar a outra função de balanceamento e a função de balanceamento ira chamar as funções para rotacionar os dados conforme é mostrado no algoritmo abaixo: public class ArvoreAVL { private static class ARVORE { public int num, altd, alte; public ARVORE dir, esq; } public static ARVORE inserir(ARVORE aux, int num) { // o objeto novo é um objeto auxiliar
Por Ayrton Yagami
ARVORE novo; if (aux == null) { novo = new ARVORE(); novo.num = num; novo.altd = 0; novo.alte = 0; novo.esq = null; novo.dir = null; aux = novo; } else if (num < aux.num) { aux.esq = inserir(aux.esq, num); if (aux.esq.altd > aux.esq.alte) { aux.alte = aux.esq.altd + 1; } else { aux.alte = aux.esq.alte + 1; } aux = balanceamento(aux); } else { aux.dir = inserir(aux.dir, num); if (aux.dir.altd > aux.dir.alte) { aux.altd = aux.dir.altd + 1; } else { aux.altd = aux.dir.alte + 1; } aux = balanceamento(aux); } return aux; } public static ARVORE balanceamento(ARVORE aux) { int d, df; d = aux.altd - aux.alte; if (d == 2) { df = aux.dir.altd - aux.dir.alte; if (df >= 0) { aux = rotacao_esquerda(aux); } else { aux.dir = rotacao_direita(aux.dir); aux = rotacao_esquerda(aux); } } else if (d == -2) { df = aux.esq.altd - aux.esq.alte; if (df <= 0) { aux = rotacao_direita(aux); } else { aux.esq = rotacao_esquerda(aux.esq); aux = rotacao_direita(aux); } } return aux; } public static ARVORE rotacao_esquerda(ARVORE aux) { ARVORE aux1, aux2; aux1 = aux.dir;
Por Ayrton Yagami
aux2 = aux1.esq; aux.dir = aux2; aux1.esq = aux; if (aux.dir == null) { aux.altd = 0; } else if (aux.dir.alte > aux.dir.altd) { aux.altd = aux.dir.alte + 1; } else { aux.altd = aux.dir.altd + 1; } if (aux1.esq.alte > aux1.esq.altd) { aux1.alte = aux1.esq.alte + 1; } else { aux1.alte = aux1.esq.altd + 1; } return aux1; } public static ARVORE rotacao_direita(ARVORE aux) { ARVORE aux1, aux2; aux1 = aux.esq; aux2 = aux1.dir; aux.esq = aux2; aux1.dir = aux; if (aux.esq == null) { aux.alte = 0; } else if (aux.esq.alte > aux.esq.altd) { aux.alte = aux.esq.alte + 1; } else { aux.alte = aux.esq.altd + 1; } if (aux1.dir.alte > aux1.dir.altd) { aux1.altd = aux1.dir.alte + 1; } else { aux1.altd = aux1.dir.altd + 1; } return aux1; } public static void exibiremordem(ARVORE aux) { if (aux != null) { System.out.print(aux.num + " "); exibiremordem(aux.esq); exibiremordem(aux.dir); } } public static void exibirpreordem(ARVORE aux) { if (aux != null) { System.out.print(aux.num + ", "); exibirpreordem(aux.esq); exibirpreordem(aux.dir); }
Por Ayrton Yagami
} public static void exibirposordem(ARVORE aux) { if (aux != null) { exibirposordem(aux.esq); exibirposordem(aux.dir); System.out.print(aux.num + ", "); } } public static void main(String[] args) { ARVORE a = null; a = inserir(a, 10 ); a = inserir(a, 4); a = inserir(a, 7); a = inserir(a, 8); a = inserir(a, 2); a = inserir(a, 3); a = inserir(a, 9); System.out.print("EM : "); exibiremordem(a); System.out.println(); System.out.print("PRE : "); exibirpreordem(a); System.out.println(); System.out.print("POS : "); exibirposordem(a); System.out.println(); }}
Exercícios
1) Dados as seguinte árvores monte-as de forma gráfica usando o algoritmo de árvores
AVL.a) 2, 3 e 4;
R:
b) 2, 4 e 3;R.:
c) 4, 3 e 2;R.:
d) 4, 3, 2 e 1;R.:
e) 2, 4, 3 e 1;R.:
f) 2, 3, 4 e 1;
Por Ayrton Yagami
R.:
2) Crie um programa que leia 10 números, armazene-os em uma árvore AVL e, em seguida, liste apenas os números pares.R.:
Por Ayrton Yagami
Aula 12 - Exclusão de um nó em Árvore Binária e Árvore AVL em JAVA
A exclusão de um nó em Árvore binária é uma operação muito comum, mas tem seu grau de complexidade, para excluir o um nó temos que localiza-lo na árvore usando uma função de localização, que é mostrada abaixo: public static boolean localizar(ARVORE aux, int num, boolean loc) { if (aux != null && loc == false) { if (aux.num == num) { loc = true; } else if (num < aux.num) { loc = localizar(aux.esq, num, loc); } else { loc = localizar(aux.dir, num, loc); } } return loc; } Quando for localizado o nó na Árvore haverá três situações distintas para a exclusão que são:
Nó a ser excluído é uma folha, Nó a ser excluído tem um filho, Nó a ser excluído tem dois filhos.
Primeira situação: Nó a ser excluído é uma folha. Para excluir o nó folha simplesmente é alterado o campo do nó pai onde informa qual é o nó filho para vazio. Na figura abaixo ilustra a exclusão do nó 7.
Segunda situação: Nó a ser excluído tem um filho. Neste caso o nó tem apenas duas ligações uma com seu pai e a outra com seu filho, para fazer a exclusão se corta a ligação do nó intermediário ligando o nó pai com o nó filho. Na figura abaixo ilustra a exclusão do nó 71.
Por Ayrton Yagami
Terceira situação: Nó a ser excluído tem dois filhos. Então para excluir um nó que tem dois filhos é substituído o nó por seu sucessor em ordem assim eliminando o nó. Na figura abaixo ilustra a exclusão do nó 25.
Abaixo é mostrado função para exclusão nó em uma Árvore Binária ou Árvore AVL: public static ARVORE excluir(ARVORE aux, int num) { ARVORE p, p2; if (aux.num == num) { if (aux.esq == aux.dir) { return null; } else if (aux.esq == null) { return aux.dir; } else if (aux.dir == null) {
Por Ayrton Yagami
return aux.esq; } else { p2 = aux.dir; p = aux.dir; while (p.esq != null) { p = p.esq; } p.esq = aux.esq; return p2; } } else if (aux.num < num) { aux.dir = excluir(aux.dir, num); } else { aux.esq = excluir(aux.esq, num); } return aux; } Nas Árvores AVL teremos que depois de excluir parar a função atualizar para recalcular os a profundidade dos nó para que possa ser balanceada, abaixo é mostrador a função atualizar: public static ARVORE atualizar(ARVORE aux) { if (aux != null) { aux.esq = atualizar(aux.esq); if (aux.esq == null) { aux.alte = 0; } else if (aux.esq.alte > aux.esq.altd) { aux.alte = aux.esq.alte + 1; } else { aux.alte = aux.esq.altd + 1; } aux.dir = atualizar(aux.dir); if (aux.dir == null) { aux.alte = 0; } else if (aux.dir.alte > aux.dir.altd) { aux.altd = aux.dir.alte + 1; } else { aux.altd = aux.dir.altd + 1; } aux = balanceamento(aux); } return aux; } Segue um exemplo que algoritmo usando Árvores AVL para fazer a exclusão de um número: public class ArvoreAVLv2 { private static class ARVORE { public int num, altd, alte; public ARVORE dir, esq; } public static ARVORE inserir(ARVORE aux, int num) {
Por Ayrton Yagami
ARVORE novo; if (aux == null) { novo = new ARVORE(); novo.num = num; novo.altd = 0; novo.alte = 0; novo.esq = null; novo.dir = null; aux = novo; } else if (num < aux.num) { aux.esq = inserir(aux.esq, num); if (aux.esq.altd > aux.esq.alte) { aux.alte = aux.esq.altd + 1; } else { aux.alte = aux.esq.alte + 1; } aux = balanceamento(aux); } else { aux.dir = inserir(aux.dir, num); if (aux.dir.altd > aux.dir.alte) { aux.altd = aux.dir.altd + 1; } else { aux.altd = aux.dir.alte + 1; } aux = balanceamento(aux); } return aux; } public static ARVORE balanceamento(ARVORE aux) { int d, df; d = aux.altd - aux.alte; if (d == 2) { df = aux.dir.altd - aux.dir.alte; if (df >= 0) { aux = rotacao_esquerda(aux); } else { aux.dir = rotacao_direita(aux.dir); aux = rotacao_esquerda(aux); } } else if (d == -2) { df = aux.esq.altd - aux.esq.alte; if (df <= 0) { aux = rotacao_direita(aux); } else { aux.esq = rotacao_esquerda(aux.esq); aux = rotacao_direita(aux); } } return aux; } public static ARVORE rotacao_esquerda(ARVORE aux) { ARVORE aux1, aux2; aux1 = aux.dir;
Por Ayrton Yagami
aux2 = aux1.esq; aux.dir = aux2; aux1.esq = aux; if (aux.dir == null) { aux.altd = 0; } else if (aux.dir.alte > aux.dir.altd) { aux.altd = aux.dir.alte + 1; } else { aux.altd = aux.dir.altd + 1; } if (aux1.esq.alte > aux1.esq.altd) { aux1.alte = aux1.esq.alte + 1; } else { aux1.alte = aux1.esq.altd + 1; } return aux1; } public static ARVORE rotacao_direita(ARVORE aux) { ARVORE aux1, aux2; aux1 = aux.esq; aux2 = aux1.dir; aux.esq = aux2; aux1.dir = aux; if (aux.esq == null) { aux.alte = 0; } else if (aux.esq.alte > aux.esq.altd) { aux.alte = aux.esq.alte + 1; } else { aux.alte = aux.esq.altd + 1; } if (aux1.dir.alte > aux1.dir.altd) { aux1.altd = aux1.dir.alte + 1; } else { aux1.altd = aux1.dir.altd + 1; } return aux1; } public static void exibiremordem(ARVORE aux) { if (aux != null) { exibiremordem(aux.esq); System.out.print(aux.num + ", "); exibiremordem(aux.dir); } } public static void exibirpreordem(ARVORE aux) { if (aux != null) { System.out.print(aux.num + ", "); exibirpreordem(aux.esq); exibirpreordem(aux.dir); }
Por Ayrton Yagami
} public static void exibirposordem(ARVORE aux) { if (aux != null) { exibirposordem(aux.esq); exibirposordem(aux.dir); System.out.print(aux.num + ", "); } } public static ARVORE excluir(ARVORE aux, int num) { ARVORE p, p2; if (aux.num == num) { if (aux.esq == aux.dir) { return null; } else if (aux.esq == null) { return aux.dir; } else if (aux.dir == null) { return aux.esq; } else { p2 = aux.dir; p = aux.dir; while (p.esq != null) { p = p.esq; } p.esq = aux.esq; return p2; } } else if (aux.num < num) { aux.dir = excluir(aux.dir, num); } else { aux.esq = excluir(aux.esq, num); } return aux; } public static ARVORE atualizar(ARVORE aux) { if (aux != null) { aux.esq = atualizar(aux.esq); if (aux.esq == null) { aux.alte = 0; } else if (aux.esq.alte > aux.esq.altd) { aux.alte = aux.esq.alte + 1; } else { aux.alte = aux.esq.altd + 1; } aux.dir = atualizar(aux.dir); if (aux.dir == null) { aux.alte = 0; } else if (aux.dir.alte > aux.dir.altd) { aux.altd = aux.dir.alte + 1; } else { aux.altd = aux.dir.altd + 1; } aux = balanceamento(aux);
Por Ayrton Yagami
} return aux; } public static boolean consultar(ARVORE aux, int num, boolean loc) { if (aux != null && loc == false) { if (aux.num == num) { loc = true; } else if (num < aux.num) { loc = consultar(aux.esq, num, loc); } else { loc = consultar(aux.dir, num, loc); } } return loc; } public static void main(String[] args) { ARVORE a = null; a = inserir(a, 1); a = inserir(a, 2); a = inserir(a, 3); a = inserir(a, 4); a = inserir(a, 5); System.out.print("EM : "); exibiremordem(a); System.out.println(); System.out.print("PRE : "); exibirpreordem(a); System.out.println(); System.out.print("POS : "); exibirposordem(a); System.out.println(); int num = 2; if (consultar(a, num, false)) { a = excluir(a, num); a = atualizar(a); } System.out.println(); System.out.print("EM : "); exibiremordem(a); System.out.println(); System.out.print("PRE : "); exibirpreordem(a); System.out.println(); System.out.print("POS : "); exibirposordem(a); System.out.println();
Por Ayrton Yagami
a = inserir(a, 2); System.out.println(); System.out.print("EM : "); exibiremordem(a); System.out.println(); System.out.print("PRE : "); exibirpreordem(a); System.out.println(); System.out.print("POS : "); exibirposordem(a); System.out.println(); }}
Exercícios
1) Dados as seguinte árvores binárias monte-as de forma gráfica usando o algoritmo de
árvores binária e exclua os números indicados: a) Dada a seguinte inserção: 1, 2, 3, 4, 5, 6, 7, 8 e 9, exclua o nó 3
R:
b) Dada a seguinte inserção: 43, 1, 56, 21, 16, 14, 72, 38 e 46 , exclua o nó 56 e depois exclua o nó 14.R:
2) Dados as seguinte árvores binárias monte-as de forma gráfica usando o algoritmo de árvores AVL e exclua os números indicados:
a) Dada a seguinte inserção: 13, 3, 23, 64, 1, 65, 7, 32 e 6 , exclua o nó 65
R:
b) Dada a seguinte inserção: 23, 4, 1, 5, 21, 46, 78, 81 e 20 , exclua o nó 4 e depois exclua o nó 20.R:
Por Ayrton Yagami
Por Ayrton Yagami
