INF1010 - Exercícios: Árvores Binárias de Busca e AVL

Parte 1: usando a implementação de mapa por árvores binárias de busca genéricas

Use os arquivos arvore.h, mapa.h, mapa_abb.c e teste_abb.c para fazer essa parte dos exercícios. (Ou use a sua implementação de árvores binárias de busca.)

1. Implemente a função mostra_chaves_decrescentes, que imprime, em ordem decrescente as chaves armazenadas nos nós da árvore.

   void mostra_chaves_decrescentes (Mapa *m);
   

2. Implemente a função e_abb, que verifica se uma árvore binária é uma árvore binária de busca, ou seja, se para cada nó n da árvore, as chaves na sua subárvore da esquerda são todas menores do que a chave de n, e as chaves na sua subárvore da direita são todas maiores.

   Uma ideia é usar uma função interna e_abbr, com dois parâmetros, min e max, que indicam os valores mínimo e máximo permitidos na subárvore a ser visitada em cada chamada recursiva.

   static int e_abbr (Mapa *m, int min, int max);
   
   /* INT_MIN e INT_MAX são, resperctivamente, o menor e o maior inteiro
      representáveis na máquina utilizada */
   int e_abb(Mapa *m) {
     return e_abbr(m, INT_MIN, INT_MAX);
   }
   

3. Implemente a função chavek que retorna a k-ésima menor chave do mapa. Se a árvore contiver menos do que k chaves, a função deve retornar -1.

   Novamente, a ideia é usar uma função interna, chavek_rec. Essa função recebe mais um parâmetro, um ponteiro para uma variável que que indica a "ordem" da última chave encontrada. Note que, quando esse valor chegar a k, você já tem a chave procurada.

   Dica: Repare que a k_ésima menor chave pode estar na subárvore esquerda ou na subárvore direita de um nó! (Desenhe uma árvore com alguns nós e experimente...)

   static int chavek_rec(Mapa *m, int k, int *ordem);
   
   int chavek (Mapa* m, int k) {
     int ordem = 0;
     int chave = chavek_rec(m, k, &ordem);
     if (ordem < k) return -1;
     return chave;
   }
   

   
   
   

   Parte 2: usando a implementação de mapa por árvores AVL

   Para essa parte você usará os arquivos arvore_avl.h, mapa.h, mapa_avl.c e teste_avl.c. (Ou use a sua implementação de árvores AVL.)
   1. Escreva uma função não recursiva para calcular a altura de uma árvore AVL.

      int altura_iter (Mapa *m);
      

   2. Note que a representação da árvore (a estrutura smapa) foi estendida e agora mantém, para cada nó, um campo chamado num_nos, que contém a soma do número de nós das suas duas subárvores. Altere suas funções de inserção e de ajuste (rotaciona) para que gerenciem esse campo, mantendo-o correto.

      Repare que a função mostra foi alterada para mostrar também esse campo, assim você pode usar o programa de teste para verificar se o valor está correto para todos os nós da árvore criada.