• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Baderous

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

9 mensagens neste tópico

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...)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

e debug já fizeste?

while (!aux->esq) {

                    value=aux->esq->valor;

                    aux=aux->esq;

                    }

isto é suposto fazer o quê ?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora