A Estrutura de Dados
Por: Jeferson95 • 11/12/2016 • Pesquisas Acadêmicas • 5.210 Palavras (21 Páginas) • 363 Visualizações
Jeferson
ARVORES
O que é uma Árvores ?
As árvores são estruturas de dados hierárquico nos quais os dados são organizados por “nós”, sendo o primeiro destino chamado de no raiz.
- Cada nó de uma árvore possui um nó pai com exceção do nó raiz e possui nós filhos.
- Os nós que não possuem filho são chamados de folhas.
- Em uma árvore que guarda números inteiros em seus nós.
[pic 1]
O que é uma árvore binaria ?
- Tipo especial de arvore em que cada nó pode ter no máximo 2 filhos, uma à esquerda e uma à direita do nó.
[pic 2]
O que é uma árvore binaria de busca ?
- A árvore binaria de busca é uma estrutura em que cada nó possuí, além de chave e os dados satélites os atributos, esquerda direita e que apontam para as nós correspondentes.
- Se um filho ou pai estiver ausente, o melhor valor ser utilizados é o valor correspondente á validade na linguagem utilizada.
OBS : Se uma árvore existe, então seu nó raiz não pode ser nulo.
PERCUSOS EM ÁRVORES
- Estrutura de dados organizadas em forma de árvores podem nos conceder diversos benefícios computacionais além de uma busca eficiente.
- Alguns destes benefícios são relacionados aos algoritmos conhecidos como percurso em árvores.
- O beneficio que advém destes algoritmos esta relacionado com operações que podem ser realizadas em cada nó da árvore á medida que as percorremos.
- Os algoritmos clássicos de percurso em árvores são :
- Em Ordem;
- Pré – Ordem;
- Pós – Ordem;
Para discutimos, crie a representação gráfica de uma árvore dos seguintes elementos:
[10,7,18,9,9,3,8,1,11]
[pic 3]
EM ORDEM
S={1,3,7,8,9,10,11,18}
EM ORDEM
No algoritmo “Em ordem” realiza-se a operação desejada na raiz entre a realização da operação na sua subárvore à esquerda e a realização de operação na subárvore à direta.
No percurso em Ordem imprime-se a chave raiz após a impressão das chaves da subárvore à esquerda e antes da impressão das chaves da subárvore à direta.
Para executa o “em ordem” em um nó :
- Se o nó possuí um filho á esquerda, então executa-se o “em ordem” no filho á esquerda;
- Imprimir a chave do nó;
- Se o nó possui um filho á direita, então executa-se o “em ordem” nos filho à direita.
ALGORITMO PRE-ORDEM
Para executa o “pré-ordem” em um nó:
- Imprimir a chave do nó;
- Se o nó possui uma filho à esquerda então executa-se o “pré-ordem” nó filho a esquerda;
- Se o nó possui um filho à direita então executa-se o “pré-ordem” no nó filho à direita.
S={10,7,3,1,9,8,18,11} [pic 4]
def pre-order(self):
print(self.key)
if self.left :
self.left.pre-order()
if self.right:
self.right.pre-order()
ALGORITMO DO PÓS-ORDEM
Para executa o “pós-ordem” em um nó:
- Se o nó possui um filho à esquerda então executa-se o “pós-ordem” no filho a esquerda;
- Se o nó possui em filho á direita então executa-se o “pós-ordem” no nó filho à direita;
- Imprimir a chave.
[pic 5]
S={1,3,8,9,7,11,18,10}
VALORES MÍNIMOS E MAXIMOS
...