JAVA: Alberi: conta nodi sinistri multipli di x

**vfldj** · 09-06-2012, 21:16

Ciao!
Ho fatto questo programmino che dovrebbe restituirmi il numero di nodi che hanno il figlio sinistro multiplo del valore che gli passo come parametro.

Esempio:
dato l'albero [/CODE]tree se gli passo 3 come parametro mi deve restituire 2 perchè solo i nodi 17 e 76 hanno figlio sinistro multiplo di 3

codice:

public int contaNodiSinistriMultipli(int x) {
	int cont = 0;
	if (this.dato % 3 == 0)
	     cont = cont + 1;
	if (left != null && right == null) {
	     if (left.dato % x == 0)
		cont = cont + left.contaNodiSinistriMultipli(x) + 1;
	     else
		cont = cont + left.contaNodiSinistriMultipli(x);
	}
	if (left == null && right != null)
		cont = cont + right.contaNodiSinistriMultipli(x);
	if (left != null && right != null) {
		cont = left.contaNodiSinistriMultipli(x) + right.contaNodiSinistriMultipli(x);
	}
	return cont;
}

Il problema è che non funziona, in base agli alberi che gli passo a volte mi restituisce il valore corretto e a volte no...

**vfldj** · 10-06-2012, 09:06

E specialmente.. Perchè non mi va il main?

codice:

public class ProvaBinaryTree {
     public static void main (String[] args) {

     System.out.println("Nodi sx con valori multipli di 3 (tree2): " + tree2.contaNodiConFiglioSinistroMultiplo(3));
      System.out.println();
      }
}

Questo è tree2

**Kaamos** · 10-06-2012, 15:17

Originariamente inviato da vfldj
Ciao!
Ho fatto questo programmino che dovrebbe restituirmi il numero di nodi che hanno il figlio sinistro multiplo del valore che gli passo come parametro.

Esempio:
dato l'albero [/CODE]tree se gli passo 3 come parametro mi deve restituire 2 perchè solo i nodi 17 e 76 hanno figlio sinistro multiplo di 3

codice:

public int contaNodiSinistriMultipli(int x) {
	int cont = 0;
	if (this.dato % 3 == 0)
	     cont = cont + 1;
	if (left != null && right == null) {
	     if (left.dato % x == 0)
		cont = cont + left.contaNodiSinistriMultipli(x) + 1;
	     else
		cont = cont + left.contaNodiSinistriMultipli(x);
	}
	if (left == null && right != null)
		cont = cont + right.contaNodiSinistriMultipli(x);
	if (left != null && right != null) {
		cont = left.contaNodiSinistriMultipli(x) + right.contaNodiSinistriMultipli(x);
	}
	return cont;
}

Il problema è che non funziona, in base agli alberi che gli passo a volte mi restituisce il valore corretto e a volte no...

Non ho capito il tuo algoritmo... perché all'inizio controlli sempre se il valore è multiplo di 3? Non tutti i nodi sono figli sinistri, e tu chiami ricorsivamente la procedura anche sui nodi destri...

Potresti aggiungere un parametro booleano alla procedura, vero se il nodo è un figlio sinistro e falso altrimenti, così il test iniziale per vedere se è multiplo lo fai solo se quel parametro è vero.

Inoltre non ho capito perché, per le chiamate ricorsive, non puoi fare semplicemente così:

codice:

if (left != null)
  cont += left.procedura(x, true);

if (right != null)
  cont += right.procedura(x, false);

Inoltre ho dato per scontato che non avessi modo, dato un nodo, di ottenerne il padre in tempo costante, altrimenti ovviamente la cosa dei booleani è evitabile.

Fra l'altro, per il calcolo del multiplo non basta il modulo ma devi anche considerare il caso di 0, che è multiplo di ogni intero. Se fai 0 % 3 il risultato è 3 e tu non lo conti come multiplo, anche se lo è.

Originariamente inviato da vfldj
E specialmente.. Perchè non mi va il main?

codice:

public class ProvaBinaryTree {
     public static void main (String[] args) {

     System.out.println("Nodi sx con valori multipli di 3 (tree2): " + tree2.contaNodiConFiglioSinistroMultiplo(3));
      System.out.println();
      }
}

Questo è tree2

"Non va" non vuol dire niente e non possiamo aiutarti.
Dà errori di compilazione? Solleva eccezioni o errori durante l'esecuzione? Non restituisce ciò che ti aspetti? Non succede niente?
Da quelle 3 righe non si può dedurre nulla (a parte la mancata dichiarazione ed inizializzazione di tree2 ma non sarà quello il problema).

**vfldj** · 10-06-2012, 16:06

Non ho capito il tuo algoritmo... perché all'inizio controlli sempre se il valore è multiplo di 3? Non tutti i nodi sono figli sinistri, e tu chiami ricorsivamente la procedura anche sui nodi destri...

Si quelle due righe alla fine le avevo tolte.
Li chiamo ricorsivamente anche sui nodi destri perchè magari questi hanno a loro volta dei figli sinistri multipli di 3.

