2

Bom dia, estou tentando criar uma função recursiva que percorra uma árvore binária e encontre o maior inteiro contido nos nós.

A minha ideia é de passar pra função o ponteiro para o nó da árvore, e um ponteiro para inteiro, e esse ponteiro para inteiro ir percorrendo a árvore sendo comparado com os outros dados.

No final, esse ponteiro vai ter o endereço de memória do maior inteiro da árvore, mas quando eu mando printar na main, não dá o retorno certo, a variável maior continua com o mesmo valor que eu inicializei. Alguém pode me dar uma luz? Espero ter explicado com clareza hehe.

A função em questão é a encontraMaior.

#include <stdlib.h>
#include <stdio.h>

typedef int tree_info;
typedef struct no_arvbin * arvbin;
struct no_arvbin {
arvbin esq;
tree_info dado;
arvbin dir;
};

void preordem(arvbin t);
/**Ex 1**/void preordemprintafolha(arvbin t);
/**Ex 2**/void encontraMaior(arvbin t, int *maior);
void criaRaiz (arvbin t);

int main()
{
arvbin a;
a = (arvbin) malloc(sizeof(arvbin));

arvbin b;
b = (arvbin) malloc(sizeof(arvbin));

arvbin c;
c = (arvbin) malloc(sizeof(arvbin));

arvbin d;
d = (arvbin) malloc(sizeof(arvbin));

criaRaiz(a);
criaRaiz(b);
criaRaiz(c);
criaRaiz(d);

a->dado = 6;
b->dado = 3;
c->dado = 2;
d->dado = 4;

a->esq = b;
a->dir = c;

b->esq = d;
int maior;
maior = -1;

encontraMaior(a, &maior);

printf("%d", maior);
return 0;
}

void criaRaiz (arvbin t){
t->esq = NULL;
t->dir = NULL;
}
void preordem(arvbin t){
if(t != NULL){
    printf("%d\n", t->dado);
    preordem(t->esq);
    preordem(t->dir);
}
}
void preordemprintafolha(arvbin t){
if(t != NULL){
    if(t->dir == NULL && t->esq == NULL){
        printf("%d\n", t->dado);
    }
    preordemprintafolha(t->esq);
    preordemprintafolha(t->dir);
}

}
void encontraMaior(arvbin t, int *maior){
/*system("pause\n");
printf("%d ", *maior);
printf(" %p\n", maior);
system("pause");*/
if(t != NULL){
    if(*maior < t->dado){
        maior = &t->dado;
        printf("%p %p", maior, &t->dado);
    }

    encontraMaior(t->esq, maior);
    encontraMaior(t->dir, maior);
}
}

1 Resposta 1

2

Aparentemente, o erro é nessas duas linhas:

            maior = &t->dado;
            printf("%p %p", maior, &t->dado);

Acho que o que você queria era isso:

            *maior = t->dado;

Fazendo-se essa mudança simples, a saída foi 6. Veja aqui funcionando no ideone.


Agora, vou fazer umas sugestões ao seu código.

Esconder que tipos de dados são ponteiros por meio de um typedef não é lá uma das melhores ideias. Sugiro fazer os seus tipos assim:

typedef int tree_info;
typedef struct no_arvbin {
    struct no_arvbin *esq;
    tree_info dado;
    struct no_arvbin *dir;
} arvbin;

E então, arvbin passa a ser o nome que você usa para se referir a struct enquanto que arvbin * é o ponteiro. Em geral, bastaria você substituir arvbin por arvbin *.

Sugiro que a sua função criaRaiz fosse assim:

arvbin *criaRaiz() {
    arvbin t = (arvbin *) malloc(sizeof(arvbin *));
    t->esq = NULL;
    t->dir = NULL;
    return t;
}

Também acho importante você criar uma função para destruir a arvbin:

void destroiArvBin(arvbin *t) {
    if (t == NULL) return;
    destroiArvBin(t->esq);
    destroiArvBin(t->dir);
    free(t);
}

Seu código ficaria assim:

#include <stdlib.h>
#include <stdio.h>

typedef int tree_info;
typedef struct no_arvbin {
    struct no_arvbin *esq;
    tree_info dado;
    struct no_arvbin *dir;
} arvbin;

void preordem(arvbin *t);

/**Ex 1**/
void preordemprintafolha(arvbin *t);

/**Ex 2**/
void encontraMaior(arvbin *t, int *maior);

arvbin *criaRaiz();
void destroiArvBin(arvbin *t);

int main() {
    arvbin *a = criaRaiz();
    arvbin *b = criaRaiz();
    arvbin *c = criaRaiz();
    arvbin *d = criaRaiz();

    a->dado = 6;
    b->dado = 3;
    c->dado = 2;
    d->dado = 4;

    a->esq = b;
    a->dir = c;

    b->esq = d;

    int maior = -1;
    encontraMaior(a, &maior);

    printf("%d", maior);
    destroiArvBin(a);
    return 0;
}

arvbin *criaRaiz() {
    arvbin *t = (arvbin *) malloc(sizeof(arvbin *));
    t->esq = NULL;
    t->dir = NULL;
    return t;
}

void destroiArvBin(arvbin *t) {
    if (t == NULL) return;
    destroiArvBin(t->esq);
    destroiArvBin(t->dir);
    free(t);
}

void preordem(arvbin *t) {
    if (t != NULL) {
        printf("%d\n", t->dado);
        preordem(t->esq);
        preordem(t->dir);
    }
}

void preordemprintafolha(arvbin *t) {
    if (t != NULL) {
        if (t->dir == NULL && t->esq == NULL) {
            printf("%d\n", t->dado);
        }
        preordemprintafolha(t->esq);
        preordemprintafolha(t->dir);
    }
}

void encontraMaior(arvbin *t, int *maior) {
    /*system("pause\n");
    printf("%d ", *maior);
    printf(" %p\n", maior);
    system("pause");*/
    if (t != NULL) {
        if (*maior < t->dado) {
            *maior = t->dado;
            //printf("%p %p", maior, &t->dado);
        }

        encontraMaior(t->esq, maior);
        encontraMaior(t->dir, maior);
    }
}

Veja aqui funcionando no ideone.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .