Arvore binaria (trabalho de facul)

[Akinase]

Tenho um trabalho do qual esta me dando trabalho, ashuahsha

a descrição é a seguinte:

Definição do trabalho Este trabalho consiste em implementar um protótipo de rede social utilizando a estrutura de dados árvore binária de busca. O sistema permitirá o cadastramento de pessoas e suas amizades. Cada pessoa possuirá um nome, um id e um conjunto de amizades. O id é um identificador inteiro único. O nome é o nome da pessoa. O conjunto de amizades é constituído dos ids das pessoas com as quais a pessoa possui algum tipo de relação de amizade. Pessoas serão armazenadas em uma árvore binária de busca em que a chave de cada nó será o id da pessoa correspondente. O conjunto de amizades de uma pessoa será representado por uma outra árvore binária de busca. Os nós desta árvore armazenam apenas o id de cada amigo, que também é usado como chave para a organização da árvore. Em resumo, o sistema armazenará uma árvore binária de busca de pessoas. Cada pessoa possuirá uma árvore binária de busca com suas amizades. O sistema deverá suportar as seguintes operações:

1. Inserção. Permite cadastrar uma nova pessoa no sistema.

2. Remoção. Permite remover uma pessoa do sistema, dado seu id.

3. Busca. Recebe o id de uma pessoa e caso a pessoa esteja no sistema, exibe suas informações e também suas amizades.

4. Cadastrar amizade. Recebe o id de duas pessoas e, caso ambas estejam cadastradadas no sistema e já não sejam amigas, cadastra uma nova amizade entre estas pessoas.

5. Remover amizade. Recebe o id de duas pessoas e, caso ambas estejam cadastradas no sistema e sejam amigas, desfaz a amizade entre as duas pessoas.

6. Consultar amizade. Recebe o id de duas pessoas e diz se existe amizade entre as duas.

7. Caminho de amizade (Bônus). Recebe o id de duas pessoas, P e Q, e, caso as duas estejam no sistema, mostra um possível caminho de amizade entre as duas. Isto é, mostra uma sequência de pessoas p1, p2, …, pn, em que p1 = P e pn = Q e existe uma relação de amizade entre pi e pi-1, para 2 <= i <= n.

 

segue o que eu já fiz:

 

#include <iostream>
#include <string>
//#include "Dicionario.h"
#include "ABB.h"
using namespace std;

class Pessoa
{
public:
    string nome;
    int idade;
    Pessoa();
    Pessoa(string n, int i);
    void Imprime();

};

Pessoa::Pessoa()
{
    nome = "vazio";
    idade = 0;
}

Pessoa::Pessoa(string n, int i)
{
    nome = n;
    idade = i;
}

void Pessoa::Imprime()
{
    cout << nome << "-" << idade << "-" << endl;
}

class Amigos
{
public:
    string nome;
    int idade;
    Amigos();
    Amigos(string n, int i);
    void Imprime();
};

Amigos::Amigos()
{
    nome = "vazio";
    idade = 0;
}

Amigos::Amigos(string n, int i)
{
    nome = n;
    idade = i;
}
int main()
{
    string opcao;
    cin >> opcao;

    Dicionario<int, Pessoa> D;

    while(opcao != "SAIR")
    {
        if(opcao == "INSERIR")
        {
            string nome, lixo;
            int chave;
            int idade;
            cin >> chave;
            getline(cin, lixo);
            getline(cin, nome);
            cin >> idade;
        
                
            Pessoa p(nome, idade);
        
            D.Inserir(chave, p);
        }
                else if(opcao == "INSERIRAMIGO")
        {
                        string nome, lixo;
                        int chave;
                        cout << "DIGITE O ID do amigo RAIZ";
                        cin >> chave;                      
            int chavemigs;
            cout << "DIGITE O ID DO AMIGO A SER INSERIDO";
            cin >> chavemigs;
                      

            
        }
        else if(opcao ==  "BUSCAR")
        {
            int chave;
            cin >> chave;
            Pessoa p = D.Buscar(chave);
            p.Imprime();
        }
        else if(opcao == "REMOVER")
        {
            int chave;
            cin >> chave;
            Pessoa p = D.Remover(chave);
        }
        else if(opcao == "IMPRIMIR")
        {
            D.Imprime();
        }
                
        cin >> opcao;
    }
}
 

#include <iostream>

using namespace std;

template <class T, class U>
class Dicionario;

template <class T, class U>
class No
{
public:
    No(T ch, U co);
    T chave;
    U conteudo;
    No * esquerda, * direita;
        //Dicionario apontando para Amigos();
};

template <class T, class U>
No<T, U>::No(T ch, U co)
{
        chave = ch;
    conteudo = co;
    esquerda = NULL;
    direita = NULL;
        //Criar novo noh migs
}

template <class T, class U>
class Nomigs
{
public:
    Nomigs(T ch, U co);
    T chave;
    U conteudo;
    Nomigs * esquerda, * direita;       
};

template <class T, class U>
Nomigs<T, U>::Nomigs(T ch, U co)
{
        chave = ch;
    conteudo = co;
    esquerda = NULL;
    direita = NULL;
}

template <class T, class U>
class Dicionario
{
public:
    No<T, U> * raiz;
        
    Dicionario();
    void Inserir(T chave, U conteudo);
    void InserirRecursivo(No<T, U> * & anda, T chave, U conteudo);
        void InserirAmigo(T chave, U conteudo);
    void InserirAmizade(Nomigs<T, U> * & anda, T chave, U conteudo);
        
    U Remover(T chave);
    U RemoverRecursivo(No<T, U> * & anda, T chave);
    U Buscar(T chave);
    U BuscarRecursivo(No<T, U> * anda, T chave);
        
