0Pricing
TypeScript Academy · Урок

Типизация древовидных структур

Моделируйте вложенные узлы деревьев с помощью рекурсивных типов

«Типизация древовидных структур» — бесплатный урок TypeScript Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения TypeScript Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс TypeScript Academy содержит 4 уроков всего.

Тип узла дерева

Деревья обобщают списки: каждый узел содержит значение и массив дочерних узлов того же типа. Это рекурсивный тип с массивом children.

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

Построение небольшого дерева

Узел с дочерними узлами — это всего лишь вложенные объекты. Пустой массив является естественным базовым случаем для leaf.

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

Более глубокая вложенность

Дочерние узлы могут иметь собственные дочерние узлы на любой глубине, поскольку каждый дочерний узел сам является полноценным 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);

Суммирование всех значений

Рекурсивная функция посещает каждый узел и рекурсивно обходит его дочерние узлы, накапливая результат; это обход в глубину.

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

Подсчёт узлов

Та же схема обхода подсчитывает узлы: один для текущего узла плюс количество узлов во всех поддеревьях.

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

Поиск максимальной глубины

Глубина равна единице плюс максимальная глубина среди дочерних узлов или единице для листа без дочерних узлов.

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

Сбор всех значений

Преобразуйте дерево в массив, объединяя текущее значение с результатом преобразования дочерних узлов в плоский массив.

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

Поиск в дереве

Рекурсивный поиск возвращает первый узел, соответствующий предикату, и исследует дочерние узлы, если текущий узел не соответствует ему.

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

Преобразование дерева

Преобразуйте каждое значение, сохраняя структуру: рекурсивно преобразуйте значение и дочерние узлы.

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

Деревья моделируют реальные данные

Файловые системы, деревья DOM, организационные диаграммы и абстрактные синтаксические деревья (AST) — всё это деревья. Один рекурсивный тип описывает их все с полной типобезопасностью.

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

Листья и ветви

Узел является листом, если его children пуст, и ветвью в противном случае. Это различие часто определяет логику обхода.

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

Быстрая проверка: структуры деревьев

Проверьте своё понимание типизации структур деревьев.

Итоги: типизация структур деревьев

Вы смоделировали деревья с помощью TreeNode<T>, где каждый узел содержит значение и массив дочерних узлов, а затем написали рекурсивные функции для суммирования, подсчёта, поиска и преобразования их элементов.

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

Часто задаваемые вопросы

Урок «Типизация древовидных структур» бесплатный?

Да — полный текст урока «Типизация древовидных структур» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс TypeScript Academy, подпишись на CoddyKit PRO. Курс TypeScript Academy содержит 4 уроков всего.

Чему я научусь в уроке «Типизация древовидных структур»?

Моделируйте вложенные узлы деревьев с помощью рекурсивных типов Ты практикуешь TypeScript Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать TypeScript Academy?

Предыдущий опыт не требуется. TypeScript Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Типизация древовидных структур»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке TypeScript Academy?

Да. Каждый урок TypeScript Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Рекурсивные определения типов
  2. Типизация древовидных структур
  3. Типы значений JSON
  4. Глубина и ограничения рекурсии
← Назад к TypeScript Academy