Рекурсивный обход дерева python

Рекурсивный обход дерева на Python

Рекурсивный обход дерева — это мощный и элегантный способ обработки узлов в древовидной структуре данных. Суть рекурсии заключается в том, что функция вызывает саму себя для решения подзадач, пока не достигнет базового случая (например, листа дерева или пустого узла).

Рассмотрим основные типы рекурсивного обхода бинарного дерева:

Прямой обход (Pre-order traversal): Корень -> Левое поддерево -> Правое поддерево Симметричный обход (In-order traversal): Левое поддерево -> Корень -> Правое поддерево Обратный обход (Post-order traversal): Левое поддерево -> Правое поддерево -> Корень

Прежде чем показать примеры, давайте определим простую структуру узла дерева.

Python

Class TreeNode:

def __init__(self, value):

self. value = value

self. left = None

self. right = None

# Создадим простое дерево для примера:

# 4

# / \

# 2 5

# / \

# 1 3

Root = TreeNode(4)

Root. left = TreeNode(2)

Root. right = TreeNode(5)

Root. left. left = TreeNode(1)

Root. left. right = TreeNode(3)

1. Прямой Обход (Pre-order traversal)

В прямом обходе мы сначала посещаем Корень, затем рекурсивно обходим Левое поддерево, и в конце рекурсивно обходим Правое поддерево.

Порядок посещения: Корень -> Левое поддерево -> Правое поддерево

Python

Def pre_order_traversal(node):

if node is None:

return

print(node. value, end=" ") # Посещаем корень

pre_order_traversal(node. left) # Обходим левое поддерево

pre_order_traversal(node. right) # Обходим правое поддерево

Print("Прямой обход (Pre-order):")

Pre_order_traversal(root) # Вывод: 4 2 1 3 5

Print("\n")

2. Симметричный Обход (In-order traversal)

В симметричном обходе мы сначала рекурсивно обходим Левое поддерево, затем посещаем Корень, и в конце рекурсивно обходим Правое поддерево. Для бинарного дерева поиска этот обход выдает значения в отсортированном порядке.

Порядок посещения: Левое поддерево -> Корень -> Правое поддерево

Python

Def in_order_traversal(node):

if node is None:

return

in_order_traversal(node. left) # Обходим левое поддерево

print(node. value, end=" ") # Посещаем корень

in_order_traversal(node. right) # Обходим правое поддерево

Print("Симметричный обход (In-order):")

In_order_traversal(root) # Вывод: 1 2 3 4 5 (отсортировано, т. к. это бинарное дерево поиска)

Print("\n")

3. Обратный Обход (Post-order traversal)

В обратном обходе мы сначала рекурсивно обходим Левое поддерево, затем рекурсивно обходим Правое поддерево, и в конце посещаем Корень. Этот обход часто используется для удаления дерева, так как сначала удаляются дочерние узлы, а затем родительские.

Порядок посещения: Левое поддерево -> Правое поддерево -> Корень

Python

Def post_order_traversal(node):

if node is None:

return

post_order_traversal(node. left) # Обходим левое поддерево

post_order_traversal(node. right) # Обходим правое поддерево

print(node. value, end=" ") # Посещаем корень

Print("Обратный обход (Post-order):")

Post_order_traversal(root) # Вывод: 1 3 2 5 4

Print("\n")

Когда использовать каждый тип обхода?

Прямой обход: Используется для создания копии дерева, для представления дерева в виде выражения (префиксная запись). Симметричный обход: Используется для получения отсортированного списка элементов бинарного дерева поиска. Обратный обход: Используется для удаления дерева (освобождения памяти), для вычисления выражений (постфиксная запись).

Эти примеры демонстрируют базовые принципы рекурсивного обхода. Рекурсия делает код более чистым и интуитивно понятным для работы с древовидными структурами.