Бинарное дерево — это иерархическая структура, в которой каждый узел имеет не более двух потомков, называемых left и right. Оно имеет один ; узлы без потомков — это . Это основа для BST, куч и деревьев выражений.
Бинарное дерево — это иерархическая структура, в которой каждый узел имеет не более двух потомков, называемых left и right. Оно имеет один ; узлы без потомков — это . Это основа для BST, куч и деревьев выражений.
1 depth 0 (root)
/ \
2 3 depth 1
/ \
4 5 depth 2 (leaves: 4,5,3)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder(n): # left, node, right -> 4 2 5 1 3
if n:
inorder(n.left); print(n.val); inorder(n.right)
def preorder(n): # node, left, right -> 1 2 4 5 3
if n:
print(n.val); preorder(n.left); preorder(n.right)
def postorder(n): # left, right, node -> 4 5 2 3 1
if n:
postorder(n.left); postorder(n.right); print(n.val)
Обход level-order (BFS) использует очередь и посещает узлы на глубину за глубиной.
| Обход | Порядок | Обычное применение |
|---|---|---|
| Inorder | L, N, R | отсортированный вывод BST |
| Preorder | N, L, R | копирование/сериализация дерева |
| Postorder | L, R, N | удаление дерева, вычисление выражения |
| Level-order | по глубине | BFS, кратчайший путь в дереве |
Каждый обход посещает каждый узел один раз → O(n) время, O(h) место в стеке, где h — высота дерева.
Бинарные деревья естественным образом моделируют иерархические данные (файловые системы, деревья разбора, деревья решений) и лежат в основе эффективных структур поиска и сортировки.
Овладение четырьмя обходами необходимо — большинство задач на собеседование по деревьям представляют собой вариацию одного из них.