contare elementi presenti in un albero binario

[autista2]

salve ragazzi,

studiando gli alberi binari mi è venuto in mente che sarebbe interessante fare una funzione che ritorni il numero di elementi presenti in un albero binario
solo che non ho la più pallida idea di come si faccia

sul web non riesco a trovare guide riguardo il conteggio degli elementi

potete aiutarmi?

[yorkeiser]

Dipende da cosa vuoi contare.
Se ti interessano i soli nodi foglia, inizializzi un contatore a 0, fai un semplice algoritmo di visita (in preordine, postordine o simmetrica, a tuo piacimento) e per ogni nodo foglia (figlio destro e sinistro = null) incrementi il contatore. Se vuoi contare tutti i nodi, a prescindere dalla tipologia, basta che incrementi il contatore ad ogni nodo visitato

[autista2]

voglio solo contare gli elementi dell'albero quindi foglie e nodi

puoi aiutarmi con un abbozzo di codice C o pseudocodice?

[autista2]

almeno potreste aiutarmi a scrivere codice funzionante per inserire e stampare a video gli elementi dell'albero?

sapreste darmi qualche sito che spiega bene l'argomento, non trovo niente che possa andare bene

[akyra]

mi sembra che yorkeiser ti abbia dato più di un input valido...di fonti ce ne sono una miriade.

Ad esempio in queste slide
ci sono svariati esempi di algoritmi per la visita in preordine,postordine ecc (sia iterativa che ricorsiva)

[autista2]

allora ecco un abbozzo del programma, funziona tutto bene (i vari pre-post-in order) eccetto il calcolo dell'altezza dell' albero

ossia:

1) andrebbe definita la funzione max(alt(T)) e non so farlo
2) anziché implementare la funzione max ho provato a far calcolare l'altezza di uno dei due rami, destro o sinistro solo che il al momento dell' esecuzione riporta il seguente errore il compilatore: SEGMENTATION FAULT...

cmq vi allego il codice e in basso ho evidenziato in blu la parte non funzionante

#include<stdio.h>
typedef int el_type;
typedef enum {false,true} boolean;
typedef struct nodo
{el_type value;
struct nodo *left,*right;} NODO;
typedef NODO *tree;
/* prototipi funzioni ausiliarie */
void showel(el_type);
boolean isless (el_type e1, el_type e2);
boolean isequal (el_type e1, el_type e2);

tree left(tree T);
tree right(tree T);
tree empty(tree T);

tree ordins(el_type,tree);
void inorder(tree);
void preorder(tree);
void postorder(tree);
int alt(tree);

void main (void)
{tree T=0;
el_type n;
do
{printf("\n Dammi un valore intero:\t");
scanf("%d",&n);
T=ordins(n,T);
} while (n!=0);
printf("\n visita in ordine:\n");
inorder(T);
printf("\n visita in preordine:\n");
preorder(T);
printf("\n visita in postordine:\n");
postorder(T);
printf("\n altezza:\n");
alt(T);
}
/* funzioni ausiliarie */
void showel(el_type e)
{ printf("%d \n", e);}
boolean isless (el_type e1, el_type e2)
{ if (e1<e2) return true;
else return false;}
boolean isequal (el_type e1, el_type e2)
{ if (e1==e2) return true;
else return false;}

tree ordins(el_type e,tree t)
{if (t==NULL)
{t=(tree)malloc(sizeof(NODO));
t->value=e;
t->left=NULL;
t->right=NULL;
return t; }
else
{if(isless(e,t->value))
{t->left=ordins(e,t->left);
return t;}
else
{t->right=ordins(e,t->right);
return t;} }
}
void inorder(tree t)
{if(t!=NULL)
{inorder(t->left);
showel(t->value);
inorder(t->right);
}
}
void preorder(tree t)
{if(t!=NULL)
{showel(t->value);
preorder(t->left);
preorder(t->right);
}
}

int alt(tree T)
{if (empty(T))
return 0;
else
return 1+ max(alt(left(T)),
alt(right(T))  );
}

tree empty(tree T)
/* inizializza un albero vuoto */
{ return 0; }

tree left (tree T)
/* restituisce il sottoalbero sinistro */
{ if (empty(T)) return(NULL);
else return(T->left); }
tree right (tree T)
/* restituisce il sottoalbero destro */
{ if (empty(T)) return(NULL);
else return(T->right); }


void postorder(tree T)
{if(T!=NULL)
{postorder(T->left);
postorder(T->right);
showel(T->value);
}
}

[autista2]

ma che tipo di errore è questo <<segmentation fault>>?

[cionci]

Intanto dagli un po' di formattazione a quel programma...altrimenti non credo che qualcuno te lo legga...
Le parentesi si mettono così:

xxxx funzione(xxx par) {
    /* codice della funzione */
}

O

xxxx funzione(xxx par) 
{
    /* codice della funzione */
}

Stessa cosa nei for e negli if...
Inoltre devi indentare il programma con un paio di spazi o con un tab dopo l'apertura di un nuovo blocco...
Non ti offendere...ma raramente ho visto un codice così incomprensibile se non fatto volutamente in maniera incomprensibile...