Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що робить preorder traversal (префіксний обхід)?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

## Коротка відповідь

Preorder traversal (префіксний обхід) - це обхід бінарного дерева в порядку: спочатку поточний вузол (N), потім ліве піддерево (L), потім праве піддерево (R), тобто N-L-R. Він відвідує корінь раніше за його нащадків.

## Детальне пояснення

Префіксний обхід визначає порядок відвідування вузлів бінарного дерева. На кожному кроці ми спочатку «обробляємо» поточний вузол (наприклад, записуємо його значення), потім рекурсивно обходимо ліве піддерево, потім праве.

1. Обробити поточний вузол (відвідати його/внести в результат).
2. Рекурсивно виконати preorder для лівого піддерева.
3. Рекурсивно виконати preorder для правого піддерева.

- Складність за часом: O(n), де n - кількість вузлів (кожен вузол відвідується рівно один раз).
- Пам'ять: O(h), де h - висота дерева (глибина стека викликів при рекурсії або розмір допоміжного стека при ітерації). У гіршому випадку (вироджене дерево) h = n.

### Де використовується preorder

- Серіалізація/копіювання дерева (з явним позначенням null-дітей).
- Відновлення дерева за preorder + inorder послідовностями.
- Отримання префіксного (польського) запису виразів у деревах виразів.

### Приклад дерева і порядок обходу

```
      1
     / \
    2   3
   / \   \
  4   5   6
```

Preorder (N-L-R) для цього дерева: [1, 2, 4, 5, 3, 6].

### Рекурсивна реалізація (JavaScript)

```
// Визначення вузла
function TreeNode(val, left = null, right = null) {
  this.val = val;
  this.left = left;
  this.right = right;
}

// Preorder: N-L-R
function preorder(root) {
  const res = [];
  function dfs(node) {
    if (!node) return;
    res.push(node.val);      // N
    dfs(node.left);          // L
    dfs(node.right);         // R
  }
  dfs(root);
  return res;
}

// Приклад
const root = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(4),
    new TreeNode(5)
  ),
  new TreeNode(3,
    null,
    new TreeNode(6)
  )
);

console.log(preorder(root)); // [1, 2, 4, 5, 3, 6]
```

### Ітеративна реалізація (стек)

```
function preorderIterative(root) {
  if (!root) return [];
  const res = [];
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);           // відвідуємо вузол
    if (node.right) stack.push(node.right); // спочатку вправо
    if (node.left) stack.push(node.left);   // потім вліво - щоб лівий був зверху стека
  }
  return res;
}

// Перевірка
console.log(preorderIterative(root)); // [1, 2, 4, 5, 3, 6]
```

### Відмінності від інших обходів

- Inorder (L-N-R): ліве - корінь - праве. Для BST дає відсортовану послідовність.
- Postorder (L-R-N): ліве - праве - корінь. Зручний для видалення/звільнення ресурсів знизу вгору.
- Preorder (N-L-R): корінь - ліве - праве. Дозволяє «спочатку зрозуміти структуру», потім заглиблюватися в піддерева.

### Складність і пам'ять

- Час: O(n) - кожен вузол відвідується один раз.
- Пам'ять: O(h) для стека рекурсії/ітерації; у гіршому випадку (лінійне дерево) - O(n).

### Часті помилки і тонкощі

- Забути обробити поточний вузол до рекурсії (це вже буде inorder/postorder).
- В ітеративній версії переплутати порядок push: потрібно спочатку класти правого, потім лівого нащадка.
- Не враховувати null-вузли при серіалізації (для однозначного відновлення дерева null треба явно фіксувати).

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати457 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.