0Pricing
TypeScript Academy · Lezione

Tipizzare le strutture ad albero

Modelli nodi di alberi annidati con tipi ricorsivi.

Tipizzare le strutture ad albero è una lezione TypeScript Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento TypeScript Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso TypeScript Academy include 4 lezioni in totale.

Il tipo di un nodo dell'albero

Gli alberi generalizzano le liste: ogni nodo ha un valore e un array di nodi figli dello stesso tipo. Si tratta di un tipo ricorsivo con un array children.

type TreeNode<T> = {
  value: T;
  children: TreeNode<T>[];
};
const leaf: TreeNode<number> = { value: 1, children: [] };
console.log(leaf.value);

Costruire un piccolo albero

Un nodo con figli è semplicemente costituito da oggetti annidati. L'array vuoto è il caso base naturale per una foglia.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
const tree: TreeNode<string> = {
  value: "root",
  children: [
    { value: "a", children: [] },
    { value: "b", children: [] }
  ]
};
console.log(tree.children.length);

Annidare a maggiore profondità

I figli possono avere a loro volta figli a qualsiasi profondità, perché ogni figlio è un TreeNode completo.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
const tree: TreeNode<number> = {
  value: 1,
  children: [
    { value: 2, children: [{ value: 4, children: [] }] },
    { value: 3, children: [] }
  ]
};
console.log(tree.children[0].children[0].value);

Somma di tutti i valori

Una funzione ricorsiva visita ogni nodo e ricorre sui relativi figli, accumulando un risultato: si tratta di un attraversamento in profondità.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function sum(node: TreeNode<number>): number {
  let total = node.value;
  for (const child of node.children) total += sum(child);
  return total;
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }, { value: 3, children: [] }] };
console.log(sum(t));

Contare i nodi

La stessa struttura di attraversamento permette di contare i nodi: uno per il nodo corrente più il numero di nodi di tutti i sottoalberi.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function count<T>(node: TreeNode<T>): number {
  return 1 + node.children.reduce((acc, c) => acc + count(c), 0);
}
const t: TreeNode<string> = { value: "r", children: [{ value: "a", children: [] }] };
console.log(count(t));

Trovare la profondità massima

La profondità è pari a uno più la profondità massima tra i figli, oppure a uno per una foglia senza figli.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function depth<T>(node: TreeNode<T>): number {
  if (node.children.length === 0) return 1;
  return 1 + Math.max(...node.children.map(depth));
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [{ value: 3, children: [] }] }] };
console.log(depth(t));

Raccogliere tutti i valori

Appiattisca un albero in un array concatenando il valore corrente con i figli appiattiti.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function flatten<T>(node: TreeNode<T>): T[] {
  return [node.value, ...node.children.flatMap(flatten)];
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }, { value: 3, children: [] }] };
console.log(flatten(t));

Cercare nell'albero

Una ricerca ricorsiva restituisce il primo nodo che corrisponde a un predicato, esplorando i figli quando il nodo corrente non corrisponde.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function find<T>(node: TreeNode<T>, pred: (v: T) => boolean): TreeNode<T> | null {
  if (pred(node.value)) return node;
  for (const c of node.children) {
    const hit = find(c, pred);
    if (hit) return hit;
  }
  return null;
}
const t: TreeNode<number> = { value: 1, children: [{ value: 5, children: [] }] };
console.log(find(t, v => v === 5)?.value);

Mappare un albero

Trasformi ogni valore preservando la struttura, mappando ricorsivamente il valore e i figli.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function mapTree<T, U>(node: TreeNode<T>, fn: (v: T) => U): TreeNode<U> {
  return { value: fn(node.value), children: node.children.map(c => mapTree(c, fn)) };
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }] };
console.log(mapTree(t, x => x * 100).value);

Gli alberi modellano dati reali

I file system, gli alberi DOM, gli organigrammi e gli AST sono tutti alberi. Un singolo tipo ricorsivo li descrive tutti con la massima sicurezza dei tipi.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
type FileTree = TreeNode<string>;
const fs: FileTree = { value: "/", children: [{ value: "home", children: [] }] };
console.log(fs.value, fs.children[0].value);

Foglie e rami

Un nodo è una foglia quando children è vuoto e un ramo negli altri casi. Questa distinzione determina spesso la logica di attraversamento.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function isLeaf<T>(node: TreeNode<T>): boolean {
  return node.children.length === 0;
}
console.log(isLeaf({ value: 1, children: [] }));

Verifica rapida: strutture ad albero

Verifichi la Sua comprensione della tipizzazione delle strutture ad albero.

Riepilogo: tipizzazione delle strutture ad albero

Ha modellato gli alberi con TreeNode<T>, in cui ogni nodo ha un valore e un array di nodi figli, quindi ha scritto funzioni ricorsive per sommare, contare, cercare e applicare il mapping ai relativi elementi.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }] };
console.log(t.children[0].value);

Domande Frequenti

La lezione «Tipizzare le strutture ad albero» è gratuita?

Sì — il testo completo di «Tipizzare le strutture ad albero» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso TypeScript Academy, passa a CoddyKit PRO. Il corso TypeScript Academy include 4 lezioni in totale.

Cosa imparerò in «Tipizzare le strutture ad albero»?

Modelli nodi di alberi annidati con tipi ricorsivi. Eserciti TypeScript Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare TypeScript Academy?

Non è richiesta alcuna esperienza precedente. TypeScript Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.

Quanto tempo richiede la lezione «Tipizzare le strutture ad albero»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione TypeScript Academy?

Sì. Ogni lezione TypeScript Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Definizioni di tipi ricorsivi
  2. Tipizzare le strutture ad albero
  3. Tipi per i valori JSON
  4. Profondità e limiti della ricorsione
← Torna a TypeScript Academy