JavaScript: calcolare la profondità minima di un albero binario

Un albero binario è una struttura dati comune utilizzata nella programmazione per organizzare e memorizzare dati in modo gerarchico. Calcolare la profondità minima di un albero binario è una operazione utile in molte applicazioni, come la ricerca efficiente di elementi o l'ottimizzazione delle prestazioni di algoritmi che operano sugli alberi binari. In questo articolo, esploreremo come calcolare la profondità minima di un albero binario utilizzando JavaScript.

La profondità minima di un albero binario è la lunghezza del cammino più breve dalla radice (il nodo superiore) all'ultimo nodo foglia (un nodo senza figli) nell'albero. In altre parole, rappresenta il numero minimo di passaggi necessari per raggiungere la foglia più vicina dalla radice.

Per calcolare la profondità minima di un albero binario, possiamo utilizzare una semplice funzione ricorsiva. Iniziamo definendo una struttura dati di base per rappresentare un nodo in un albero binario:


class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Ora, creiamo una funzione che calcoli la profondità minima:


function minDepth(root) {
  // Se l'albero è vuoto, la profondità minima è 0.
  if (root === null) {
    return 0;
  }
  
  // Se il nodo corrente è una foglia, restituisci 1.
  if (root.left === null && root.right === null) {
    return 1;
  }
  
  // Calcola la profondità minima dei sottoalberi sinistro e destro.
  const leftDepth = minDepth(root.left);
  const rightDepth = minDepth(root.right);
  
  // Restituisci la profondità minima tra i sottoalberi sinistro e destro.
  return 1 + Math.min(leftDepth, rightDepth);
}

Questa funzione è ricorsiva e opera in questo modo:

  1. Se l'albero è vuoto (rappresentato da null), la profondità minima è 0.

  2. Se il nodo corrente è una foglia (non ha figli), la profondità minima è 1.

  3. Altrimenti, calcoliamo la profondità minima dei sottoalberi sinistro e destro chiamando la funzione minDepth ricorsivamente su di essi.

  4. Infine, restituiamo 1 più il minimo tra le profondità dei sottoalberi sinistro e destro. Questo rappresenta la profondità minima dell'albero.

Ecco un esempio di utilizzo della funzione minDepth con un albero binario:


const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

const depth = minDepth(root);
console.log("Profondità Minima:", depth); // Output: Profondità Minima: 2

In questo esempio, l'albero binario ha una profondità minima di 2.

Conclusioni

Calcolare la profondità minima di un albero binario è un'operazione fondamentale nella gestione delle strutture dati gerarchiche. Utilizzando JavaScript e una funzione ricorsiva, è possibile ottenere facilmente la profondità minima di un albero binario. Questo calcolo può essere utile in vari contesti di programmazione, come l'ottimizzazione degli algoritmi che operano sugli alberi binari o la ricerca efficiente di elementi all'interno dell'albero.

Torna su