TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

A Estrutura de Dados

Por:   •  11/12/2016  •  Pesquisas Acadêmicas  •  5.210 Palavras (21 Páginas)  •  316 Visualizações

Página 1 de 21

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ó :

  1. Se o nó possuí um filho á esquerda, então executa-se o “em ordem” no filho á esquerda;
  2. Imprimir a chave do nó;
  3. 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ó:

  1. Imprimir a chave do nó;
  2. Se o nó possui uma filho à esquerda então executa-se o “pré-ordem” nó filho a esquerda;
  3. 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ó:

  1. Se o nó possui um filho à esquerda então executa-se o “pós-ordem” no filho a esquerda;
  2. Se o nó possui em filho á direita então executa-se o “pós-ordem” no nó filho à direita;
  3. Imprimir a chave.

[pic 5]

S={1,3,8,9,7,11,18,10}

                                                                                                                                                                                                                                                                                                

VALORES MÍNIMOS E MAXIMOS

...

Baixar como (para membros premium)  txt (20.2 Kb)   pdf (758.4 Kb)   docx (415.5 Kb)  
Continuar por mais 20 páginas »
Disponível apenas no TrabalhosGratuitos.com