As Estruturas de Dados e Algoritmos em Java
Por: jpfer • 6/9/2018 • Dissertação • 14.335 Palavras (58 Páginas) • 352 Visualizações
Aula 4
Árvores Binárias
Referências Bibliográficas
LARORE, Robert. Estruturas de dados e Algoritmos em Java. Rio de Janeiro: Moderna, 2004. Cap VIII.
Arquivos
ClasseVetor_1.java
ClasseVetor_1Main.java
Resumo
- Em vetores, a pesquisa em um vetor binário é rápida, porém a inserção em um vetor ordenado é muito lenta;
- Inserções e eliminações em uma lista encadeada são as mais rápidas a serem executadas, basta alterar algumas referências. Porém, localizar um elemento específico na lista é difícil;
- Árvores fornecem ambas as características (pesquisa de um vetor e inserção/eliminação de uma lista encadeada), tornando-se uma das estruturas de dados mais interessantes.
- Arvore consiste em nós conectados por arestas;
- As linhas (arestas) entre os nós representam o modo como os nós são relacionados.
- Caminho: pense em alguém caminhando de nó em nó nas arestas que os conectam. A seqüência resultante de nós é chamada de caminho.
- Raiz: o nó da parte superior da árvore é chamado de raiz. Há apenas uma raiz em uma árvore. Para uma coleção de nós e arestas serem definidos como uma árvore, tem que haver um (e apenas um) caminho da raiz até qualquer outro nó.
- Pai: qualquer nó (exceto a raiz) tem exatamente uma aresta que sobe para outro nó. O nó acima dele é chamado de pai do nó.
- Filho: qualquer nó pode ter uma ou mais linhas descendo para outros nós. Eses nós de um dado nó são chamados de seus filhos.
- Folha: um nó que não tem filhos é chamado nó folha. Pode haver apenas uma raiz em uma árvore, mas pode haver muitas folhas.
- Subárvore: qualquer nó pode ser considerado como sendo a raiz de uma subárvore, que consiste em seus filhos, nos filhos de seus filhos, etc. Se você pensar em termos de famílias, a subárvore de um nó contém todos os seus descendentes.
- Visitando: um nó é visitado quando o controle do programa chega ao nó, em geral para executar alguma operação (comparar valores, etc.). Passar simplesmente sobre o nó Nodo caminho de um nó para outro não é considerado como visitar o nó.
- Percorrendo: percorrer uma árvore significa visitar todos os nós em alguma ordem especificada. Por exemplo, visitar todos os nós em ordem ascendente do valor-chave.
- Chaves: vimos que um campo de dados em um objeto é geralmente designado a um valor-chave. Esse valor é usado para buscar o item ou executar outras operações nele. Nos diagramas de árvores, quando um círculo representa um nó que mantém um item de dados, o valor-chave do item é geralmente mostrado Nodo círculo.
- Níveis: o nível de um determinado nó refere-se a quantas gerações o nó está da raiz, ou seja, 1 mais a profundidade do seu pai.
- Árvores binárias: se todo nó em um árvore puder ter Nodo máximo dois filhos, a árvore será chamada de árvore binária (árvore binária de busca).
- Os dois filhos de cada nó em uma árvore são chamados de filho à direita e filho à esquerda;
- Em uma árvore binária de busca, o filho à esquerda de um nó tem que ter uma chave menor que seu pai e o filho à direita de um nó tem que ter uma chave maior ou igual ao seu pai.
- Uma analogia – estrutura hierárquica de arquivos em um sistema de computador.
Classes para implementação de uma árvore não balanceada
Árvores não balanceadas são aquelas que possuem a maioria de seus nós em um lado da raiz.
Classe No: primeiro, precisamos de uma classe que represente a estrutura dos nós. Esses objetos contêm os dados que representam os objetos sendo armazenados e também referências para cada um dos dois filhos de um nó.
package arvore; public class Nodo { int codigo; //dado String nome; //dado int idade; //dado Nodo filhoEsq; //filho à esquerda deste nó Nodo filhoDir; //filho à direita deste nó
public void mostraNo(){ { System.out.println("{"+codigo+", "+nome+ ", "+idade+"} "); } } } |
Classe Arvore: precisamos de uma classe a partir da qual instanciamos a árvore dita: o objeto que mantém todos os nós. Ela tem apenas um campo: uma variável Nodo que mantém a raiz, a partir da qual acessamos os demais nós. Possui também os métodos contendo as ações que podemos executar usando uma árvore.
...