PDA

Visualizza la versione completa : [C]Stampare tutti i cammini radici foglie


emperoraugust
05-02-2013, 13:52
Salve a tutti!

Sto cercando di risolvere il seguente problema:

Scrivere una routine che, dato in imput un puntatore alla radice di un albero binario di caratteri, stampi tutti i cammini radice-foglia.

Io ho usato una struttura del genere:


struct nodo{
char inf;
struct nodo *sx;
struct nodo *dx; };

Ho provato a scrivere la seguente funzione:


struct nodo *stampaCammini(struct nodo *p){
if(p!=NULL){
printf("%c",p->inf);
p->sx=stampaCammini(p->sx);
p->dx=stampaCammini(p->dx);
if(p->sx==NULL && p->dx==NULL)
return(p)
}
else printf("\n");
return(p);
}


però questa funzione mi stampa solo il primo cammino e poi i nodi rimanenti, senza quindi svolgere il compito di stampare tutti i cammini radice-foglia.

Non so come procedere.

Ringrazio in anticipo chiunque abbia la pazienza di aiutarmi!

MItaly
05-02-2013, 15:36
Puoi costruirti una lista linkata sullo stack, da seguire ogni volta che devi stampare tutto un percorso:


struct nodo
{
struct nodo * sx;
struct nodo * dx;
char inf;
};

struct nodoList
{
struct nodo * payload;
struct nodoList * next;
};

void stampaCammini(struct nodo * p)
{
struct nodoList root;
root.next=NULL;
root.payload=p;
stampaCamminiHelper(&root, &root);
}

void stampaCamminiHelper(struct nodoList *prev, struct nodoList * root)
{
struct nodoList node;
node.next=NULL;
prev->next=&node;
if(prev->payload)
{
node.payload=prev->payload->sx;
stampaCamminiHelper(&node, root);
node.payload=prev->payload->dx;
stampaCamminiHelper(&node, root);
if(!prev->payload->sx && !prev->payload->dx)
{
struct nodoList *n=root;
while(n!=NULL)
{
putchar(n->payload->inf);
n=n->next;
}
putchar('\n');
}
}
}

emperoraugust
05-02-2013, 15:56
Grazie tante! :)
Avevo pensato pure di creare uno stack per memorizzare i caratteri ma non riuscivo ad implementare il tutto.

Ora mi studio per bene il tuo codice

MItaly
05-02-2013, 16:17
Originariamente inviato da emperoraugust
Avevo pensato pure di creare uno stack per memorizzare i caratteri ma non riuscivo ad implementare il tutto.

Quella è una soluzione forse più facile (e anche più efficiente), ma, per un'implementazione semplice devi accettare di avere un limite massimo alla profondità dell'albero.

Loading