[C] Alberi: stampa in ordine decrescente di occorrenze

[tigerjack89]

Ciao a tutti. Ennesimo problema per me, stavolta con gli alberi.
Il concetto generale degli alberi mi è ben chiaro, avendoli già studiati in java.
Tuttavia, ho ancora dei problemi.

Per esempio, in questo problema devo visualizzare in ordine decrescente di frequenza le stringhe dell'albero.
Ogni nodo è così strutturato

struct tnode
{
	char *word; //la parola da memorizzare
	int count; //il numero di occorrenze della parola
	struct tnode *left; //un puntatore al nodo figlio sinistro
	struct tnode *right; //e uno al destro
};

L'aggiunta di una parola all'albero riesco a gestirla bene, stessa cosa per quanto riguarda la stampa in ordine lessicografico delle parole. L'albero è fatto in modo che ogni nodo sinistro contiene solo parole lessicograficamente minori del nodo padre ed ogni nodo destro quelle maggiori.

Come faccio, a questo punto, a stampare invece non in base all'ordine lessicografico, ma a quello delle occorrenze di una data parola?
Ho provato in vari modi, ma tutti sbagliati :S. Eccone uno; in questo esempio la funzione searchmax cerca il valore massimo nella funzione, treeprintn dovrebbe stampare tutti i valori che hanno n occorrenze, mentre treeprintcount si occupa di passare i giusti valori alla funzione precedente.
Mentre la funzione di ricerca funziona alla perfezione, sulle altre due ho parecchi dubbi; eseguendo il programma, infatti, viene stampato solo il valore massimo.

void treeprintn(struct tnode *p, int n)
{
	if (p != NULL && (p->count) == n)
	{
		printf("%3d %s\n", p->count, p->word);
		treeprintn(p->left, n);
		treeprintn(p->right, n);
	}
}

void treecountprint(struct tnode *p)
{
	int max = searchmax(p, 0);
	int i = 1;
	while (i <= max && p != NULL)
	{
		treeprintn(p, i);
		i++;
	}	
}

int searchmax(struct tnode *p, int max)
{
	if (p != NULL)
	{
		if ((p->count) > max)
			max = p->count;
		max = searchmax(p->left, max);
		max = searchmax(p->right, max);	
	}
	
	return max;
}

Ogni sorta di consiglio o suggerimento è sempre ben accetto

[ramy89]

Puoi fare una visita dfs ricorsiva o iterativa se hai a disposizione una pila.
Durante la visita puoi mettere in un array tutte le occorrenze incontrate nei vari nodi (il valore count).
Alla fine della procedura hai questo array con tutte le occorrenze, lo ordini in senso decrescente.

[tigerjack89]

Originariamente inviato da ramy89
Puoi fare una visita dfs ricorsiva o iterativa se hai a disposizione una pila.
Durante la visita puoi mettere in un array tutte le occorrenze incontrate nei vari nodi (il valore count).
Alla fine della procedura hai questo array con tutte le occorrenze, lo ordini in senso decrescente.

Non so se è quello che intendevi tu, ma ho risolto modificando semplicemente la funzione treeprintn in questo modo

void treeprintn(struct tnode *p, int n)
{
	if (p != NULL)
	{
		if ((p->count) == n)
			printf("%3d %s\n", p->count, p->word);
		treeprintn(p->left, n);
		treeprintn(p->right, n);
	}
}

Ah, il potere di 5 minuti di pausa!!
Grazie mille comunque per l'aiuto. Come avresti implementato tu la funzione?

[ramy89]

Dici:

Per esempio, in questo problema devo visualizzare in ordine decrescente di frequenza le stringhe dell'albero.

Ma questa procedura:

void treeprintn(struct tnode *p, int n)
{
	if (p != NULL)
	{
		if ((p->count) == n)
			printf("%3d %s\n", p->count, p->word);
		treeprintn(p->left, n);
		treeprintn(p->right, n);
	}
}

Stampa solo le parole che hanno n occorrenze.

[tigerjack89]

Originariamente inviato da ramy89
...cut...

E' proprio a questo che servono le altre due funzioni
Cerco prima il valore massimo, poi stampo di volta in volta tutti i nomi, partendo da quelli che hanno valore 1 fino ad arrivare a quelli col valore massimo.

[ramy89]

Certo che non è il massimo della velocità
Quanto è il valore massimo?
Potresti risolvere il tutto anche facendo una sola visita.

[tigerjack89]

Originariamente inviato da ramy89
Certo che non è il massimo della velocità
Quanto è il valore massimo?
Potresti risolvere il tutto anche facendo una sola visita.

Beh il valore massimo dipende da quante volte viene inserita la stessa parola.
In che modo si può fare una sola visita?

[ramy89]

Durante la visita dfs metti tutte le occorrenze in un array di interi.
Poi ordini l' array e stampi le occorrenze.

[tigerjack89]

Originariamente inviato da ramy89
Durante la visita dfs metti tutte le occorrenze in un array di interi.
Poi ordini l' array e stampi le occorrenze.

Mmm. Non riesco a seguirti. Forse perchè non ho idea di come si implementi una visita dfs

[ramy89]

C' è su wikipedia (leggi l' articolo), comunque ti faccio un esempio:

void dfs(struct tnode* p,int v[])
{
    static int i=0;
    if(p!=NULL)
    {
        v[i++]=p->count;
        dfs(p->right,v);
        dfs(p->left,v);
    }
}

Parametri: N numeri degli elementi del grafo, i indice del prossimo nodo da inserire.E' ricorsiva ma si potrebbe anche fare con una pila.
Il grafo è un albero per cui ogni nodo viene visitato una volta.
Ora hai l' array disordinato, e hai chiamato N volte la procedura per ottenere tutti i valori dell' array.
Rimane solo da ordinarlo, se usi il qsort di stdlib.h in totale spendi n+nlogn.