Исходный код EJIO.utils.struct.tree

## /utils/struct/tree.py

from abc import abstractmethod
from typing import Protocol, Iterable
from collections.abc import Generator
from typing import Any
from ..interface import StaticClass
from .stack import Stack
from .queue import Queue


__all__ = [
    'TreeNode',
    'TreeTraverser',
]




class TreeNode(Protocol):
    """
    Абстрактный протокол, описывающий минимальный контракт для узла любого дерева.
    """
    __slots__ = ()

    @property
    @abstractmethod
    def value(self) -> Any:
        """
        Возвращает полезную нагрузку (данные), хранящуюся в узле.

        :return: Значение хранящееся в узле.
        :raises NotImplementedError: Должен быть реализован в подклассе.
        """
        raise NotImplementedError

    @property
    @abstractmethod
    def children(self) -> Iterable['TreeNode']:
        """
        Возвращает итерируемый объект со всеми дочерними узлами (потомками).

        :return: Итератор по всем дочерним узлам.
        :raises NotImplementedError: Должен быть реализован в подклассе.
        """
        raise NotImplementedError



    @abstractmethod
    def destroy(self) -> None:
        """
        Каскадно уничтожает текущий узел и всех его потомков,
        разрывая циклические ссылки и высвобождая память.

        :raises NotImplementedError: Должен быть реализован в подклассе.
        """
        raise NotImplementedError


    def __del__(self) -> None:
        """Очищает память при удалении объекта, чтобы избежать рекурсии."""
        self.destroy()





class TreeTraverser(StaticClass):
    """
    Статический алгоритмический движок для итеративного обхода древовидных структур.
    Работает с любыми деревьями, поддерживающими протокол TreeNode.
    """
    __slots__ = ()



    @classmethod
    def depth_first_search[T: TreeNode](cls, root: T) -> Generator[T, None, None]:
        """
        Итеративный обход дерева в глубину (DFS / Pre-order).
        Использует стек. Безопасен для глубоких деревьев.

        :param root: Корень дерева, обход которого необходимо совершить.
        :yields: Узлы дерева в порядке обхода.
        """
        if root is None:
            return

        stack: Stack[T] = Stack()
        stack.push(root)

        while not stack.empty:
            node = stack.pop()
            yield node

            # Складываем детей в стек с конца, чтобы левые ветви обрабатывались первыми
            # Преобразуем Iterable в развернутый список для безопасного реверса
            children_list = list(node.children)
            for child in reversed(children_list):
                if child is not None:
                    stack.push(child) # type ignore[arg-type]




    @classmethod
    def breadth_first_search[T: TreeNode](cls, root: T) -> Generator[T, None, None]:
        """
        Итеративный обход дерева в ширину (BFS / По уровням).
        Использует очередь из utils. Идеален для поиска кратчайших путей в графах/деревьях.

        :param root: Корень дерева, обход которого необходимо совершить.
        :yields: Узлы дерева в порядке обхода.
        """
        if root is None:
            return

        queue: Queue[T] = Queue()
        queue.push(root)

        while not queue.empty:
            node = queue.pop()
            yield node

            for child in node.children:
                if child is not None:
                    queue.push(child) #type ignore[arg-type]