Обход дерева - это вид обхода графа, который обуславливает процесс посещения (проверки и/или обновления) каждого узла структуры дерева данных ровно один раз. Такие обходы классифицируются по порядку, в котором узлы посещаются. Алгоритмы в статье относятся к двоичным деревьям, но могут быть обобщены и для других деревьев.
Дерево – это структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.
Бинарное дерево – это конечное множество элементов, которое либо пусто, либо содержит элемент (корень), связанный с двумя различными бинарными деревьями, называемыми левыми и правами поддеревьями.
Для чего это нужно?
Бинарные деревья поиска обычно применяются для реализации множеств и ассоциативных массивов (например: set и map в c++ или Treeset и Treemap в java). Более сложные применения включают в себя ropes, различные алгоритмы вычислительной геометрии, в основном в алгоритмах на основе «сканирующей прямой».
Из чего состоит двоичное дерево?
Двоичное дерево состоит из вершин и связей между ними. Конкретнее, у дерева есть выделенная вершина-корень и у каждой вершины может быть левый и правый сыновья. На словах звучит несколько сложно, но если взглянуть на картинку все становится понятным:
