Двоичные деревья. 
Структуры и алгоритмы обработки данных

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

ДД можно реализовать двумя способами:

• · на основе массива записей с использованием индексных указателей
• · на базе механизма динамического распределения памяти с сохранением в каждой вершине адресов ее потомков (если они есть).

Второй способ является значительно более удобным и поэтому используется наиболее часто. В этом случае каждая вершина описывается как запись, содержащая как минимум три поля: информационную составляющую и два ссылочных поля для адресации потомков:

Type Tp = ^TNode; {объявление ссылочного типа данных}.

TNode = record

Inf: ;

Left, Right: Tp;

end;

Для обработки дерева достаточно знать адрес корневой вершины. Для хранения этого адреса надо ввести ссылочную переменную:

Var pRoot: Tp;

Тогда пустое дерево просто определяется установкой переменной pRoot в нулевое значение (например — nil).

Реализацию основных операций с ДД удобно начать с процедур обхода. Поскольку дерево является нелинейной структурой, то НЕ существует единственной схемы обхода дерева. Классически выделяют три основных схемы:

• · обход в прямом направлении
• · симметричный обход
• · обход в обратном направлении.

Для объяснения каждого из этих правил удобно воспользоваться простейшим ДД из трех вершин. Обход всего дерева следует проводить за счет последовательного выделения в дереве подобных простейших поддеревьев и применением к каждому из них соответствующего правила обхода. Выделение начинается с корневой вершины.

Сами правила обхода носят рекурсивный характер и формулируются следующим образом:

• 1. Обход в прямом направлении:
  • · обработать корневую вершину текущего поддерева
  • · перейти к обработке левого поддерева таким же образом
  • · обработать правое поддерево таким же образом.
• 2. Симметричный обход:
  • · рекурсивно обработать левое поддерево текущего поддерева
  • · обработать вершину текущего поддерева
  • · рекурсивно обработать правое поддерево
• 3. Обход в обратном направлении:
  • · рекурсивно обработать левое поддерево текущего поддерева
  • · рекурсивно обработать правое поддерево
  • · затем — вершину текущего поддерева.

В качестве примера по шагам рассмотрим обход следующего ДД с числовыми компонентами (10 вершин):

Обход в прямом порядке:

• 1. Выделяем поддерево 0−1-2
• 2. обрабатываем его корень — вершину 0
• 3. переходим к левому потомку и выделяем поддерево 1−3-4
• 4. обрабатываем его корень — вершину 1
• 5. выделяем левое поддерево 3-&# (здесь * обозначает пустую ссылку)
• 6. обрабатываем его корень — вершину 3
• 7. т.к. левого потомка нет, обрабатываем правое поддерево
• 8. т.к. правого поддерева нет, возвращаемся к поддереву 1−3-4
• 9. выделяем поддерево 4−6-7
• 10. обрабатываем его корень — вершину 4
• 11. выделяем левое поддерево 6-&#
• 12. обрабатываем его корень — вершину 6
• 13. т.к. левого потомка нет, обрабатываем правое поддерево
• 14. т.к. правого потомка нет, то возвращаемся к поддереву 4−6-7
• 15. выделяем правое поддерево 7-&#
• 16. обрабатываем его корень — вершину 7
• 17. т.к. левого поддерева нет, обрабатываем правое поддерево
• 18. т.к. правого поддерева нет, то возвращаемся к поддереву 4−6-7
• 19. т.к. поддерево 4−6-7 обработано, то возвращаемся к поддереву 1−3-4
• 20. т.к. поддерево 1−3-4 обработано, возвращаемся к поддереву 0−1-2
• 21. выделяем правое поддерево 2-*-5
• 22. обрабатываем его корень — вершину 2
• 23. т.к. левого потомка нет, обрабатываем правого потомка
• 24. выделяем поддерево 5−8-9
• 25. обрабатываем его корень — вершину 5
• 26. выделяем левое поддерево 8-&#
• 27. обрабатываем его корень — вершину 8
• 28. т.к. левого поддерева нет, обрабатываем правое поддерево
• 29. т.к. правого поддерева нет, то возвращаемся к поддереву 5−8-9
• 30. выделяем правое поддерево 9-&#
• 31. обрабатываем его корень — вершину 9
• 32. т.к. левого поддерева нет, обрабатываем правое поддерево
• 33. т.к. правого поддерева нет, то возвращаемся к поддереву 5−8-9
• 34. т.к. поддерево 5−8-9 обработано, то возвращаемся к поддереву 2-*-5
• 35. т.к. поддерево 2-*-5 обработано, то возвращаемся к поддереву 0−1-2
• 36. т.к. поддерево 0−1-2 полностью обработано, то обход закончен

В итоге получаем следующий порядок обхода вершин: 0−1-3−4-6−7-2−5-8−9.

