[C]Stampare tutti i cammini radici foglie

[emperoraugust]

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]

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]

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]

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.