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

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

def dfs(root, target, path, result):
    if root is None:
        return
    # Append the current node to the path
    path.append(root)
    if root == target:
        # Store a copy of the current path in the result
        result.extend(path)
    # Recurse on the children
    for child in root.children:
        dfs(child, target, path, result)
    # Remove the current node from the path (backtracking)
    path.pop()
# Example usage
root = Node(1)
# Build your tree here...
target_node = find_target_node(root)  # Replace with your own logic to find the target node
path_to_target = []
result = []
dfs(root, target_node, path_to_target, result)

Метод 2: поиск в ширину (BFS) с очередью
BFS — это еще один алгоритм обхода графа, который можно использовать для поиска пути от корневого узла к целевому узлу. Используя очередь для хранения узлов, BFS гарантирует, что мы посещаем узлы уровень за уровнем. Вот пример реализации на Python:

from collections import deque
def bfs(root, target):
    if root is None:
        return None
    queue = deque([(root, [])])
    while queue:
        node, path = queue.popleft()
        if node == target:
            return path + [node]
        for child in node.children:
            queue.append((child, path + [node]))
    return None
# Example usage
root = Node(1)
# Build your tree here...
target_node = find_target_node(root)  # Replace with your own logic to find the target node
path_to_target = bfs(root, target_node)

Метод 3: рекурсивный подход
В этом методе мы используем рекурсивную функцию для поиска пути от корневого узла к целевому узлу. Вот пример реализации на Python:

def find_path_recursive(root, target):
    if root is None:
        return None
    if root == target:
        return [root]
    for child in root.children:
        path = find_path_recursive(child, target)
        if path is not None:
            return [root] + path
    return None
# Example usage
root = Node(1)
# Build your tree here...
target_node = find_target_node(root)  # Replace with your own logic to find the target node
path_to_target = find_path_recursive(root, target_node)