corsoJava
  • Corso JAVA
  • Introduzione linguaggio
  • Verifica tipi primitivi vs reference
  • Esercizi su equals
  • Introduzione su oggetti
  • Packages e import
  • Polimorfismo
    • Pit stop
  • Enum
  • String รจ speciale
  • Eccezioni
  • Nested Classes
  • Array, ArrayList e Hash Table
    • Esempio gioco carte
  • Linked data structures
  • Tipi generici
  • Comparing Java and C# Generics - Jonathan Pryor's web log
  • Contenitori
    • Esempi con classi container
  • Input/Output streams, Files
  • Basic I/O
  • Java IO Tutorial
  • Networking
  • I Thread e concorrenza
    • Esercizi multithreading
    • Thread interference
    • Esercizi thread interference
    • wait(), notify() e notifyAll() per la sincronizzazione tra i thread
    • Verifiche produttore/consumatore
    • Lock esplicito - java.util.concurrent.Locks
    • Semafori
    • Programmare con i thread
    • I Virtual Thread
    • Materiale
  • I Thread e networking
  • Esempi Java Socket Programming
  • Esempi Javascript Socket Programming
  • Messaggi datagram e invio multicast
  • Lambda Expression
  • Java Stream
  • Data Oriented Programming in Java
  • Java improved its 'Hello World' experience
  • Appendice A: utilizzo classe Scanner
  • Java For The Experienced Beginner
  • Modern Java
  • CodeJava - Java Core
  • Is OOP Relevant Today?
  • Book
Powered by GitBook
On this page
  • Algoritmi ricorsivi
  • Linked data structures
  • Alberi binari

Linked data structures

Algoritmi ricorsivi

Esempio, la binary search puรฒ essere anche implementata in modo ricorsivo:

/**
 * Search in the array A in positions numbered loIndex to hiIndex, inclusive,
 * for the specified value. If the value is found, return the index in the array
 * where it occurs. If the value is not found, return -1. Precondition: The
 * array must be sorted into increasing order.
 */

static int binarySearch(int[] A, int loIndex, int hiIndex, int value) {
	if (loIndex > hiIndex) {
		// The starting position comes after the final index,
		// so there are actually no elements in the specified
		// range. The value does not occur in this empty list!
		return -1;
	} else {
		// Look at the middle position in the list. If the
		// value occurs at that position, return that position.
		// Otherwise, search recursively in either the first
		// half or the second half of the list.
		int middle = (loIndex + hiIndex) / 2;
		if (value == A[middle])
			return middle;
		else if (value < A[middle])
			return binarySearch(A, loIndex, middle - 1, value);
		else // value must be > A[middle]
			return binarySearch(A, middle + 1, hiIndex, value);
	}
} // end binarySearch()

Linked data structures

Struttura dati definita in modo ricorsivo:

class Node {
  String item;
  Node next;  
}

Alberi binari

class TreeNode {
    int item; // The data in this node.
    TreeNode left; // Pointer to the left subtree.
    TreeNode right; // Pointer to the right subtree.
}
PreviousEsempio gioco carteNextTipi generici

Last updated 6 years ago

Esempio di linked list
Struttura ad albero