Деревья

Описание
Дерево является частным случаем графов. Если в график графов неориентированный и не имеет цикличности его можно назвать деревом и схематично отобразить в виде источника (вершина) с расходящимися ветвями ( ребра с вершинами)

from dataclasses import dataclass
from typing import ClassVar


@dataclass
class TreeNode:
    value: int
    left: ClassVar = None
    right: ClassVar = None

    def pre_order(self, node) -> None:
        if node:
            print(node.value)
            self.pre_order(node.left)
            self.pre_order(node.right)

    def post_order(self, node) -> None:
        if node:
            self.post_order(node.left)
            self.post_order(node.right)
            print(node.value)

    def in_order(self, node) -> None:
        if node:
            self.in_order(node.left)
            print(node.value)
            self.in_order(node.right)


if __name__ == '__main__':
    tree = TreeNode(1)
    tree.left = TreeNode(2)
    tree.right = TreeNode(3)
    tree.left.left = TreeNode(4)
    tree.left.right = TreeNode(5)

    tree.post_order(tree)
обход по дереву способом Pre-order
Сначала посещаем текущую вершину, затем рассматриваем её поддеревья.Pre-order стоит использовать тогда, когда вы знаете что вам нужно проверить узлы перед тем как проверять их листья.

В результате Pre-order обхода мы получим такой порядок : F, B, A,D,C,E,G,I,H

def pre_order(self, node) -> None:
        if node:
            print(node.value)
            self.pre_order(node.left)
            self.pre_order(node.right)
обход по дереву способом in-order
Рассматриваем левое поддерево, посещаем текущую вершину и затем рассматриваем правое поддерево.
Применим только к бинарным деревьям. In-order обход используется как раз когда нам надо проверять в начале детей и только потом подыматься к родительским узлам.

В таком случае мы получаем просто: A,B,C,D,E,F,G,H,I

def in_order(self, node) -> None:
        if node:
            self.in_order(node.left)
            print(node.value)
            self.in_order(node.right)
обход по дереву способом post-order
Рассматриваем все поддеревья текущей вершины, затем посещаем её. Post-order обход используется когда нам необходимо анализировать путь от листа до корня дерева.

В таком случае мы получаем просто: A, C, E, D, B, H, I, G,F

def post_order(self, node) -> None:
        if node:
            self.post_order(node.left)
            self.post_order(node.right)
            print(node.value)