TypeScript Academy · Lekcja

Typowanie struktur drzewiastych

Modeluj zagnieżdżone węzły drzewa za pomocą typów rekurencyjnych

Typowanie struktur drzewiastych to bezpłatna lekcja TypeScript Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej TypeScript Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs TypeScript Academy zawiera 4 lekcji w sumie.

Typ węzła drzewa

Drzewa uogólniają listy: każdy węzeł ma wartość oraz tablicę węzłów potomnych tego samego typu. Jest to typ rekurencyjny z tablicą children.

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

Budowanie małego drzewa

Węzeł z dziećmi to po prostu zagnieżdżone obiekty. Pusta tablica jest naturalnym przypadkiem bazowym dla liścia.

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);

Głębsze zagnieżdżanie

Węzły potomne mogą mieć własne dzieci na dowolnej głębokości, ponieważ każdy potomek jest pełnym obiektem typu TreeNode.

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);

Sumowanie wszystkich wartości

Funkcja rekurencyjna odwiedza każdy węzeł i wywołuje samą siebie dla jego dzieci, gromadząc wynik w ramach przejścia w głąb.

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));

Zliczanie węzłów

Ten sam schemat przejścia pozwala zliczać węzły: jeden dla bieżącego węzła plus liczba węzłów we wszystkich poddrzewach.

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));

Znajdowanie maksymalnej głębokości

Głębokość wynosi jeden plus maksymalna głębokość wśród dzieci albo jeden w przypadku liścia bez dzieci.

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));

Zbieranie wszystkich wartości

Proszę spłaszczyć drzewo do tablicy, łącząc bieżącą wartość ze spłaszczonymi dziećmi.

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));

Przeszukiwanie drzewa

Rekurencyjne wyszukiwanie zwraca pierwszy węzeł spełniający predykat, przeszukując dzieci, gdy bieżący węzeł go nie spełnia.

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);

Mapowanie drzewa

Proszę przekształcić każdą wartość, zachowując strukturę przez rekurencyjne mapowanie wartości i dzieci.

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);

Drzewa odwzorowują rzeczywiste dane

Systemy plików, drzewa DOM, schematy organizacyjne i drzewa AST to drzewa. Jeden rekurencyjny typ opisuje je wszystkie przy pełnym bezpieczeństwie typów.

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);

Liście i gałęzie

Węzeł jest liściem, gdy tablica children jest pusta, a w przeciwnym razie jest gałęzią. To rozróżnienie często wyznacza logikę przechodzenia po drzewie.

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: [] }));

Szybkie sprawdzenie: struktury drzewiaste

Proszę sprawdzić swoją wiedzę na temat typowania struktur drzewiastych.

Podsumowanie: typowanie struktur drzewiastych

Zamodelowali Państwo drzewa za pomocą TreeNode<T>, w którym każdy węzeł ma wartość i tablicę węzłów potomnych, a następnie napisali rekurencyjne funkcje do sumowania, zliczania, wyszukiwania i mapowania ich elementów.

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

Często zadawane pytania

Czy lekcja „Typowanie struktur drzewiastych” jest bezpłatna?

Tak — pełny tekst „Typowanie struktur drzewiastych” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu TypeScript Academy, przejdź na CoddyKit PRO. Kurs TypeScript Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Typowanie struktur drzewiastych”?

Modeluj zagnieżdżone węzły drzewa za pomocą typów rekurencyjnych Ćwiczysz TypeScript Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć TypeScript Academy?

Nie wymagamy żadnego doświadczenia. TypeScript Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.

Ile czasu zajmuje lekcja „Typowanie struktur drzewiastych”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji TypeScript Academy?

Tak. Każda lekcja TypeScript Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do TypeScript Academy