JavaScript: calcolare la profondità massima di un albero binario

Gli alberi binari sono una struttura dati comune in informatica utilizzata per organizzare dati in una struttura ad albero. Ogni nodo può avere al massimo due figli: un figlio sinistro e un figlio destro. Calcolare la profondità massima di un albero binario è una delle operazioni più comuni quando si lavora con questa struttura dati. In questo articolo, esploreremo come calcolare la profondità massima di un albero binario utilizzando JavaScript.

Un albero binario è costituito da nodi collegati tra loro. Ogni nodo può contenere un valore e può avere al massimo due figli, un figlio sinistro e un figlio destro. La radice è il nodo principale da cui inizia l'albero, mentre le foglie sono i nodi che non hanno figli.

Ecco un esempio di struttura di un albero binario:


       1
      / \
     2   3
    / \
   4   5

In questo esempio, il nodo radice contiene il valore 1 e ha due figli, il nodo 2 e il nodo 3. Il nodo 2 ha due figli, il nodo 4 e il nodo 5.

Per calcolare la profondità massima di un albero binario, possiamo utilizzare una ricorsione. La profondità di un nodo è data dalla profondità del suo nodo padre più uno. Pertanto, possiamo definire una funzione ricorsiva che calcoli la profondità massima visitando tutti i nodi dell'albero.

Ecco un esempio di come farlo in JavaScript:


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

function getMaxDepth(root) {
  if (!root) {
    return 0;
  }

  const leftDepth = getMaxDepth(root.left);
  const rightDepth = getMaxDepth(root.right);

  return Math.max(leftDepth, rightDepth) + 1;
}

// Creiamo un albero di esempio
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

const maxDepth = getMaxDepth(root);
console.log("Profondità massima dell'albero:", maxDepth);

In questo codice, abbiamo creato una classe Nodo per rappresentare i nodi dell'albero. La funzione getMaxDepth prende la radice dell'albero come argomento e calcola la profondità massima utilizzando la ricorsione.

Conclusioni

Calcolare la profondità massima di un albero binario è una operazione comune quando si lavora con questa struttura dati. Utilizzando la ricorsione, è possibile ottenere facilmente la profondità massima di un albero binario in JavaScript. Ricordate che questa è solo una delle molte operazioni che è possibile eseguire sugli alberi binari, e la conoscenza di tali operazioni è fondamentale per lavorare con successo con questa struttura dati.

Torna su