INF1010 3WB – T1: Uma aplicação de uma árvore binária de busca: Dicionário de textos (strings).

Enunciado:

Implemente uma classe Dicionario de elementos chave-valor formados por textos (strings), em C++, respeitando o seguinte:

1. Cada chave é única, ou seja, não devem existir elementos com chave repetida. Se o mesmo elemento for inserido mais de uma vez apenas a primeira vez modifica o dicionário. Ao tentar editar ou remover um elemento que não existe, nada acontece. Ao tentar obter um elemento que não existe, a string retornada é vazia.
2. Utilize uma árvore binária de busca para armazenar os elementos utilizando a ordem alfabética das chaves.
3. Utilize a interface mostrada no arquivo t1_dicionario_abb.h para sua classe.
4. É permitido criar funções ou variáveis membro privadas, para facilitar a implementação.

t1_dicionario_abb.h

#ifndef T1_DICIONARIO_ABB_H
#define T1_DICIONARIO_ABB_H

#include <string>

class DicionarioAbb
{
public:
    //Cria um dicionario vazio
    DicionarioAbb();

    //Cria um dicionario com um primeiro elemento
    DicionarioAbb(const std::string &chave, const std::string &valor);

    //Cria um dicionario a partir de outro
    DicionarioAbb(const DicionarioAbb& orig);

    //Destroi o dicionario
    virtual ~DicionarioAbb();

    //Insere um elemento no dicionario
    void insere(const std::string &chave, const std::string &valor);

    //Obtém o valor de um elemento, dada a sua chave
    std::string obtemValor(const std::string &chave);

    //Remove um elemento no dicionario, dada a sua chave
    bool remove(const std::string &chave);

    //Retorna o numero de elementos do conjunto
    unsigned int tamanho();

    //Exibe os elementos do dicionario na ordem lexografica das suas chaves
    void mostra();

    //Exibe a arvore que armazena o dicionario no formato
    //( raiz (sub-arvore a esquerda) (sub arvore a direita) )
    void mostraAbb();

    //Retorna a altura da arvore que armazena o dicionario
    int altura();

private:
    struct AbbNo
    {
        std::string _chave;
        std::string _valor;

        AbbNo* _pai;  // no pai
        AbbNo* _esq;  // sub-arvore a esquerda
        AbbNo* _dir;  // sub-arvore da direita
    };

    AbbNo* _raiz;

    /* Funcoes e membros privados que julgar necessarios */
};

#endif // T1_DICIONARIO_ABB_H

Links úteis:

• Programa para teste main.cpp.
• Casos de teste.