    int NumNos(No<T, U> * x);
    int NumFolhas(No<T, U> * x);
    int NosCaminho(No<T, U> * anda, T chave);
    int NumNiveis(No<T, U> * x);

    void Imprime();
    void ImprimeRec(No<T, U> * x);
};

template <class T, class U>
void Dicionario<T, U>::InserirAmigo(T chave, U conteudo)
{
    InserirAmizade(raiz, chave, conteudo);
}

    
    /*template <class T, class U>
void Dicionario<T, U>::InserirAmizade(NoMigs<T, U> * & anda, T chave, U conteudo)
     * 
     * NO1 = Arvore->Buscar(chave1)
    No2 = Arvore->Buscar(chave2)
    No1->Arvore->Inserir(chave2)
    NO2->Arvore->Inseir(chave1)
     */

template <class T, class U>
Dicionario<T, U>::Dicionario()
{
    raiz = NULL;
}

template <class T, class U>
void Dicionario<T, U>::Inserir(T chave, U conteudo)
{
    InserirRecursivo(raiz, chave, conteudo);
}

template <class T, class U>
void Dicionario<T, U>::InserirRecursivo(No<T, U> * & anda, T chave, U conteudo)
{
    if(anda == NULL)
    {
        No<T, U> * novo = new No<T, U>(chave, conteudo);

        anda = novo;
    }

    if(chave == anda->chave)
        return;

    if(chave < anda->chave)
        InserirRecursivo(anda->esquerda, chave, conteudo);

    if(chave > anda->chave)
        InserirRecursivo(anda->direita, chave, conteudo);
}

template <class T, class U>
U Dicionario<T, U>::Buscar(T chave)
{
    return BuscarRecursivo(raiz, chave);
}

template <class T, class U>
U Dicionario<T, U>::BuscarRecursivo(No<T, U> * anda, T chave)
{
    if(anda == NULL)
        return U();

    if(chave == anda->chave)
        return anda->conteudo;

    if(chave < anda->chave)
        return BuscarRecursivo(anda->esquerda, chave);

    if(chave > anda->chave)
        return BuscarRecursivo(anda->direita, chave);
}

template <class T, class U>
U Dicionario<T, U>::Remover(T chave)
{
    return RemoverRecursivo(raiz, chave);
}

template <class T, class U>
U Dicionario<T, U>::RemoverRecursivo(No<T, U> * & anda, T chave)
{
    if(anda == NULL)
        return U();

    if(chave == anda->chave)
    {
        U conteudo = anda->conteudo;
        //Caso 3: 2 Filhos
        if(anda->esquerda != NULL && anda->direita != NULL)    
        {
            //Encontrar maior da esquerda de anda
            No<T, U> * ME = anda->esquerda;
            while(ME->direita != NULL)
                ME = ME->direita;

            T chaveME = ME->chave;
            anda->conteudo = RemoverRecursivo(anda->esquerda, ME->chave);
            anda->chave = chaveME;
        }
        else
        {
            No<T, U> * novoanda;
            //Caso 1: Nó Folha
            if(anda->esquerda == NULL && anda->direita == NULL)    
            {
                novoanda = NULL;
            }
            //Caso 2: 1 Filho (direita)
            else if(anda->esquerda == NULL && anda->direita != NULL)
            {
                cout << "achou caso" << endl;
                novoanda = anda->direita;
            }
            //Caso 2: 1 Filho (esquerda)
            else if(anda->direita == NULL && anda->esquerda != NULL)
            {
                novoanda = anda->esquerda;
            }

            delete anda;
            anda = novoanda;
        }

        return conteudo;
    }
    if(chave < anda->chave)
        return RemoverRecursivo(anda->esquerda, chave);
    else if(chave > anda->chave)
        return RemoverRecursivo(anda->direita, chave);
}

template <class T, class U>
void Dicionario<T, U>::Imprime()
{
    ImprimeRec(raiz);
    cout << "Numero de noh: " << NumNos(raiz) << endl;
    cout << "Numero de niveis: " << NumNiveis(raiz) << endl;
    cout << "Numero de folhas: " << NumFolhas(raiz) << endl;
}

template <class T, class U>
void Dicionario<T, U>::ImprimeRec(No<T, U> * x)
{
    if(x == NULL)
        return;    

    ImprimeRec(x->esquerda);
    cout << x->chave << " ";
    x->conteudo.Imprime();
    ImprimeRec(x->direita);
}

template <class T, class U>
int Dicionario<T, U>::NumNos(No<T, U> * x)
{
    if(x == NULL)
        return 0;

    return 1 + NumNos(x->esquerda) + NumNos(x->direita);
}

template <class T, class U>
int Dicionario<T, U>::NumFolhas(No<T, U> * x)
{
    if(x == NULL)
        return 0;
    if(x->esquerda == NULL && x->direita == NULL)
        return 1;
    return NumFolhas(x->esquerda) + NumFolhas(x->direita);
}

template <class T, class U>
int Dicionario<T, U>::NosCaminho(No<T, U> * anda, T chave)
{
    if(anda == NULL)
        return 0;    

    if(chave == anda->chave)
        return 1;

    if(chave < anda->chave)
        //o nó atual contribui em uma unidade
        //+ o número de nós na esquerda
        return 1 + NosCaminho(anda->esquerda, chave);

    if(chave > anda->chave)
        return 1 + NosCaminho(anda->direita, chave);
}

template <class T, class U>
int Dicionario<T, U>::NumNiveis(No<T, U> * x)
{
    if(x == NULL)
        return 0;

    int ne = NumNiveis(x->esquerda);
    int nd = NumNiveis(x->direita);
    int max;
    if(ne > nd)
        max = ne;
    else 
        max = nd;

    return 1 + max;
}