[Java] Banale esercizio su alberi binari di ricerca.

[dexter86]

Salve a tutti,
è un esercizio banale lo so ma non riesco a venirne a capo.

questo è il testo:
Scrivere il metodo Java static int sommaIntervallo(TreeNode radice, int min, int max) che re-
stituisce la somma dei soli nodi il cui valore è compreso tra min e max, sfruttando la struttura del BST per
evitare di visitare inutilmente porzioni di rami dell'albero. Calcolare il costo computazionale, motivandolo
opportunamente.

Questo è quello che ho scritto io, mi pare corretto logicamente, però testandolo non funziona come dovrebbe.

    public int stampaIntervallo(BSTNode root, int min, int max) {
        int somma = 0;
        if (root == null) return 0;

        if ((min < root.key) && (root.key < max)) {
            somma += root.key;
            if (root.left.key > min)
                somma += stampaIntervallo(root.left, min, max);
            if (root.right.key < max)
                somma += stampaIntervallo(root.right, min, max);
        }
       
        if (root.key > max)
            somma += stampaIntervallo(root.left, min, max);
        if (root.key < min)
            somma += stampaIntervallo(root.right, min, max);
       
        return somma;

    }

[dexter86]

Mi rispondo da solo.
Ecco una possibile soluzione :

public static int sommaIntervallo(BSTNode radice, int min, int max) {
      if (radice == null)
         return 0;
      int ris = 0;
      if (radice.key >= min && radice.key <= max)
         ris += radice.key;
      if (radice.key >= min)
         ris += sommaIntervallo(radice.left, min, max);
      if (radice.key <= max)
         ris += sommaIntervallo(radice.right, min, max);
      return ris;
   }

[index]

Ciao dexter86,
se non ho capito male hai un albero binario e vuoi navigare ogni nodo (che contiene un valore) sommando solo i valori che sono compresi tra min e max. Giusto?

Dal secondo algoritmo che hai inserito presumo che i nodi siano anche ordinati, altrimenti non si spiega. Giusto?

Ciao.

[dexter86]

L'esercizio è per l'appunto su un BST ovvero un albero binario di ricerca, la cui peculiarità è quella che i figli di un nodo sono ordinati, usualmente avendo valori minori di quelli del nodo di partenza nei figli a sinistra e valori più grandi nei figli a destra.

se non ho capito male hai un albero binario e vuoi navigare ogni nodo (che contiene un valore) sommando solo i valori che sono compresi tra min e max. Giusto?

Giusto.

[index]

Si si mea culpa, mi era sfuggito BST (non l'avevo proprio visto).