35. Бинарные деревья
В этом разделе мы рассмотрим различные алгоритмы обхода бинарного дерева. К алгоритмам создания бинарного дерева мы обратимся несколько позже, а пока будем считать, что дерево уже создано и хранится в динамической памяти именно как древовидная структура (хотя это и не обязательно, можно хранить дерево в массиве, такой способ называется линейной проекцией дерева). Обойти дерево — значит обработать в заданном порядке все его вершины. В простейшем случае достаточно просто вывести значения всех элементов, записанных в вершинах дерева, тогда мы получим линейную запись дерева. Различают три различных способа обхода: префиксный, постфиксный и инфиксный. Префиксный обход осуществляется в последовательности корень — левое поддерево в префиксном порядке — правое поддерево в префиксном порядке. Обход в постфиксном порядке — это левое поддерево в постфиксном порядке — правое поддерево в постфиксном порядке — корень. Инфиксный обход — это обход в последовательности левое поддерево в инфиксном порядке — корень — правое поддерево в инфиксном порядке. Пусть, например, дерево имеет вид:
Тогда его префиксная запись — abdecfg, постфиксная запись — debfgca и инфиксная запись — dbeafcg. Часто используют скобочные постфиксную, префиксную и инфиксную записи дерева. В скобочной линейной записи запись каждого поддерева заключается в скобки. Так, в нашем примере скобочная префиксная запись имеет вид (a(b(d)(e))(c(f)(g))), скобочная постфиксная запись — (((d)(e)b)((f)(g)c)a), скобочная инфиксная запись — (((d)b(e))a((f)c(g))). Иногда опускают внешнюю пару скобок. Бесскобочные линейные записи дерева пригодны только для работы со строго бинарными деревьями, в которых все уровни заполнены и количество вершин равно 2 h -1, где h — высота дерева, тогда по линейной бесскобочной записи можно однозначно восстановить структуру дерева, но если дерево не является строго бинарным, то различные деревья могут иметь одинаковые линейные записи. Пусть, например, дерево имеет вид:
В его скобочных линейных записях необходимо обозначать отсутствующие поддеревья всех вершин, кроме листьев; например, префиксная запись поддерева с корнем в c в виде c(g) недостаточна, так как неясно, каким именно потомком является g — левым или правым. Это поддерево необходимо записать в виде c()(g). Полные скобочные записи этого дерева имеют вид: префиксная — (a(b(d(e)(f))())(c()(g))) , постфиксная — ((((e)(f)d)()b)(()(g)c)a) , инфиксная — ((((e)d(f))b())a(()c(g))).
Известно много различных алгоритмов обхода бинарного дерева. Самый простой из них — это рекурсивный обход. Пусть дерево размещается в хипе и описано в программе в виде:
Запишем рекурсивную процедуру префиксного обхода.
Источник
Способы обхода бинарных деревьев
Обход дерева — процесс посещения всех его вершин в определенном порядке. Существует несколько способов обхода (прохождения) всех узлов дерева. Три наиболее часто используемые способа обхода:
- обход в прямом порядке,
- обход в обратном порядке,
- обход во внутреннем порядке (симметричный обход).
Сортировка с прохождением бинарного дерева
В качестве примера использования прохождения бинарного дерева можно привести один из способов сортировки. Допустим, мы имеем некоторый массив и пытаемся упорядочить его элементы по возрастанию. Сама сортировка при этом распадается на две фазы 1. построение дерева; 2. прохождение дерева в симметричном порядке. Дерево строится по следующим принципам. В качестве корня создается узел, в который записывается первый элемент массива. Для каждого очередного элемента создается новый лист. Если элемент меньше значения в текущем узле, то для него выбирается левое поддерево, если больше или равен — правое. Для создания очередного узла происходят сравнения элемента со значениями существующих узлов, начиная с корня. Во время второй фазы происходит прохождение дерева в симметричном порядке. Результатом сортировки является последовательность значений элементов, извлекаемых их пройденных узлов. Для того чтобы сделать сортировку по убыванию, необходимо изменить только условия выбора поддерева при создании нового узла во время построения дерева.
Источник