[JAVA] Albero binario: contare il numero di nodi a una certa profondità

[adp]

salve ragazzi, per favor emi aiutate? devo fare un esercizio che in un albero binario conta il numero di nodi ad altezza k:
public static <E> int contanodi(BinaryTree<E> T, int k)
il mio albero è cosatruito cosi:

/*L'albero usato per il II test e`
* 
*                              2
*                        /           \
*                       2             8    (profondità 1)
*                     /  \           /  \   
*                    1    3          4  2     (profondità 2)
*                         |           |  /\ 
*                         6           7  2 11		  (profondità 3)
*                         /\              
*                        2  8            	   (profondità 4)
*Il programma deve stampare:

	T e` l'albero disegnato in alto

	il numero di nodi a profondita 0=1
	il numero di nodi a profondita 1=2
	il numero di nodi a profondita 2=4
	il numero di nodi a profondita 3=4
	il numero di nodi a profondita 4=2
*/
public class ExBinaryTree_12_11 {
	public static void main(String[] args){
		
		ExamBinaryTree <String>T= new ExamBinaryTree<String>();
T.examAddRoot("2");
T.examExpandExternal(T.root(), "2", "8");
T.examExpandExternal(T.left(T.root()),"1","3");
T.examExpandExternal(T.right(T.root()),"4","2");
T.examInsertRight(T.left(T.right(T.root())),"7");
T.examExpandExternal(T.right(T.right(T.root())),"2","11");
T.examInsertRight(T.right(T.left(T.root())),"6");
T.examExpandExternal(T.right(T.right(T.left(T.root()))),"2", "8");
System.out.println("I test: l'albero e` vuoto");
 int num= countNodes(T,2);//mi dovrebbe stampare 4
System.out.println("I numero di nodi a profontita' d sono:"+ num); 
	}

grazie 10000

[satifal]

Non vedo l'implementazione del metodo countNodes() e neanche della classe ExamBinaryTree.

[adp]

ho impostato una soluzione del genere:

public static <E> int  countNodes(BinaryTree<E> T,int d){
	return countNodes(T,T.root(),d,0);
}
public static <E> int  countNodes(BinaryTree<E> T,Position<E>nodo,int d,int count){
	int num=1;
	if(T.isEmpty()){		
		return 0;
	}
	else{	
		if(count==d)
		  return num;
		else
			num=num+1;
			for(Position<E>figlio:T.children(nodo)){				
				countNodes(T,figlio,d,count+1);	
	}
	return num;

ma nn funziona ricorsivamente, quindi nn mi da i valori giusti, qualcuno sala soluzione??

[adp]

ragazzi, in questa lunga giornata ho provato e riprovato, e so arrivato a questa soluzione

public static <E> int  countNodes(BinaryTree<E> T,int d){	
	return countNodes(T,T.root(),d,0);
}
public static <E> int  countNodes(BinaryTree<E> T,Position<E>nodo,int d,int count){
	int num=0;
		if(T.isEmpty()){
		     return 0;
		 }
		else{
		 if(count==d)
			 return num=+1;
     	 else
		 for(Position<E>figlio:T.children(nodo)){
		 num=num+countNodes(T,figlio,d,count+1);
		 }
		return num;

}

c'è un problema pero' , questa soluzione funziona solo fino al livello 2, cioè se kiamo la funzione (T,2) mi restituisce 4, se la chiamo con (T,3) mi da errore dicendo che l'albero è vuoto, è strano xchè anche a profondita 3 ci sono 4 nodi, sapete dirmi come mai?

[VincenzoTheBest]

Ti consiglio di seguire l'esempio che ti vado a scrivere:
Supponi di avere il seguente albero come istanza

                  a
        -------|--------
        |                   |
        b                   c
     --|--              --|--
    |      |             |     |
   d       e            f      g

quindi ha 3 livelli.
Suppongo che l'interfaccia della struttura dati presenti due operatori
sin(node) e des(node) che hanno la funzione di restituire rispettivamento il figlio sinistro e quello destro di node, ma questo non è una questione centrale.

Fissando che ti avvali di una struttura lineare di appoggio P e di una variabile k che indica il livello corrente di scansione, allora dovresti considerare i seguenti passi:

T; //istanza di albero bin
P; //istanziato e inizialmente vuoto
k = 1;
n = 0; //conta nodi
P.ins(a);

passi eseguiti finchè P non è vuoto..

   estrai e rimuovi il primo nodo aggiunto;
   n = n + 1;
   P.ins( T.sin(a) ); P.ins( T.des(a) );
   => P[b, c]

   estrai e rimuovi il primo nodo aggiunto;
   n = n + 1;
   n == 2^k { 
         a questo livello k, ci sono esattamente |P|+1 nodi;
         k = k + 1;
   }
   P.ins( T.sin(b) ); P.ins( T.des(b) );
   => P[c, d, e]

   estrai e rimuovi il primo nodo aggiunto;
   n = n + 1;             
   P.ins( T.sin(c) ); P.ins( T.des(c) );
   => P[d, e, f, g]

   estrai e rimuovi il primo nodo aggiunto;
   n = n + 1;
   n == 2^k { 
         a questo livello k, ci sono esattamente |P|+1 nodi;
         k = k + 1;
   }
   P.ins( T.sin(d) ); P.ins( T.des(d) ); //non inserisci in quanto nulli
   => P[e, f, g] 

   ...per il livello 3 nulla verrà notificato in quanto la procedurà stopperà
   esattamente per n = 7.

Tieni presente che un albero binario al k-esimo livello dovrebbe avere 2^k nodi, da questo calcolo esce fuori il mio algoritmo.
Adesso sta a te trovare la giusta implementazione, anche se il tuo dato astratto albero utilizza un metodo alternativo agli operatori sin e des.