Estruturas de Dados - Árvores (Koike)

Prévia do material em texto

Árvores
Estruturas de Dados
Profa. Carla Koike
   
Listas encadeadas 
são estruturas 
lineares: como 
incluir hierarquias?
   
TAD Árvore
● Árvores consistem de nós e arcos:
– raiz, no topo, é um nó que tem ancestrais
– folhas, na base, são nós que não tem filhos
   
Definição recursiva
● Uma árvore é uma coleção de nós
● A coleção pode estar vazia, ou consistir de um 
nó raiz R
● Existe um arco direcionado de R para   a raiz 
de cada subárvore: a raiz de cada subárvore é 
chamada de filho de R, e R é o pai da raiz de 
cada subárvore.
   
Nó raiz da árvore
Subárvore 
de raiz B
Subárvore 
de raiz C
   
Características das Árvores
● Cada nó pode ser atingido a partir da raiz, através de 
uma seqüência única de arcos, chamada de caminho
● O número de arcos no caminho é chamado de 
comprimento do caminho
● O nível de um nó é o comprimento do caminho da raiz 
até o nó mais um, que é o número de nós no caminho.
● A altura de uma árvore não vazia é o nível máximo de 
um nó na árvore.
   
Características das Árvores, cont.
Nível 1: raiz
Nível 2: B,C,D e E
Nível 3: F, G, H
Nível 4: I
Altura da árvore: 4
   
Árvores Binárias
● Conjunto finito de elementos que está vazio ou 
pode ser particionado em três subonjuntos 
disjuntos:
– raiz, um subconjunto que possui um único 
elemento
– Subárvore esquerda, que é uma árvore binária; e
– Subárvore direita, também uma árvore binária
   
Diferentes Árvores Binária
   
Diferenças: Árvores e 
Árvores Binárias
● Os nós de uma árvore binárias não podem ter 
mais de dois filhos, enquanto não há limites 
para o número de filhos de uma árvore
● A árvore binária tem os filhos ordenados 
segundo um certo critério
   
Árvore Binária como Lista 
Encadeada
struct Node *root;
typedef long TipoChave;
typedef struct Registro {
  TipoChave Chave;
  /* outros componentes */
} Registro;
typedef struct No * Apontador;
typedef struct No {
  Registro Reg;
  Apontador Esq, Dir;
} No;
typedef Apontador TipoDicionario;
   
Busca em uma árvore binária
● Como os elementos da árvore binária estão 
ordenados, a busca na árvore faz uso de um 
algoritmo simples:
– compare o elemento com a raiz: se for igual, pare a 
busca; se for menor, vá para a subárvore da 
esquerda; se for maior, vá para a subárvore da 
direita
   
void Pesquisa(Registro *x, Apontador *p)
{ if (*p == NULL) 
  { printf("Erro : Registro nao esta presente 
na arvore\n");
    return;
  }
  if (x­>Chave < (*p)­>Reg.Chave) 
  { Pesquisa(x, &(*p)­>Esq);
    return;
  }
  if (x­>Chave > (*p)­>Reg.Chave)
  Pesquisa(x, &(*p)­>Dir);
  else
    *x = (*p)­>Reg;
} 
Busca em Árvore Binária
   
Aplicação: Encontrando o Número
   
Aplicação: Encontrando Texto
Fiesta
Mercedes
Uno
Courier
Brava
Besta
Parati
   
Percurso de uma árvore binária
● As vezes, é necessário percorrer todos os nós 
da árvore: percurso, transversalização, ou 
caminhamento
● Uma árvore binária pode ser percorrida de três 
formas:
– pré­ordem, percurso em profundidade
– em ordem, ou ordem simétrica
– pós­ordem
   
Pré­ordem, Percurso em 
Profundidade
void Preorder(Apontador *p)
{
  printf("%ld\n",(*p)­>Reg);
  if (&(*p)­>Esq !=NULL)
     Preorder(x, &(*p)­>Esq);
  if (&(*p)­>Dir !=NULL)
     Preorder(x, &(*p)­>Dir);
}
● Visita o nó raiz
● Visita sub­árvore da esquerda
● Visita sub­árvore da direita
   
Pré­ordem, Percurso em 
Profundidade
Ordem de Visita dos Nós:
F B A D C E G I H
   
Em ordem, ou ordem simétrica
void InOrder(Apontador *p)
{
  if (&(*p)­>Esq !=NULL)
     InOrder(x, &(*p)­>Esq);
  printf("%ld\n",(*p)­>Reg);
  if (&(*p)­>Dir !=NULL)
     InOrder(x, &(*p)­>Dir);
}
● Visita sub­árvore da esquerda
● Visita o nó raiz
● Visita sub­árvore da direita
   
Em ordem, ou ordem simétrica
Ordem de Visita dos Nós:
A B C D E F G H I
   
Pós­ordem
void PosOrder(Apontador *p)
{
  if (&(*p)­>Esq !=NULL)
     PosOrder(x, &(*p)­>Esq);
  if (&(*p)­>Dir !=NULL)
     PosOrder(x, &(*p)­>Dir);      
  printf("%ld\n",(*p)­>Reg);
}
● Visita sub­árvore da esquerda
● Visita sub­árvore da direita
● Visita o nó raiz
   
Pós­ordem
Ordem de Visita dos Nós:
A C E D B H I G F
   
Aplicação: Classificação
● Dada uma lista de números em um arquivo d 
entrada, queremos imprimi­los em ordem 
crescente.
● Ex: 14 15 4 9 7 18 3 5 16 4 20 17 9 14 5
● Solução: ao lermos o arquivo, armazenamos os 
números em um árvore binária. Para imprimir, 
basta percorrer a árvore.
   
Aplicação: Classificação
14 15 4 9 7 18 3 5 16 4 20 17 9 14 5
14
154
9
   
Aplicação: Classificação
14 15 4 9 7 18 3 5 16 4 20 17 9 14 5
   
Aplicação: Classificação
Como essa árvore deve ser percorrida para imprimir os números em 
ordem crescente?
   
Aplicação: Expressões contendo 
operadores binários