[C++] Esercizio sugli alberi

[Kamui]

Devo risolvere questo problema per domani, ma sono piuttosto fuso (un pomeriggio per fare un programma sulle liste ) e non riesco a trovare una soluzione decente...

Si scriva una funzione NumeroNodi che, ricevendo in ingresso il puntatore alla radice di un albero binario e un intero positivo H, restituisce il numero di nodi NON foglia presenti al livello H nell'albero.

Come dovrei fare? la mia idea sarebbe di fare un ciclo che porti la radice al livello H desiderato... e poi da qui contare quanti nodi non sono foglie. E' giusto?
Ho provato a farlo così il codice, ma mi sa che è abominevole...

Il main è all'incirca così:

int H;
int tot;
cout<<"\n\n\tA che livello vuoi contare i nodi non foglia? ";
cin>> H;
tot=NumeroNodi(radice,H);
cout<<"\n\tAl livello "<<H<<" ci sono "<<tot<<" nodi non foglia";

E questa la funzione...

int NumeroNodi(treenode* p,int level)
{
	int cont=0, contsx=0, contdx=0;
	
	if(p!=NULL)
	{
		for(int i=0; i<=level; i++)
			p=p->dx;
		while(p->dx!=NULL || p->sx!=NULL)
			contdx++;

		for(int j=0; j<=level; j++)
			p=p->sx;
		while(p->dx!=NULL || p->sx!=NULL)
			contsx++;
	}
	
	cont=contdx+contsx;
	return cont;
}

Grazie dell'aiuto

[PunkIvi]

int Nodi(tree T)
{ if ((!T) || (!T->left) || (!T->right)) return 0;
else return 1+Nodi(T->left)+Nodi(T->right);
}

Se passo una foglia non conto altrimenti conto ricorsivamente.

[Kamui]

Bello :bubu:

però mi ritorna sempre 3 nodi non foglia
Perchè mi serve anche sapere a che livello

l'ho scritto così:

int NumeroNodi(treenode* p,int level)
{
if(p!=NULL)
{
	for(int i=0; i<=level; i++)
	if((!p) || (!p->dx) || (!p->sx))
		return 0;
	else
		return 1+NumeroNodi(p->sx,level)+NumeroNodi(p->sx,level);
}
return 0;
}

[PunkIvi]

Perchè mi serve anche sapere a che livello

Cioè? Non capisco che vuoi dire
Il tuo per me non va, non capisco che c'entra il for.

[Kamui]

Il testo dell'esercizio chiede di contare i nodi non foglia a un determinato livello; il for mi serviva per arrivare a quel livello, come l'avevo fatto io prima, ma con questa soluzione non so come arrivare a quel livello sì quel for lì non c'entra nulla

[PunkIvi]

int Nodi(tree T)
{ if ((!T) || (!T->left) || (!T->right)) return 0;
else return 1+Nodi(T->left)+Nodi(T->right);
}

Questa è la mia funzione di prima, e funziona ovunque, basta che gli passi il nodo da cui vuoi cominciare a contare. Nel caso nostro diventa una radice di un sottoalbero, e da lì conta. Non so se mi sono spiegato.

[Kamui]

Sì, ma come glielo passo il nodo da cui voglio iniziare a contare? cioè, come ci arrivo?

[PunkIvi]

Il testo mi pare poco chiaro...
Al livello H non c'è un solo sottoalbero e non è specificato di quale devi calcolare i nodi. Chiedi chiarimenti. Per arrivare al livello ci sono tanti modi, al volo mi vengono in mente le visite pre-order e post-order.

[r0x]

Il for non ha senso, la funzione esce sempre al primo ciclo.

[Kamui]

Originariamente inviato da PunkIvi
Il testo mi pare poco chiaro...
Al livello H non c'è un solo sottoalbero e non è specificato di quale devi calcolare i nodi. Chiedi chiarimenti. Per arrivare al livello ci sono tanti modi, al volo mi vengono in mente le visite pre-order e post-order.

Poco chiaro è dire nulla... ma per farti contento di faccio leggere il testo dell'esercizio sulle liste:

Il software incluso nei registratori di cassa prevede anche la struttura per la memorizzazione di un singolo scontrino per volta. Uno scontrino è un elenco di articoli non noto a priori. Per ogni articolo è noto il nome, il prezzo unitario e la quantità acquistata. Può capitare che l'addetto alla cassa commetta un errore, ad esempio inserisca un numero di pezzi acquistati superiore al reale. In tal caso il cassiere effettua uno storno,ovvero inserisce immediatamente dopo l'articolo il cui numero di pezzi acquistati è errato un nuovo articolo con lo stesso nome e con un numero negativo di pezzi da comprare. Si realizzino le funzioni AggiungiArticolo e StampaConTotale. La prima funzione deve inserire un nuovo articolo nello scontrino su cui si sta operando; mentre la seconda stampa a video tutto lo scontrino (iniziando dal primo articolo inserito) e il totale, ottenuto come somma di tutti gli articoli, sottratti gli eventuali storni.
Esercizio l bis
Si estenda la funziona StampaConTotale indicata nel esercizio l,
immaginando che il cassiere possa correggere in qualsiasi momento
il dato sbagliato, dunque non necessariamente immediatamente dopo averlo inserito. È possibile realizzare direttamente questa funzione senza svolgere la StampaConTotale

il famoso esercizio su cui ho passato tutta la giornata... ma alla fine ce l'ho fatta più o meno

il for non doveva ciclare nulla, solo portarmi al nodo predefinito :master:
cercherò di trovare una soluzione col pre-order allora