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

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

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

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

Контент

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

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

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

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

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

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

Postorder traversal (постфіксний обхід) - це поглиблений обхід дерева, який відвідує вузли в порядку: ліве піддерево, праве піддерево, сам вузол (L-R-Root). Для n-арного дерева - усі діти зліва направо, потім вузол.

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

Постфіксний обхід - одна з форм обходу в глибину (DFS). Головна ідея: спочатку повністю обробити піддерева, а потім поточний вузол. Це робить postorder природним вибором для задач, де значення вузла залежить від результатів його нащадків.

- Порядок обходу (бінарне дерево): ліве піддерево, праве піддерево, вузол (L-R-Root).
- Для n-арного дерева: обійти всіх дітей зліва направо, потім поточний вузол.
- Складність: час O(n), пам'ять O(h) при рекурсії (h - висота дерева). Ітеративні версії використовують O(h) додаткової пам'яті для стека.
- Де корисний: обчислення значень у дереві виразів (отримання постфіксної форми), видалення/звільнення дерева знизу вгору, обчислення розмірів/висот піддерев, серіалізація в обернений польський запис.

### Приклад на дереві

```
      A
     / \
    B   C
   / \
  D   E

Постфіксний порядок: D, E, B, C, A
```

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

```
// Вузол бінарного дерева
// { val: any, left: Node|null, right: Node|null }

function postorderRecursive(node, visit) {
  if (!node) return;
  postorderRecursive(node.left, visit);
  postorderRecursive(node.right, visit);
  visit(node);
}

// Приклад
const tree = {
  val: 'A',
  left: {
    val: 'B',
    left: { val: 'D', left: null, right: null },
    right: { val: 'E', left: null, right: null }
  },
  right: { val: 'C', left: null, right: null }
};

const result = [];
postorderRecursive(tree, n => result.push(n.val));
console.log(result); // ['D', 'E', 'B', 'C', 'A']
```

### Ітеративна реалізація (JavaScript, без рекурсії)

Однoстековий підхід з покажчиком на останній відвіданий вузол. Рухаємось вліво, потім перевіряємо правого нащадка і вирішуємо, спускатися чи відвідувати вершину.

```
function postorderIterative(root, visit) {
  const stack = [];
  let lastVisited = null;
  let curr = root;

while (stack.length || curr) {
    if (curr) {
      stack.push(curr);
      curr = curr.left;
    } else {
      const peek = stack[stack.length - 1];
      if (peek.right && lastVisited !== peek.right) {
        curr = peek.right;
      } else {
        visit(peek);
        lastVisited = stack.pop();
      }
    }
  }
}

// Перевірка
const out = [];
postorderIterative(tree, n => out.push(n.val));
console.log(out); // ['D', 'E', 'B', 'C', 'A']
```

### N-арне дерево

У n-арному дереві вузол має масив children. Ми обходимо всіх дітей зліва направо, потім відвідуємо поточний вузол:

```
// Вузол n-арного дерева: { val, children: Node[] }
function postorderNAry(node, visit) {
  if (!node) return;
  for (const child of node.children || []) {
    postorderNAry(child, visit);
  }
  visit(node);
}

// Приклад структури:
const nary = {
  val: 'A',
  children: [
    { val: 'B', children: [ { val: 'E', children: [] }, { val: 'F', children: [] } ] },
    { val: 'C', children: [] },
    { val: 'D', children: [] }
  ]
};

const order = [];
postorderNAry(nary, n => order.push(n.val));
console.log(order); // ['E', 'F', 'B', 'C', 'D', 'A']
```

### Типові задачі, де потрібен постфіксний обхід

- Дерева виразів: обчислення значення і генерація оберненого польського запису.
- Видалення/звільнення дерева: спочатку звільняємо нащадків, потім батька.
- Підрахунок властивостей піддерев: розміри, висоти, суми значень.
- Серіалізація/копіювання, коли порядок «знизу вгору» критичний.

### Граничні випадки і зауваження

- Порожнє дерево: обхід нічого не робить.
- Один вузол: повертається сам корінь.
- Сильно незбалансоване дерево: глибина рекурсії може досягати O(n); за ризику переповнення стека використовуйте ітеративний варіант.

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

Для рев’юера

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

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