Дерево и бинарное дерево

Дерево (tree) — иерархическая структура данных из узлов, связанных рёбрами без циклов; бинарное дерево — дерево, где каждый узел имеет не более двух дочерних узлов (left и right).

Зачем нужно

Деревья — основа большинства иерархических структур: файловые системы, DOM HTML, JSON-объекты, абстрактные синтаксические деревья компиляторов, индексы баз данных. Бинарные деревья лежат в основе BST, кучи, сегментного дерева и многих других структур. Понимание деревьев необходимо для эффективной работы с вложенными данными.

Где используется

  • DOM-дерево браузера (иерархия HTML-элементов)
  • Файловые системы (директории и файлы)
  • JSON/XML: представление вложенных данных
  • Компиляторы: Abstract Syntax Tree (AST)
  • Базы данных: B-tree индексы
  • Приоритетные очереди (куча — специальное бинарное дерево)

Основной контент

Основные термины

           root (корень)
           [1]
          /   \
        [2]   [3]    ← children (дочерние)
        / \     \
      [4] [5]  [6]   ← leaves (листья)

- root: узел без родителя
- leaf: узел без дочерних узлов
- height: длина пути от корня до самого глубокого листа
- depth: расстояние от узла до корня
- subtree: узел + всё его поддерево

Виды деревьев

Тип Описание
Binary tree Каждый узел имеет ≤ 2 детей
Full binary tree Каждый узел имеет 0 или 2 детей
Complete binary tree Все уровни заполнены, кроме последнего (заполнен слева)
Perfect binary tree Все листья на одном уровне
BST Binary tree со свойством left < root < right
Heap Complete binary tree с heap property

Реализация узла и дерева

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

// Построение дерева вручную
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

Обходы дерева

// Pre-order: root → left → right (для копирования дерева)
function preOrder(node, result = ) {
  if (!node) return result;
  result.push(node.val);      // посетить корень
  preOrder(node.left, result);
  preOrder(node.right, result);
  return result;
}

// In-order: left → root → right (BST: отсортированный порядок)
function inOrder(node, result = ) {
  if (!node) return result;
  inOrder(node.left, result);
  result.push(node.val);
  inOrder(node.right, result);
  return result;
}

// Post-order: left → right → root (для удаления дерева)
function postOrder(node, result = ) {
  if (!node) return result;
  postOrder(node.left, result);
  postOrder(node.right, result);
  result.push(node.val);
  return result;
}

// Level-order (BFS): уровень за уровнем
function levelOrder(root) {
  if (!root) return ;
  const result = , queue = [root];
  while (queue.length) {
    const level = , size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Высота дерева — O(n)

function height(node) {
  if (!node) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

Частые ошибки

  • Забывать базовый случай if (!node) return в рекурсивных функциях — TypeError при обращении к null.val.
  • Путать обходы: in-order для BST даёт отсортированный массив, pre-order — нет.
  • Считать высоту дерева log n в общем случае — только для сбалансированного дерева; обычное BST может быть O(n).
  • Модифицировать дерево во время обхода без осторожности — нарушение структуры.

Связанные темы

Ресурсы