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

eMineiro

[Resolvido] Inserção em Árvore Binária Usando Recursividade

6 mensagens neste tópico

Hoje eu estava fazendo uma arvore binária que define do seguinte modo

struct arv {
        int info;
        struct arv* esq;
        struct arv* dir;
};
typedef struct arv Arv;

Então comecei a brincar com a arvore criei alguma funções, dentre elas a função de inserir.O que acontece é que eu produzi minha função sozinho e o compilador não relata erros mas parece que os dados inseridos na arvore não são atualizados.Fui ao wikipedia e vi tal função de inserção e incrivel estava igualzinha a minha com algumas excessões que utilizavam ** que ainda nao sei muito bem manipula-los.

Mesmo testando a função do wikipedia o maldito ainda nao me inseria nada na arvore.

aqui vai então a minha função de inserção:

void arv_insere(Arv *a,int info){
        if (a == NULL){
                Arv* a=(Arv*)malloc(sizeof(Arv));
                a->info = info;
                a->esq = NULL;
                a->dir = NULL;
        }else{
                if (a->info <= info){
                           arv_insere(a->dir, info);
                }
                if (a->info > info){
                           arv_insere(a->esq, info);
                }
        }
}

Aonde foi que eu errei?, a função roda normalmente, porém quando utilizo minha função pertece que tenho absoluta certeza que está certa, me retorna o valor 0, indicando que o numero nao existe(nao pertence) na arvore.

Pra quem quiser saber como eh a função pertence ai está:

int arv_vazia(Arv* a){
        return a == NULL;
}

int arv_pertence(Arv* a, int info){
        if(arv_vazia(a)){
                 return 0;
        }
        return (a->info == info) || arv_pertence(a->esq,info) || arv_pertence(a->dir,info);
}

Aqui está o site da wikipedia, onde tem uma função idêntica a minha mas que também não rodou no programa:

http://pt.wikipedia.org/wiki/%C3%81rvore_de_busca_bin%C3%A1ria#Inser.C3.A7.C3.A3o

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens mesmo que usar o **.

A razão é que, em C, *todos* os parametros de todas as funções são passados por valor, incluindo os "*".

Supondo que o teu main() é

int main(void) {
   struct arv *a_main;
   a_main = NULL;
   arv_insere(a_main, 42);
   /* arv_free() */
   return 0;
}

Quando a função arv_insere() é chamada o `a_main` "deixa de existir". O `a` dentro da função só existe dentro da função e não tem relação nenhuma com `a_main`. Todas as alterações que fizeres ao `a` dentro da função não se reflectem no `a_main`.

Na tua função só tens uma alteração ao `a`, mas é fundamental essa alteração reflectir-se no `a_main`.

Edit: correcção de bug no nome da struct

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Consegui resolver essa história de ponteiro para ponteiro e assim ficou a função final

void arv_insere(Arv **a,int info){
        Arv *aux;
        if (arv_vazia(*a)){
                *a = arv_cria (info,NULL,NULL);
        }else{
                if ((*a)->info <= info){
                        arv_insere(&(*a)->dir, info);
                }else{
                        arv_insere(&(*a)->esq, info);
                }
        }
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Então e o aux? :)

Se o declaras, usa-o que fica o código mais "limpo"

void arv_insere(Arv **a,int info){
        Arv *aux = *a;
        if (arv_vazia(aux)){
                aux = arv_cria (info,NULL,NULL);
        }else{
                if (aux->info <= info){
                        arv_insere(&aux->dir, info);
                }else{
                        arv_insere(&aux->esq, info);
                }
        }
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É eu tinha usado de primeiro e percebi que não precisaria usa-lo hehehehe.....na verdade é melhor evitar criar variaveis atoa, mesmo que o seu programa seja pequeno mas isso te força a acostumar a programar para grandes projetos.

Apesar de eu não entender nada de otimização é uma area que gosto muito e acho interessante pena que meu professor de C só me ensinou algoritimos e nada de otimização, acho que ao decorrer do meu curso eu vou aprendendo

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