Jump to content
Baderous

Inserção numa árvore binária de procura

Recommended Posts

Baderous

Estou a tentar criar uma árvore binária de procura com esta estrutura:

typedef struct nodo *ABPInt;

struct nodo {
       int valor;
       ABPInt esq, dir;
       };

Para inserir, estou a fazer o seguinte:

ABPInt insereABP(ABPInt a, int n) {
       int value;
       ABPInt aux = a, nodo=NULL;
       if (!aux) {
          nodo = (ABPInt)malloc(sizeof(struct nodo));
          if (!nodo)
             return;
          nodo->valor=n;
          nodo->esq=NULL;
          nodo->dir=NULL;
          a=nodo;
          aux=a;
          }
       else {
           value=aux->valor;
           if (n<aux->valor) {
              while (!aux->esq) {
                    value=aux->esq->valor;
                    aux=aux->esq;
                    }
              if (n<value) {
                 nodo = (ABPInt)malloc(sizeof(struct nodo));
                 if (!nodo)
                    return;
                 nodo->valor=n;
                 nodo->esq=NULL;
                 nodo->dir=NULL;
                 aux->esq=nodo;
                 }
              else {
                 nodo = (ABPInt)malloc(sizeof(struct nodo));
                 if (!nodo)
                    return;
                 nodo->valor=n;
                 nodo->esq=NULL;
                 nodo->dir=NULL;
                 aux->dir=nodo;
                  }
              }
           else {
               while (!aux->dir) {
                     value=aux->dir->valor;
                     aux=aux->dir;
                     }
               if (n<value) {
                 nodo = (ABPInt)malloc(sizeof(struct nodo));
                 if (!nodo)
                    return;
                 nodo->valor=n;
                 nodo->esq=NULL;
                 nodo->dir=NULL;
                 aux->esq=nodo;
                 }
               else {
                 nodo = (ABPInt)malloc(sizeof(struct nodo));
                 if (!nodo)
                    return;
                 nodo->valor=n;
                 nodo->esq=NULL;
                 nodo->dir=NULL;
                 aux->dir=nodo;
                   }
           }
           }
       return a;
       }

Ele insere bem quando a árvore está vazia, mas quando já lá tem 1 elemento, arrebenta. Não estou a conseguir resolver, alguém tem sugestões? (Provavelmente, isto está ineficiente...)

Share this post


Link to post
Share on other sites
lesiano

else {
           value=aux->valor;
           if (n<aux->valor) {
              while (!aux->esq) {
                    value=aux->esq->valor;
                    aux=aux->esq;
                    }
              if (n<value) {
                 nodo = (ABPInt)malloc(sizeof(struct nodo));
                 if (!nodo)
                    return;
                 nodo->valor=n;
                 nodo->esq=NULL;
                 nodo->dir=NULL;
                 aux->esq=nodo;
                 }

Aí falta uma chaveta.

Share this post


Link to post
Share on other sites
Rui Carlos

E que tal fazer uma versão recursiva da função? Simplificava as coisas :P

Acho que este ciclo

while (!aux->esq) {
  value=aux->esq->valor;
  aux=aux->esq;
}

não faz sentido, pois o facto de n ser menor do que a raiz não implica que seja menor que todos os outros elementos. Logo, não faz sentido fazer aux=aux->esq sempre.

Share this post


Link to post
Share on other sites
vitortomaz

e debug já fizeste?

while (!aux->esq) {

                    value=aux->esq->valor;

                    aux=aux->esq;

                    }

isto é suposto fazer o quê ?

Share this post


Link to post
Share on other sites
vitortomaz

something like this  :P

int Retrieve(TreeNode* tree, ItemType& item, bool& found, int& num)
// Recursively searches tree for item.
// Post: If there is an element someItem whose key matches item's,
// found is true and item is set to a copy of someItem;
// otherwise found is false and item is unchanged.
{
if (tree == NULL)
{
found = false; // item is not found.
return num=0;
}
else if (item < tree->info)
{
Retrieve(tree->left, item, found, num); // Search left subtree.
num=num+1;
}
else if (item > tree->info)
{
Retrieve(tree->right, item, found, num);// Search right subtree.
num = num+1;
}
else
{
item = tree->info; // item is found.
found = true;
} 
}

Share this post


Link to post
Share on other sites
Baderous

Tentei corrigir a falha que o Rui Carlos apontou e já melhorou, ora vejam se agora está (é que parece-me que se insiro mais do que 3 elementos, o 4º já faz overwrite a uma das folhas):

ABPInt insereABP(ABPInt a, int n) {
       int value;
       ABPInt aux = a, nodo=NULL, aux2 = a;
       if (!aux) {
          nodo = (ABPInt)malloc(sizeof(struct nodo));
          if (!nodo)
             return;
          nodo->valor=n;
          nodo->esq=NULL;
          nodo->dir=NULL;
          a=nodo;
          aux=a;
          }
       else {
           value=aux->valor;
           while (!aux) {
                 aux2=aux;
                 value=aux->valor;
                 if (n<value)
                    aux=aux->esq;
                 else
                     aux=aux->dir;
                     }
           if (n<value) {
              nodo = (ABPInt)malloc(sizeof(struct nodo));
              if (!nodo)
                 return;
              nodo->valor=n;
              nodo->esq=NULL;
              nodo->dir=NULL;
              aux2->esq=nodo;
                 }
           else {
                nodo = (ABPInt)malloc(sizeof(struct nodo));
                if (!nodo)
                   return;
                nodo->valor=n;
                nodo->esq=NULL;
                nodo->dir=NULL;
                aux2->dir=nodo;
                }
           }
       return a;
       }

Também tentei fazer recursivo, mas também acho que não está a dar...

ABPInt insereABP(ABPInt a, int n) {
       ABPInt aux = a, nodo = NULL;
       if (!aux) {
          nodo = (ABPInt)malloc(sizeof(struct nodo));
          if (!nodo)
             return;
          nodo->valor=n;
          nodo->esq=NULL;
          nodo->dir=NULL;
          a=nodo;
          }
       else
           if (n<a->valor)
              insereABP(a->esq,n);
           else
               insereABP(a->dir,n);
       return a;
       }

Share this post


Link to post
Share on other sites
Rui Carlos

Acho que ainda estás a complicar...

Repara que quando tens aux a NULL, já sabes o que tens a fazer, certo? É aquele primeiro bloco.

Logo, antes apenas precisas de pôr aux a NULL. Assim, a função penso que se pode reduzir ao ciclo que só para quando aux é NULL, e ao bloco que insere o novo elemento (depois há ali um pormenor que é capaz de trazer um pequena dificuldade).

No recursivo, falta-te fazer a->esq=insereABP(a->esq,n); (e o mesmo para a direita).

Share this post


Link to post
Share on other sites
Baderous

Acho que ainda estás a complicar...

Repara que quando tens aux a NULL, já sabes o que tens a fazer, certo? É aquele primeiro bloco.

Logo, antes apenas precisas de pôr aux a NULL. Assim, a função penso que se pode reduzir ao ciclo que só para quando aux é NULL, e ao bloco que insere o novo elemento (depois há ali um pormenor que é capaz de trazer um pequena dificuldade).

Já consegui meter a minha versão a funcionar. O erro estava no while(!aux), que deveria ser while(aux):

ABPInt insereABP(ABPInt a, int n) {
       int value;
       ABPInt aux = a, nodo=NULL, aux2 = a;
       if (!aux) {
          nodo = (ABPInt)malloc(sizeof(struct nodo));
          if (!nodo)
             return;
          nodo->valor=n;
          nodo->esq=NULL;
          nodo->dir=NULL;
          a=nodo;
          aux=a;
          }
       else {
           value=aux->valor;
           while (aux) {
                 aux2=aux;
                 value=aux->valor;
                 if (n<value)
                    aux=aux->esq;
                 else
                     aux=aux->dir;
                     }
           if (n<value) {
              nodo = (ABPInt)malloc(sizeof(struct nodo));
              if (!nodo)
                 return;
              nodo->valor=n;
              nodo->esq=NULL;
              nodo->dir=NULL;
              aux2->esq=nodo;
                 }
           else {
                nodo = (ABPInt)malloc(sizeof(struct nodo));
                if (!nodo)
                   return;
                nodo->valor=n;
                nodo->esq=NULL;
                nodo->dir=NULL;
                aux2->dir=nodo;
                }
           }
       return a;
       }

Também já consegui fazer como estavas a dizer Rui Carlos:

ABPInt insereABP(ABPInt a, int n) { //Versão iterativa simplificada
       int value;
       ABPInt aux = a, nodo=NULL, aux2 = a;
       while (aux) {
             aux2=aux;
             value=aux->valor;
             if (n<value)
                aux=aux->esq;
             else
                 aux=aux->dir;
                 }
       if (!aux) {
          nodo = (ABPInt)malloc(sizeof(struct nodo));
          if (!nodo)
             return;
          nodo->valor=n;
          nodo->esq=NULL;
          nodo->dir=NULL;
          if (aux==a) {
             a=nodo;
             aux=a;
             }
          else
              if (n<value)
                 aux2->esq=nodo;
              else
                  aux2->dir=nodo;
          }
       return a;
       }

No recursivo, falta-te fazer a->esq=insereABP(a->esq,n); (e o mesmo para a direita).

Era isso mesmo, já funciona.

Obrigado. :P

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.