В каком порядке итеративный обход дерева с использованием стека выведет узлы, если дочерние элементы упорядочены слева направо?

Итеративный обход дерева со стеком

При итеративном обходе дерева в глубину (DFS) с использованием стека порядок вывода узлов зависит от того, как мы помещаем дочерние элементы в стек. Если дочерние узлы упорядочены слева направо, то для получения прямого (pre-order) обхода мы сначала помещаем в стек правый дочерний узел, затем левый. Это гарантирует, что левый узел будет извлечен и обработан первым, так как стек работает по принципу "последним пришел — первым вышел" (LIFO).

Пример кода

function iterativePreOrder(root) {
  if (!root) return;
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    console.log(node.value); // Обрабатываем узел
    // Сначала добавляем правый, потом левый
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
}

В этом примере для дерева с корнем A, левым дочерним B и правым C, вывод будет: A, B, C. Если бы мы сначала добавляли левый, а потом правый, то вывод был бы: A, C, B.

Применение

Такой подход используется в алгоритмах, где необходимо обработать все узлы дерева, начиная с корня и углубляясь в левую ветвь, например, при сериализации дерева или поиске пути. Итеративная реализация предпочтительна рекурсивной в средах с ограниченным стеком вызовов, так как она позволяет избежать переполнения стека.

Вывод: Итеративный обход со стеком и правильным порядком добавления дочерних узлов (сначала правый, затем левый) обеспечивает прямой обход дерева, что полезно для задач, требующих обработки узлов в порядке "корень-лево-право", особенно при работе с глубокими деревьями.