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

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

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

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

Контент

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

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

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

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

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

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

- DFS (обхід у глибину):
  - Preorder (прямий, NLR)
  - Inorder (симетричний, LNR) - визначений для бінарних дерев
  - Postorder (зворотний, LRN)
- BFS (обхід у ширину): Level-order (по рівнях)

## Розгорнута відповідь

### Класифікація обходів

- DFS (Depth-First Search, обхід у глибину)
  - Preorder (NLR, прямий): спочатку вузол, потім ліве піддерево, потім праве.
  - Inorder (LNR, симетричний): ліве піддерево, вузол, праве піддерево. Застосовний до бінарних дерев; для BST дає відсортовану послідовність.
  - Postorder (LRN, зворотний): ліве піддерево, праве піддерево, потім вузол.
- BFS (Breadth-First Search, обхід у ширину)
  - Level-order (по рівнях): відвідування вузлів шар за шаром згори вниз, зліва направо.

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

- Час: усі перелічені обходи відвідують кожен вузол рівно один раз - O(n).
- Пам'ять: DFS - O(h), де h - висота дерева (рекурсивний стек або явний стек; у гіршому випадку O(n)). BFS - O(w), де w - максимальна ширина рівня (у гіршому випадку O(n)).

### Рекурсивні приклади (JavaScript)

```javascript
// Вузли бінарного дерева
class Node {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// DFS (рекурсивно)
function preorder(node, res = []) { // NLR - прямий
  if (!node) return res;
  res.push(node.val);
  preorder(node.left, res);
  preorder(node.right, res);
  return res;
}

function inorder(node, res = []) { // LNR - симетричний (для бінарних дерев)
  if (!node) return res;
  inorder(node.left, res);
  res.push(node.val);
  inorder(node.right, res);
  return res;
}

function postorder(node, res = []) { // LRN - зворотний
  if (!node) return res;
  postorder(node.left, res);
  postorder(node.right, res);
  res.push(node.val);
  return res;
}

// BFS (по рівнях)
function bfs(root) {
  const res = [];
  if (!root) return res;
  const q = [root];
  while (q.length) {
    const node = q.shift();
    res.push(node.val);
    if (node.left) q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return res;
}
```

### Ітеративні приклади (JavaScript)

```javascript
function preorderIter(root) {
  const res = [];
  if (!root) return 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;
}

// BFS (по рівнях)
function bfsIter(root) {
  return bfs(root);
}
```

### Приклад дерева і результати обходів

```javascript
const root =
  new Node(1,
    new Node(2,
      new Node(4),
      new Node(5)
    ),
    new Node(3,
      null,
      new Node(6)
    )
  );

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

console.log('Preorder (NLR):', preorder(root));   // [1, 2, 4, 5, 3, 6]
console.log('Inorder (LNR):', inorder(root));     // [4, 2, 5, 1, 3, 6]
console.log('Postorder (LRN):', postorder(root)); // [4, 5, 2, 6, 3, 1]
console.log('BFS (level-order):', bfs(root));     // [1, 2, 3, 4, 5, 6]
```

### Коли який обхід використовувати

- Preorder: копіювання/серіалізація дерева, генерація префіксного запису виразів.
- Inorder (для бінарних дерев): отримання відсортованого списку з BST, перевірка властивостей BST.
- Postorder: видалення/звільнення дерева (знизу вгору), обчислення виразів (польський постфіксний запис).
- BFS (level-order): пошук найкоротшого шляху за кількістю ребер у неважених деревах/графах, пошарові задачі (середні по рівню, праві/ліві види тощо).

### Зауваження і підводні камені

- Inorder коректно визначений лише для бінарних дерев; для загального k-арного дерева його аналог залежить від домовленостей.
- Рекурсія може призвести до переповнення стека на сильно незбалансованих деревах; використовуйте ітеративні варіанти.
- Існують оптимізації за пам'яттю, наприклад Morris Traversal для inorder з O(1) додаткової пам'яті, але він змінює зв'язки під час обходу.

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

Для рев’юера

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

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