Essays.club - TCC, Modelos de monografias, Trabalhos de universidades, Ensaios, Bibliografias
Pesquisar

A Estrutura de Dados

Por:   •  6/5/2018  •  2.343 Palavras (10 Páginas)  •  401 Visualizações

Página 1 de 10

...

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

Para encontrar o valor mínimo de uma árvore de busca binária, deve-se buscar o nó que esta localizado na posição mais à esquerda da árvore.

Em contraposição, pra encontrar o valor máximo, deve-se buscar o nó mais à direita.

- Buscar o mínimo em um nó :

- Se o nó possui filho a esquerda então busca return o minimo do filho à esquerda.

- Senão

- Buscar o máximo em um nó :

- Se o nó possui à direita então buscar o máximo no filho à direita.

- Senão retorna o nó.

[pic 6]

def find_minimo(self):

if self.left:

return self.left.find_minimo()

return self

def find_maximo(self):

if self.right:

return self.right.find_maximo()

return self

INSERÇÃO(ADD)

A inserção começa com uma busca, procurando pelo valor, mas se não for encontrado, procuram-se as subárvores da esquerda ou direita, como na busca.

def add(self,node):

if node.key

if self.left is None:

self.left = node

node.parent = self

else:

self.left.add(node)

if node.key >= self.key:

if self.right is None:

self.right = node

node.parent = self

else:

self.right.add(node)

root = BSTNode(10)

root.left = BSTNode(7)

root.right = BSTNode(18)

root.left.left = BSTNode(3)

root.left.right = BSTNode(9)

root.left.left.left = BSTNode(1)

root.left.right.left = BSTNode(8)

root.right.left = BSTNode(11)

REMOÇÃO

A remoção em árvore binária nos faz pensar em 3 situações(casos) primárias em que ela pode ocorrer. Discutiremos essas 3 situações e seus possíveis desmembramentos.

Situação 1 : O nó a ser removido é uma folha.

Antes da Remoção

[pic 7]

Remoção

[pic 8]

Depois da Remoção

[pic 9]

- Este é o caso mais simples;

- A solução é identificar o nó pai é fazer com que a referência as nó a ser iliminado receba nulo.

- Desmembramento da Situação 1

- O nó pode ser um filho a esquerda;

- O nó pode ser um filho à direta;

Situação 2 : O nó possui apenas um filho.

Antes da Remoção

[pic 10]

Remoção

[pic 11]

Depois da Remoção

[pic 12]

- A solução é fazer com que pai do nó eliminado passe a apontar para o único filho do eliminado.

- Não importa que o filho do eliminado seja uma folha ou uma subárvore

- Desmembramento da Situação 1

- O nó pode ser um filho a esquerda;

- O nó pode ser um filho à direta;

Árvore AVL

- Adel'Son – Vel'Sjij – Landis

PROFUNDIDADE

A profundidade de um nó em uma árvore é a quantidade de ancestrais do nó, excluindo-se o próprio nó.

ALTURA

Se o nó é uma folha, então sua altura é 0, em qualquer outro caso, a altura do nó é 1+ a altura máxima dos filhos.

Situação 3 : O nó ser eliminado possuí 2 filhos

Antes da Remoção

[pic 13]

Remoção

[pic

...

Baixar como  txt (15.7 Kb)   pdf (71.9 Kb)   docx (585.3 Kb)  
Continuar por mais 9 páginas »
Disponível apenas no Essays.club