1.5 Деревья 8
Деревья, пожалуй, являются одними из наиболее важных нелинейных структур, которые встречаются при работе с компьютерными алгоритмами.
Формально дерево определяется как конечное множество Т одного или более узлов со следующими свойствами:
существует один выделенный узел, а именно- корень данного дерева Т;
остальные узлы (за исключением корня) распределены среди m0 непересекающихся множеств T_1,....T_m, и каждое из этих множеств, в свою очередь, является деревом; деревья Т_1,..., Т_m называются поддеревьями данного корня.
Данное определение является рекурсивным: дерево определено на основе понятия дерева.
На рис. 6 изображено дерево. Корневой узел А соединен с тремя поддеревьями, начинающимися узлами В, С и D. Эти узлы соединены с поддеревьями, имеющими корни в узлах Е, F и G, которые в свою очередь связаны с поддеревьями с корнями Н, I и J.
Данная терминология является смесью терминов, заимствованных из ботаники и генеалогии. Из ботаники взято определение узла, который представляет собой точку, где может возникнуть ветвь. Ветвь описывает связь между двумя узлами, лист - узел, откуда не выходят другие ветви.
Рис. 6. Дерево
Из генеалогии пришли термины, описывающие отношения. Если узел находится непосредственно над другим, то он называется родительским, а нижний узел называется дочерним. Узлы на пути вверх от узла до корня принято считать предками узла. Например, на рис. 6 предками узла I являются узлы Е, В и А. Все узлы, расположенные ниже какого-либо узла, называются его потомками. На рис. 6 потомками узла В являются узлы Е, Н, I и J. Узлы, имеющие одного и того же родителя, называются сестринскими.
Кроме того, существует несколько понятий, возникших собственно в программистской среде. Внутренний узел - это узел, не являющийся листом. Порядком узла или его степенью называется количество его дочерних узлов. Степень дерева - это максимальный порядок его узлов. Степень дерева, изображенного на рис. 6, равна 3, так как узлы А и Е, имеющие максимальную степень, имеют по три дочерних узла.
Высота узла равна числу его предков плюс 1. На рис. 6 узел Е имеет высоту 3. Высота дерева - это наибольшая высота всех узлов. Высота дерева, изображенного на рис. 6, равна 4.
Дерево степени 2 называется двоичным или бинарным деревом. Деревья степени 3 называются троичными или тернарными. Аналогично дерево степени N называется N-ичным деревом.
Если в расположении узлов дерева имеет значение относительный порядок поддеревьев, то дерево является упорядоченным.
Лес - это множество, не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
Между абстрактными понятиями леса и деревьев существует не очень заметная разница. При удалении корня дерева получается лес, и наоборот: при добавлении одного узла в лес, все деревья которого рассматриваются как поддеревья нового узла, получается дерево.
Обход деревьев
Последовательное обращение ко всем узлам дерева называется обходом. Существует несколько последовательностей обхода узлов двоичного дерева. Три самых простых - прямой, симметричный и обратный, которые реализуются с помощью достаточно простых рекурсивных алгоритмов. Для каждого заданного узла алгоритм выполняет следующие действия:
Прямой порядок:
Обращение к узлу.
Рекурсивный прямой обход левого поддерева.
Рекурсивный прямой обход правого поддерева.
Симметричный порядок:
Рекурсивный симметричный обход левого поддерева.
Обращение к узлу.
Рекурсивный симметричный обход правого поддерева.
Обратный порядок:
Рекурсивный обратный обход левого поддерева.
Рекурсивный обратный обход правого поддерева.
Обращение к узлу.
Для дерева, изображенного на рисунке 7, порядок обхода будет следующим:
Рис. 7. Пример дерева для иллюстрации различных методов его обхода
Прямой порядок: A, B, D, С, Е, G, F, H, J
Симметричный порядок: D, B, A, E, G, C, H, F, J
Обратный порядок: D, B, G, E, H, J, F, C, A