"Non va" non vuol dire niente e non possiamo aiutarti.
Dà errori di compilazione? Solleva eccezioni o errori durante l'esecuzione? Non restituisce ciò che ti aspetti? Non succede niente?
Da quelle 3 righe non si può dedurre nulla (a parte la mancata dichiarazione ed inizializzazione di tree2 ma non sarà quello il problema).

Non va vuol dire che mi da quest'errore:
ProvaBinaryTree.java:197: error: cannot find symbol
System.out.println("Quanti sono i nodi sinistri con valori multiplo di 3 di tree2? " + tree2.contaNodiConFiglioSinistroMultipli(3));
^
symbol: method contaNodiConFiglioSinistroMultipli(int)
location: variable tree2 of type BinaryTree
1 error

Procedura completata con codice di uscita 1

**Kaamos** · 10-06-2012, 16:16

Originariamente inviato da vfldj
Si quelle due righe alla fine le avevo tolte.
Li chiamo ricorsivamente anche sui nodi destri perchè magari questi hanno a loro volta dei figli sinistri multipli di 3.

Si si, contestavo solo il controllo, chiamare ricorsivamente anche sui figli destri ovviamente è giusto, infatti l'ho fatto anche io nelle 4 righe di codice che ho scritto sopra.

Originariamente inviato da vfldj Non va vuol dire che mi da quest'errore:
ProvaBinaryTree.java:197: error: cannot find symbol
System.out.println("Quanti sono i nodi sinistri con valori multiplo di 3 di tree2? " + tree2.contaNodiConFiglioSinistroMultipli(3));
^
symbol: method contaNodiConFiglioSinistroMultipli(int)
location: variable tree2 of type BinaryTree
1 error

Procedura completata con codice di uscita 1

Beh l'errore mi pare chiaro, non trova il metodo contaNodiConFiglioSinistroMultipli(int) nella classe BinaryTree, evidentemente non c'è. Ma se non ci fai vedere come e dove hai scritto questo metodo come possiamo aiutarti?

**vfldj** · 10-06-2012, 16:25

Eccolo..
Grazie per la pazienza..

codice:

public class BinaryTree {

	private BinaryNode root;

	public static class BinaryNode {

        .........

		public int contaNodiConFiglioSinistroMultipli(int x) {
			int cont = 0;
			if (left != null && right == null) {
				if (left.dato % x == 0)
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x) + 1;
				else
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x);
			}
			if (left == null && right != null)
				cont = cont + right.contaNodiConFiglioSinistroMultipli(x);
			if (left != null && right != null) {
				cont = left.contaNodiConFiglioSinistroMultipli(x) + right.contaNodiConFiglioSinistroMultipli(x);
			}
			return cont;
		}        

        }


    public int contaNodiSinistriMultipli(int x) {
		if(root == null)
			return -1;
		return root.contaNodiConFiglioSinistroMultipli(x);
	}
}

e il main

codice:

		System.out.println("Quanti sono i nodi sinistri con valori multiplo di 3 di tree2? " + tree2.contaNodiConFiglioSinistroMultipli(3));
		System.out.println();

tree2 è inizializzato e tutto..

**Kaamos** · 10-06-2012, 16:42

Originariamente inviato da vfldj
Eccolo..
Grazie per la pazienza..

codice:

public class BinaryTree {

	private BinaryNode root;

	public static class BinaryNode {

        .........

		public int contaNodiConFiglioSinistroMultipli(int x) {
			int cont = 0;
			if (left != null && right == null) {
				if (left.dato % x == 0)
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x) + 1;
				else
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x);
			}
			if (left == null && right != null)
				cont = cont + right.contaNodiConFiglioSinistroMultipli(x);
			if (left != null && right != null) {
				cont = left.contaNodiConFiglioSinistroMultipli(x) + right.contaNodiConFiglioSinistroMultipli(x);
			}
			return cont;
		}        

        }


    public int contaNodiSinistriMultipli(int x) {
		if(root == null)
			return -1;
		return root.contaNodiConFiglioSinistroMultipli(x);
	}
}

e il main

codice:

		System.out.println("Quanti sono i nodi sinistri con valori multiplo di 3 di tree2? " + tree2.contaNodiConFiglioSinistroMultipli(3));
		System.out.println();

tree2 è inizializzato e tutto..

Hai definito il metodo contaNodiSinistriMultipli(int) nella classe BinaryTree ed il metodo contaNodiConFiglioSinistroMultipli(int) nella classe BinaryNode, ma non c'è nessun metodo contaNodiConFiglioSinistroMultipli(int) nella classe BinaryTree, come giustamente ti dice il compilatore. Hai sbagliato semplicemente nome (supponendo che tree2 sia un oggetto BinaryTree).

