Які основні типи обходів дерева існують?

АлгоритмиJunior~1 хв читання

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

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

function inorderIter(root) {
  const res = [];
  const stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) {
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop();
    res.push(cur.val);
    cur = cur.right;
  }
  return res;
}

function postorderIter(root) {
  const res = [];
  if (!root) return res;
  const s1 = [root];
  const s2 = [];
  while (s1.length) {
    const node = s1.pop();
    s2.push(node);
    if (node.left) s1.push(node.left);
    if (node.right) s1.push(node.right);
  }
  while (s2.length) {
    res.push(s2.pop().val);
  }
  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) додаткової пам'яті, але він змінює зв'язки під час обходу.

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

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.