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

Что такое обход Морриса?
Обход Морриса — это алгоритм обхода дерева, который позволяет нам перемещаться по двоичному дереву без использования каких-либо дополнительных структур данных, таких как стеки или очереди. Это достигается путем временного изменения структуры дерева. Этот алгоритм в основном используется для обхода дерева по порядку, но его также можно адаптировать для обхода в предварительном и послепорядковом порядке.

Метод 1: обход по порядку Морриса
Первый метод, который мы рассмотрим, — это обход по порядку Морриса. Этот метод позволяет нам посещать узлы бинарного дерева в порядке возрастания.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def morris_inorder(root):
    current = root
    while current:
        if not current.left:
            print(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                print(current.val)
                current = current.right
# Usage example
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
morris_inorder(root)

Метод 2: обход предварительного заказа Морриса
Второй метод, который мы рассмотрим, — это обход предварительного заказа Морриса. Этот метод позволяет нам посещать узлы бинарного дерева в предварительной последовательности.

def morris_preorder(root):
    current = root
    while current:
        if not current.left:
            print(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current
                print(current.val)
                current = current.left
            else:
                predecessor.right = None
                current = current.right
# Usage example (using the same tree as before)
morris_preorder(root)

Метод 3: обход постпорядка Морриса
Третий метод, который мы рассмотрим, — это обход постпорядка Морриса. Этот метод позволяет нам посещать узлы бинарного дерева в пост-порядке.

def reverse_nodes(start, end):
    if start == end:
        return
    prev = None
    current = start
    while prev != end:
        next_node = current.right
        current.right = prev
        prev = current
        current = next_node
def print_reverse(start, end):
    reverse_nodes(start, end)
    current = end
    while current != start:
        print(current.val)
        current = current.right
    reverse_nodes(end, start)
def morris_postorder(root):
    dummy = TreeNode(0)
    dummy.left = root
    current = dummy
    while current:
        if not current.left:
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current
                current = current.left
            else:
                print_reverse(current.left, predecessor)
                predecessor.right = None
                current = current.right
# Usage example (using the same tree as before)
morris_postorder(root)

Morris Traversal обеспечивает эффективный способ обхода двоичных деревьев без использования дополнительных структур данных. Мы исследовали три метода: обход по порядку Морриса, обход по предварительному заказу Морриса и обход по посту Морриса, каждый из которых имеет свой собственный пример кода. Используя уникальные свойства обхода Морриса, мы можем оптимизировать обход деревьев и повысить эффективность наших алгоритмов.

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

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