В информатике и структурах данных под обходом дерева понимается процесс посещения каждого узла дерева ровно один раз. Одним из распространенных методов обхода дерева является обход по порядку. В этой статье мы рассмотрим различные методы упорядоченного обхода двоичного дерева, включая как рекурсивные, так и итеративные подходы. Мы предоставим примеры кода на Python для иллюстрации каждого метода.

1. Рекурсивный обход по порядку:
   Рекурсивный подход — это простой способ выполнить неупорядоченный обход. Он следует за левым поддеревом, посещает текущий узел, а затем рекурсивно обходит правое поддерево. Вот пример реализации на Python:

class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None
def inorder_recursive(node):
    if node is not None:
        inorder_recursive(node.left)
        print(node.data, end=" ")
        inorder_recursive(node.right)

2. Итеративный обход по порядку с использованием стека.
   Итеративный подход позволяет избежать рекурсивных вызовов функций за счет использования стека для отслеживания узлов. Он начинается с корня и неоднократно пересекает левого дочернего узла, пока не достигнет конечного узла. Затем он посещает узел, переходит к правому дочернему узлу и повторяет процесс. Вот пример реализации:

def inorder_iterative(root):
    stack = []
    current = root
    while True:
        if current is not None:
            stack.append(current)
            current = current.left
        elif stack:
            current = stack.pop()
            print(current.data, end=" ")
            current = current.right
        else:
            break

3. Обход по порядку Морриса:
   Обход Морриса — это оптимизированная по пространству версия обхода по порядку, которая не требует стека или рекурсии. Он временно изменяет структуру дерева, чтобы создать связанное двоичное дерево. Вот пример реализации:

def morris_inorder(root):
    current = root
    while current is not None:
        if current.left is None:
            print(current.data, end=" ")
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right is not None and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                print(current.data, end=" ")
                current = current.right

В этой статье мы рассмотрели три различных метода выполнения неупорядоченного обхода двоичного дерева. Мы обсудили рекурсивный подход, итеративный подход с использованием стека и обход Морриса. Каждый метод имеет свои преимущества и варианты использования в зависимости от конкретных требований решаемой проблемы. Понимая эти методы, вы сможете эффективно перемещаться по двоичным деревьям и обрабатывать узлы в желаемом порядке.