JavaScript: verificare se un albero binario è simmetrico

Un albero binario è una struttura dati molto comune in informatica e programmazione. Un albero binario è detto "simmetrico" se è possibile riflettere il suo sottoalbero destro in modo che diventi uguale al suo sottoalbero sinistro. In altre parole, l'albero è simmetrico se le sue parti sinistra e destra sono strutturalmente identiche.

In questo articolo, esploreremo come verificare se un albero binario è simmetrico utilizzando JavaScript. Per farlo, utilizzeremo una funzione ricorsiva che effettuerà la verifica. Inizieremo definendo una struttura dati per rappresentare un nodo nell'albero binario.

Iniziamo definendo la struttura dati del nodo dell'albero binario. Ogni nodo avrà due proprietà principali: il valore del nodo e i suoi figli sinistro e destro.


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

Per verificare se un albero binario è simmetrico, dobbiamo scrivere una funzione ricorsiva che confronti i sottoalberi sinistro e destro di ogni nodo. Ecco come fare:


function isSymmetric(root) {
  if (!root) {
    // Se l'albero è vuoto, è simmetrico per definizione.
    return true;
  }

  // Funzione di supporto per la verifica della simmetria.
  function isMirror(left, right) {
    if (!left && !right) {
      // Entrambi i sottoalberi sono vuoti, quindi sono simmetrici.
      return true;
    }
    if (!left || !right || left.value !== right.value) {
      // Se uno dei sottoalberi è vuoto o i valori non corrispondono, non sono simmetrici.
      return false;
    }
    
    // Verifica la simmetria ricorsivamente.
    return isMirror(left.left, right.right) && isMirror(left.right, right.left);
  }

  // Chiamata iniziale alla funzione di supporto.
  return isMirror(root.left, root.right);
}

Ora che abbiamo definito la funzione isSymmetric, possiamo utilizzarla per verificare se un albero binario è simmetrico o meno. Ecco un esempio:


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

// Verifichiamo se l'albero è simmetrico.
const result = isSymmetric(root);

if (result) {
  console.log("L'albero è simmetrico.");
} else {
  console.log("L'albero non è simmetrico.");
}

In questo esempio, l'albero è simmetrico, quindi il risultato sarà "L'albero è simmetrico."

Conclusioni

La verifica della simmetria di un albero binario è una questione comune in programmazione, e possiamo farlo in modo efficiente utilizzando una funzione ricorsiva in JavaScript. La funzione isSymmetric confronta i sottoalberi sinistro e destro di ogni nodo e restituisce true se l'albero è simmetrico e false altrimenti. Utilizzando questo approccio, è possibile determinare facilmente se un albero binario è simmetrico o meno in JavaScript.

Torna su