[JAVA] metodo alberi che conta i numeri uguali

[8paolo9]

Ciao a tutti, ho sempre la mia classe Binary tree e la classe Binary Nodo. Sta volta la classe BinaryNodo è composta dai seguenti campi:

int dato;
Nodo left;
Nodo right;
int contDouble;


Devo fare un metodo che scorre l'albero e ogni volta che incontro un Nodo con lo stesso valore devo incrementare il contDouble. Il mio probelma penso che sia che ogni qualvolta che dealloco lui vede il dato uguale e quindi incrementa sempre.


Questo è un esempio di come dovrebbe lavorare il metodo:

[IMG]

[/IMG]



Questo è il mio codice:

//CLASSE BINARY TREE

public void countDupl () { 
	if (root == null)
		throw new RuntimeException ("Albero vuoto");
	else
		root.countDupl();
}


//CLASSE BINARY NODE

public int countDupl () {
	if (left != null) {
		if (left.dato == dato)
			contDouble = left.contDouble+1;
		contDouble += left.countDupl();
	}
	if (right != null) {
		if (right.dato == dato)
			contDouble = right.contDouble+1;
		contDouble += right.countDupl();
	}
	return contDouble;
	}
}

Grazie!!

[desa]

E' proprio l'algoritmo a essere sbagliato.
E' abbastanza complicato spiegare a parole perchè (forse delle System.out organizzate opportunamente potrebbero esserti d'aiuto)... diciamo però che le questioni principali sono 2:
- esplorando ricorsivamente l'albero ti "perdi" il valore che stavi analizzando;
- se, come nel ramo sinistro dell'albero di esempio che hai postato, il dato presente in un nodo è diverso da quello del suo figlio, la "catena" di incrementi che hai costruito ricorsivamente si spezza.

In generale, non vedo proprio come tu possa impostare correttamente tutti i countDouble in un'unica passata ricorsiva. La prima soluzione che mi viene in mente è: PER OGNI NODO "n" dell'albero (a partire dalla root), se il suo countDouble è uguale a 0 visiti il sottoalbero di cui "n" è radice fino ad arrivare ai nodi foglia. Da qui, risali all'indietro fino a "n", incrementando correttamente tutti i nodi che incontri sul cammino e che contengono lo stesso dato di "n".

Un po' arzigogolato da scrivere, ma prova a pensare se può essere una soluzione valida!