В более краткой записи симметричный обход дает следующие результаты:

Итого: 3−1-6−4-7−0-2−8-5−9

Аналогично, обход в обратном порядке дает:

Итого: 3−6-7−4-1−8-9−5-2−0

Видно, что результирующая последовательность вершин существенно зависит от правила обхода. Иногда используются разновидности трех основных правил, например — обход в обратно-симметричном порядке: правое поддерево — корень — левое поддерево.

Учитывая рекурсивный характер правил обхода, программная их реализация наиболее просто может быть выполнена с помощью рекурсивных подпрограмм. Каждый рекурсивный вызов отвечает за обработку своего текущего поддерева. Из приведенных выше примеров видно, что после полной обработки текущего поддерева происходит возврат к поддереву более высокого уровня, а для этого надо запоминать и в дальнейшем восстанавливать адрес корневой вершины этого поддерева. Рекурсивные вызовы позволяют выполнить это запоминание и восстановление автоматически, если описать адрес корневой вершины поддерева как формальный параметр рекурсивной подпрограммы.

Каждый рекурсивный вызов прежде всего должен проверить переданный ей адрес на nil. Если этот адрес равен nil, то очередное обрабатываемое поддерево является пустым и никакая его обработка не нужна, поэтому просто происходит возврат из рекурсивного вызова. В противном случае в соответствии с реализуемым правилом обхода производится либо обработка вершины, либо рекурсивный вызов для обработки левого или правого поддерева.

Рекурсивная реализация обхода в прямом направлении:

Procedure Forward (pCurrent: Tp);

Begin.

If pCurrent nil then.

Begin.

" обработка корневой вершины pCurrent^ «;

Forward (pCurrent^.Left);

Forward (pCurrent^.Right);

End;

End;

Первоначальный вызов рекурсивной подпрограммы производится в главной программе, в качестве стартовой вершины задаётся адрес корневой вершины дерева: Forward (pRoot).

Остальные две процедуры обхода с именами Symmetric и Back отличаются только порядком следования трех основных инструкций в теле условного оператора.

Для симметричного прохода:

Symmetric (pCurrent^.Left);

" обработка корневой вершины pCurrent^ «;

Symmetric (pCurrent^.Right);

Для обратного прохода:

Back (pCurrent^.Left);

Back (pCurrent^.Right);

" обработка корневой вершины pCurrent^ «;

В принципе, достаточно легко реализовать нерекурсивный вариант процедур обхода, если учесть, что рекурсивные вызовы и возвраты используют стековый принцип работы. Например, рассмотрим схему реализации нерекурсивного симметричного обхода. В соответствии с данным правилом сначала надо обработать всех левых потомков, т. е. спустится влево максимально глубоко. Каждое продвижение вниз к левому потомку приводит к запоминанию в стеке адреса бывшей корневой вершины. Тем самым для каждой вершины в стеке запоминается путь к этой вершине от корня дерева.

Обращение к рекурсивной процедуре для обработки левого потомка надо заменить помещением в стек адреса текущей корневой вершины и переходом к левому потомку этой вершины. Обработка правого потомка заключается в извлечении из стека адреса некоторой вершины и переходе к её правому потомку.

Для нерекурсивного обхода дерева необходимо объявить вспомогательную структуру данных — стек. В информационной части элементов стека должны храниться адреса узлов этого дерева, поэтому ее надо описать с помощью соответствующего ссылочного типа Tp.

Схематично нерекурсивный симметричный обход выглядит следующим образом:

pCurrent:= pRoot; {начинаем с корневой вершины дерева}.

Stop:= false; {вспомогательная переменная}.

while (not stop) do {основной цикл обхода}.

begin.

while pCurrent nil do {обработка левых потомков}.

begin.

" занести pCurrent в стек" ;

pCurrent:= pCurrent^.left;

end;

if «стек пуст» then stop:= true {обход закончен}.

else.

begin.

" извлечь из стека адрес и присвоить его pCurrent «;

" обработка узла pCurrent «;

pCurrent:= pCurrent^.right;

end;

end;

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

Еще одним интересным применением процедур обхода является уничтожение всего дерева с освобождением занимаемой вершинами памяти. Ясно, что в простейшем поддереве надо сначала удалить левого и правого потомка, а уже затем — саму корневую вершину. Здесь наилучшим образом подходит правило обхода в обратном направлении.

Разные правила обхода часто используются для вывода структуры дерева в наглядном графическом виде. Например, для рассмотренного выше дерева с десятью вершинами применение разных правил обхода позволяет получить следующие представления дерева:

Из этих примеров видно, что наличие нескольких правил обхода дерева вполне обоснованно, и в каждой ситуации надо выбирать подходящее правило.