Fra l'altro, in caso di albero vuoto, io ritornerei 0, non -1. Se l'albero è vuoto non ci sono nodi con figli sinistri aventi valore multiplo di 3, ma non si verifica nessuna condizione d'errore. E comunque quando vuoi segnalare condizioni d'errore sarebbe più appropriato sollevare un'eccezione, obbligando il chiamante a tenere conto dell'errore che si è verificato.

P.S.: BinaryNode dovrebbe essere privata, non pubblica. Chi utilizza l'albero deve interfacciarsi solo tramite le chiavi contenuto nei nodi, non deve vedere i nodi. Inoltre se hai già affrontato i generici, utilizzali.

**vfldj** · 11-06-2012, 09:31

Originariamente inviato da Kaamos
Hai definito il metodo contaNodiSinistriMultipli(int) nella classe BinaryTree ed il metodo contaNodiConFiglioSinistroMultipli(int) nella classe BinaryNode, ma non c'è nessun metodo contaNodiConFiglioSinistroMultipli(int) nella classe BinaryTree, come giustamente ti dice il compilatore. Hai sbagliato semplicemente nome (supponendo che tree2 sia un oggetto BinaryTree).

Fra l'altro, in caso di albero vuoto, io ritornerei 0, non -1. Se l'albero è vuoto non ci sono nodi con figli sinistri aventi valore multiplo di 3, ma non si verifica nessuna condizione d'errore. E comunque quando vuoi segnalare condizioni d'errore sarebbe più appropriato sollevare un'eccezione, obbligando il chiamante a tenere conto dell'errore che si è verificato.

P.S.: BinaryNode dovrebbe essere privata, non pubblica. Chi utilizza l'albero deve interfacciarsi solo tramite le chiavi contenuto nei nodi, non deve vedere i nodi. Inoltre se hai già affrontato i generici, utilizzali.

Mii che scema!! Ops

Solitamente ritorno -1 perchè così mi salta all'occhio che è un albero "particolare", comunque si se facessi una cosa più seria restituirei un'eccezione ma ora si tratta di semplici esercizi per allenarsi

Ok allora metto BinaryNode privata, grazie per il consiglio..
I generici non so cosa siano..

**vfldj** · 11-06-2012, 09:39

Ho risolto in questo modo:

codice:

		public int contaNodiConFiglioSinistroMultipli(int x) {
			int cont = 0;
			if (left != null && right == null) {
				if (left.dato % x == 0)
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x) + 1;
				else
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x);
			}
			if (left == null && right != null)
				cont = cont + right.contaNodiConFiglioSinistroMultipli(x);
			if (left != null && right != null) {
				if (left.dato % x == 0)
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x) + right.contaNodiConFiglioSinistroMultipli(x) + 1;
				else
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x) + right.contaNodiConFiglioSinistroMultipli(x);
			}
			return cont;
		}

Grazie ancora!!

**Kaamos** · 11-06-2012, 14:53

Originariamente inviato da vfldj
Mii che scema!! Ops

Solitamente ritorno -1 perchè così mi salta all'occhio che è un albero "particolare", comunque si se facessi una cosa più seria restituirei un'eccezione ma ora si tratta di semplici esercizi per allenarsi

Ok allora metto BinaryNode privata, grazie per il consiglio..
I generici non so cosa siano..

Hai presente quando in una struttura dati specifichi il tipo, ad esempio ArrayList<String> invece di ArrayList?
http://docs.oracle.com/javase/tutori...ics/index.html

Originariamente inviato da vfldj
Ho risolto in questo modo:

codice:

		public int contaNodiConFiglioSinistroMultipli(int x) {
			int cont = 0;
			if (left != null && right == null) {
				if (left.dato % x == 0)
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x) + 1;
				else
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x);
			}
			if (left == null && right != null)
				cont = cont + right.contaNodiConFiglioSinistroMultipli(x);
			if (left != null && right != null) {
				if (left.dato % x == 0)
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x) + right.contaNodiConFiglioSinistroMultipli(x) + 1;
				else
					cont = cont + left.contaNodiConFiglioSinistroMultipli(x) + right.contaNodiConFiglioSinistroMultipli(x);
			}
			return cont;
		}

Grazie ancora!!

Io avrei fatto più una cosa del genere per semplificarlo, ma non ho un albero su cui provarlo, magari ho dimenticato qualche caso particolare:

codice:

int contaFigliSinistriMultipliDi(int value)
{
	return isEmpty() ? 0 : contaFigliSinistriMultipliDi(root, false);
}

codice:

private int contaFigliSinistriMultipliDi(int value, boolean isLeftChild)
{
	int counter = 0;
	
	if (isLeftChild && (key == 0 || key % 3 == 0))
		++counter;
	
	if (leftChild != null)
		counter += contaFigliSinistriMultipliDi(leftChild, true);
	
	if (rightChild != null)
		counter += contaFigliSinistriMultipliDi(rightChild, false);
	
	return counter;
}

Discussione: JAVA: Alberi: conta nodi sinistri multipli di x

Strumenti discussione

Ricerca discussione

Visualizza

JAVA: Alberi: conta nodi sinistri multipli di x

Permessi di invio