• 0
Sign in to follow this  
Akinase

Arvore binaria (trabalho de facul)

Question

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;
}

Share this post


Link to post
Share on other sites

0 answers to this question

Recommended Posts

There have been no answers to this question yet

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this