int conta_foglie(nodo *x){ if(!x) return 0; else{ if((x->left==0) && (x->right==0)) return 1; else return (conta_foglie(x->left))+conta_foglie(x->right)); } }int conta_foglie(nodo *x){ if(!x) return 0; else{ if((x->left==0) && (x->right==0)) return 1; else return (conta_foglie(x->left))+conta_foglie(x->right)); } } Continua a leggere »
Archivio della categoria: C++
Funzione che conta i nodi di un albero
int conta(nodo *x){ if(x) return 1+conta(x->left)+conta(x->right); else return 0; }int conta(nodo *x){ if(x) return 1+conta(x->left)+conta(x->right); else return 0; } Continua a leggere »
Inserisce nell’array c il cammino percorso per trovare il nodo y
int f2(nodo *x, int *y,int *c,int top){ if(!x) return -1; //se l'albero è vuoto ritorno -1 if(x->info==y) return top; if(x->left){ int sx=f2(x->left,y,c,top+1); if(sx!=-1){ c[top]=0; return sx; } } if(x->right){ int dx=f2(x->right,y,c,top+1); if(dx!=-1){ c[top]=1; return dx; } } return (-1); }int f2(nodo *x, int *y,int *c,int top){ if(!x) return -1; //se l'albero è vuoto ritorno -1 if(x->info==y) return top; if(x->left){ int ... Continua a leggere »
Da un array C che contiene un cammino, restituire il nodo corrispondente
nodo *trova(nodo *x, int *C,int lung){ if(!x) return 0; //se l'albero è vuoto ritorno zero if(!lung) return x; if(*C==0) return trova(x->left,C+1,lung-1); //restituisce il puntatore al nodo (della parte sinistra) in cui c'è x else return trova(x->right,C+1,lung-1); //restituisce il puntatore al nodo (della parte destra) in cui c'è x }nodo *trova(nodo *x, int *C,int lung){ if(!x) return 0; //se l'albero è ... Continua a leggere »
Calcolare l’altezza di un albero
int altezza(nodo *x){ if(!x) return -1; //se l'albero è vuoto ritorno -1 else{ int a=altezza(x->left); //vado a sinistra int b=altezza(x->right); //vado a destra if(a>b) return a+1; //sommo 1 ad a return b+1; //sommo 1 ad b } }int altezza(nodo *x){ if(!x) return -1; //se l'albero è vuoto ritorno -1 else{ int a=altezza(x->left); //vado a sinistra int b=altezza(x->right); //vado a destra ... Continua a leggere »
Trovare e restituire un nodo con campo info == y
nodo * trova(nodo *x,char y){ if(!x) return x; //se l'albero è vuoto ritorno zero if(x->info==y) return x; //abbiamo trovato un nodo nodo *z=trova(x->left,y); //cerco a sinistra if(z) return z; //se non abbiamo trovato niente a sinistra guardo a destra return trova(x->right,y); //cerco a sinistra }nodo * trova(nodo *x,char y){ if(!x) return x; //se l'albero è vuoto ritorno zero if(x->info==y) return ... Continua a leggere »
Funzione che stampa il campo info ogni k nodi
int f1(nodo *x, int salta, int k){ if(x){ return salta; salta=f1(x->left,salta,k); salta=f1(x->right,salta,k); if(salta==0){ cout<<x->info; return k-1; }else return salta-1; } //invocazione: int k=3; k=f1(root,k-1,k);int f1(nodo *x, int salta, int k){ if(x){ return salta; salta=f1(x->left,salta,k); salta=f1(x->right,salta,k); if(salta==0){ cout<<x->info; return k-1; }else return salta-1; } //invocazione: int k=3; k=f1(root,k-1,k); Continua a leggere »
Funzioni di stampa nei 3 principali modi di scorrimento
Funzione ricorsiva stampa in ordine prefisso void STAMPA(nodo *root){ if(root){ cout<<root->info<<"("; STAMPA(root->left); cout<<","; STAMPA(root->right); cout<<")"; }else cout<<"_"; }void STAMPA(nodo *root){ if(root){ cout<<root->info<<"("; STAMPA(root->left); cout<<","; STAMPA(root->right); cout<<")"; }else cout<<"_"; } Funzione ricorsiva stampa in ordine infisso Continua a leggere »
Tipi di scorrimento di un albero
Un albero può essere percorso principalmente in 3 modi: Infisso Prefisso Postfisso Infisso A sinistra Nodo A destra Prefisso Continua a leggere »
Creare un albero in C++
Inclusione delle librerie (linux) e del namespace #include <iostream> using namespace std;#include <iostream> using namespace std; La struttura dell’albero che stiamo per realizzare si può trovare di seguito ed è uguale a quella nelle sezioni precedenti. Struttura dell’albero strcut nodo{ char info; nodo *left, *right; nodo(char a=0, nodo *b=0, nodo *c=0){info=a,left=b,right=c;} };strcut nodo{ char info; nodo *left, *right; nodo(char ... Continua a leggere »
Struttura di un albero
La struttura che vedremo è la struttura standard di un’albero realizzato in C++. struct nodo { char info; nodo *left; nodo *right; nodo (char a='\0', nodo *b=0, nodo *c=0){ //COSTRUTTORE info=a; left=b; right=c; } };struct nodo { char info; nodo *left; nodo *right; nodo (char a='\0', nodo *b=0, nodo *c=0){ //COSTRUTTORE info=a; left=b; right=c; } }; Continua a leggere »
Introduzione agli alberi
In informatica gli alberi hanno una struttura un pò strana, nel senso che “crescono” all’inverso, ovvero prima c’è la radice, poi i rami e a seguire le foglie. “Quindi bisogna avere dei concetti giardinaggio”. Vediamo di seguito un esempio di albero: Continua a leggere »