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

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

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
def postorder_recursive(node):
    if node is None:
        return
    # Traverse left subtree
    postorder_recursive(node.left)
    # Traverse right subtree
    postorder_recursive(node.right)
    # Visit the root node
    print(node.value, end=" ")
# Usage example
root = Node(4)
root.left = Node(2)
root.right = Node(6)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(5)
root.right.right = Node(7)
print("Postorder traversal (recursive):")
postorder_recursive(root)

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

def postorder_iterative(node):
    if node is None:
        return
    stack = []
    result = []
    current = node
    while True:
        while current:
            if current.right:
                stack.append(current.right)
            stack.append(current)
            current = current.left
        current = stack.pop()
        if (
            current.right is not None
            and stack
            and current.right == stack[-1]
        ):
            stack.pop()
            stack.append(current)
            current = current.right
        else:
            result.append(current.value)
            current = None
        if not stack:
            break
    # Print the result in reverse order to get postorder traversal
    print(" ".join(str(x) for x in result[::-1]))
# Usage example
root = Node(4)
root.left = Node(2)
root.right = Node(6)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(5)
root.right.right = Node(7)
print("Postorder traversal (iterative):")
postorder_iterative(root)

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

def postorder_morris(node):
    if node is None:
        return
    result = []
    current = node
    while current:
        if current.right is None:
            result.append(current.value)
            current = current.left
        else:
            successor = current.right
            while successor.left and successor.left != current:
                successor = successor.left
            if successor.left is None:
                successor.left = current
                result.append(current.value)
                current = current.right
            else:
                successor.left = None
                current = current.left
    # Print the result in reverse order to get postorder traversal
    print(" ".join(str(x) for x in result[::-1]))
# Usage example
root = Node(4)
root.left = Node(2)
root.right = Node(6)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(5)
root.right.right = Node(7)
print("Postorder traversal (Morris):")
postorder_morris(root)

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