A Estrutura de Dados
Por: Salezio.Francisco • 6/5/2018 • 2.343 Palavras (10 Páginas) • 481 Visualizações
...
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
...