Implementazione albero binario

di il
11 risposte

Implementazione albero binario

Perchè lanciando il seguente codice:

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


typedef struct elem{
    struct elem* sx;
    struct elem* dx;
    int info;

}node;

typedef node* albero;

main() {
    albero root;
    root=(albero)malloc(sizeof(node));
    root->info = 50;
    root->sx=(albero)malloc(sizeof(node));
    root->sx->info=13;
    root->sx->sx=NULL;
    root->sx->dx = (albero)malloc(sizeof(node));
    root->dx->info = 75;
    root->dx->sx= (albero)malloc(sizeof(node));
    root->dx->dx = NULL;
    root->sx->dx->info = 38;
    printf("%d\n",root->sx->info);

}
Mi appare il seguente errore?
[img]
http://imageshack.com/a/img537/1668/AFwUAj.pn
[/img]

11 Risposte

  • Re: Implementazione albero binario

    Devi controllare che quello che usi sia allocato ...

    Non è così, ad esempio, per

    root->dx->info = 75;

    perché

    root->dx

    non è allocato
  • Re: Implementazione albero binario

    Risolto!
    Grazie mille!!
  • Re: Implementazione albero binario

    Stesso problema precedente, però stavolta richiamando una banale funzione che dovrebbe calcolare l'altezza di un albero binario:
    
    #include <stdio.h>
    #include <stdlib.h>
    
    
    typedef struct elem{
        struct elem* sx;
        struct elem* dx;
        int info;
    
    }node;
    
    typedef node* albero;
    
    int max(int a, int b){
        if (a > b) return a;
        else return b;
    }
    
    int altezza(albero T){
    
        if (T == NULL) return -1;
        else
            return 1 + max(altezza(T->sx),altezza(T->dx));
    
    }
    
    
    main() {
        albero root;
        root=(albero)malloc(sizeof(node));
        root->info = 50;
        root->sx=(albero)malloc(sizeof(node));
        root->sx->info=75;
        root->sx->sx=NULL;
        root->dx=(albero)malloc(sizeof(node));
        root->dx->info = 13;
        root->dx->sx= (albero)malloc(sizeof(node));
        root->dx->dx = NULL;
        root->dx->sx->info = 38;
        root->sx->dx=NULL;
        printf("%d\n",altezza(root));
    
    }
    
    
    Qualche consiglio??
  • Re: Implementazione albero binario

    Esegui il programma linea per linea con il debugger e individua la posizione dell'istruzione che genera l'errore.
  • Re: Implementazione albero binario

    Se gli do in input un albero vuoto ritorna senza problemi -1; il programma si arresta inspiegabilmente appena ho uno o più elementi...
  • Re: Implementazione albero binario

    Hai fatto quello che ti ho consigliato?

    Comunque l'albero non è costruito correttamente ... deve essere
    
    albero root;
    
    root=(albero)malloc(sizeof(node));
    root->info = 50;
    	
    root->sx=(albero)malloc(sizeof(node));
    root->sx->info=75;
    root->sx->sx=NULL;
    root->sx->dx=NULL;
    
    root->dx=(albero)malloc(sizeof(node));
    root->dx->info = 13;
    root->dx->dx = NULL;
    
    root->dx->sx= (albero)malloc(sizeof(node));
    root->dx->sx->info = 38;
    root->dx->sx->sx = NULL;
    root->dx->sx->dx = NULL;
    
    printf("%d\n",altezza(root));
    
  • Re: Implementazione albero binario

    ASSIOMA: la malloc non azzera la memoria allocata.

    Il che vuol dire che 'root->sx' o 'root->dx' potrebbero non essere a zero, e quindi potresti pensare che li c'e' qualcosa di allocato.

    O lo fai tu a mano con una memset, o usi la calloc

    Ed infatto, nel codice di @oregon, corettamente , e' stato fatto a mano.
  • Re: Implementazione albero binario

    Grazie mille ragazzi, impeccabili come sempre!
  • Re: Implementazione albero binario

    Nuovo cruccio:
    devo implementare un programma C che prenda in input un albero binario di caratteri e un carattere. Se tale carattere è una foglia il programma deve creare dinamicamente un stringa che contenga i caratteri che formano il percorso radice-carattere.
    Esempio:
    f
    / \
    a v
    / \ \
    s b r

    invocando il metodo cammino(T,'b') deve restituire un stringa del tipo: "fab/0"
    mentre se gli do: cammino(T,'v') deve restituire NULL
    Ho scritto il seguente codice, ma ahimè mi imbatto nel maledetto segmentation fault
    
    #include "libreria.h"
    
    int esiste_foglia(albero T,char f) {
        if (T==NULL)
            return 0;
        else
            if((T->info==f)&&(T->left==NULL)&&(T->right==NULL))
                return 1;
    
            else return esiste_foglia(T->left,f)|| esiste_foglia(T->right,f);
    
    
    }
    
    int is_leaf(albero T,char c) {
        if (T==NULL)
            return 0;
        else if(T->left==NULL&&T->right==NULL&&T->info==c)
            return 1;
        return is_leaf(T->left,c) || is_leaf(T->right,c);
    }
    
    
    int profondita_foglia(albero T, char c) {
        if (T==NULL || !is_leaf(T,c) || T->info==c)
            return 0;
        else
            if(is_leaf(T->left,c))
                return 1+profondita_foglia(T->left,c);
            else
                if(is_leaf(T->right,c))
                    return 1+profondita_foglia(T->right,c);
    
    
    }
    
    char* cammino(albero T,char c){
    
        int i;
        char* stringa=NULL;
        int p;
        if(T==NULL || !is_leaf(T,c))
            return 0;
    
        else
            p=profondita_foglia(T,c);
            stringa=calloc(p+2,sizeof(char));
            i=0;
            cammino_aux(T,stringa,c,&i);
            return stringa;
    
    }
    
    
    
    
    void cammino_aux(albero T,char* s,char c,int* i) {
    
    
        if(T->info==c) {
            s[*i]=c;
            *i=*i+1;
            s[*i]='\0';
        }
        else
            if (is_leaf(T->left,c)){
                s[*i]=T->info;
                *i=*i+1;
                cammino_aux(T->left,s,c,*i);
            }
            else {
                if (is_leaf(T->right,c)){
                    s[*i]=T->info;
                    *i=*i+1;
                    cammino_aux(T->right,s,c,*i);
    
                }
            }
    }
    
    Consigli? Suggerimenti? Insulti?
  • Re: Implementazione albero binario

    Nuovo cruccio nuovo thread...
  • Re: Implementazione albero binario

    Okappa!!
Devi accedere o registrarti per scrivere nel forum
11 risposte