Имеется ряд способов графического изображения деревьев. Пер-
вый способ заключается в использовании для изображения поддеревь-
ев известного метода диаграмм Венна, второй - метода вкладываю-
щихся друг в друга скобок, третий способ - это способ, применяе-
мый при составлении оглавлений книг. Последний способ, базирую-
щийся на формате с нумерацией уровней, сходен с методами, исполь-
зуемыми в языках программирования. При применении этого формата
каждой вершине приписывается числовой номер, который должен быть
меньше номеров, приписанных корневым вершинам присоединенных к
ней поддеревьев. Отметим, что корневые вершины всех поддереьев
данной вершины должны иметь один и тот же номер.
МЕТОД ВЛОЖЕННЫХ СКОБОК
(V0(V1(V2(V5)(V6))(V3)(V4))(V7(V8)(V9(V10))))
а) (V0) б) V0├────────────────┤
/ V1├────────────┤
(V1) (V7) V2├────────┤
/ | | V5├────┤
(V2) (V3) (V4) (V8)(V9) V6├────┤
/ V3├────────┤
(V5)(V6) (V10) V4├────────┤
V7├────────────┤
V8├────────┤
V9├────────┤
V10├────┤
в) г) ┌────────────────────────────────────┐
┌──┐ │V0 │
│V0│ │┌──────────────┐ ┌─────────────────┐│
└┬┬┘ ││V1 ┌─────────┐│ │V7 ││
┌──┘└─────┐ ││ │V3 ││ │ ┌─────┐┌───────┐││
┌─┴─┐ ┌──┴┐ ││ └─────────┘│ │ │V8 ││V9 │││
│V1 │ │ V7│ ││┌────────────┐│ │ │ ││┌─────┐│││
└┬┬┬┘ └┬┬─┘ │││V4 ││ │ │ │││V10 ││││
┌──┘│└─┐ │└──┐ ││└────────────┘│ │ │ │││ ││││
┌─┴┐┌─┴┐┌┴─┐┌─┴┐┌─┴─┐ ││┌────────────┐│ │ │ │││ ││││
│V2││V3││V4││V8││V9 │ │││V2 ││ │ │ ││└─────┘│││
└┬┬┘└──┘└──┘└──┘└─┬─┘ │││┌────┐┌────┐││ │ │ ││ │││
┌─┘└┐ │ ││││V5 ││V6 │││ │ │ ││ │││
┌─┴┐ ┌┴─┐ ┌─┴─┐ │││└────┘└────┘││ │ │ ││ │││
│V5│ │V6│ │V10│ ││└────────────┘│ │ └─────┘└───────┘││
└──┘ └──┘ └───┘ │└──────────────┘ └─────────────────┘│
└────────────────────────────────────┘
Рис.6.11. Представление дерева : а)- исходное дерево,
б)- оглавление книг, в)- граф, г)- диаграмма Венна
Все эти представления демонстрируют одну и ту же структуру и
поэтому эквивалентны. С помощью графа можно наглядно представить
разветвляющиеся связи, которые по понятным причинам привели к об-
щеупотребительному термину "дерево".
6.2.3. Бинарные деревья.
Существуют m-арные деревья, т.е. такие деревья у которых по-
лустепень исхода каждой вершины меньше или равна m (где m может
быть равно 0,1,2,3 и т.д.). Если полустепень исхода каждой верши-
ны в точности равна либо m, либо нулю, то такое дерево называется
ПОЛНЫМ m-АРНЫМ ДЕРЕВОМ.
При m=2 такие деревья называются соответственно БИНАРНЫМИ,
или ПОЛНЫМИ БИНАРНЫМИ.
На рисунке 6.12(a) изображено бинарное дерево, 6.12(b)- пол-
ное бинарное дерево, а на 6.12(c) показаны все четыре возможных
расположения сыновей некоторой вершины бинарного дерева.
a) b)
┌────┐ ┌────┐
│ │ │ │
└┬──┬┘ └┬──┬┘
┌──┘ └──┐ ┌──┘ └──┐
┌───┴┐ ┌┴───┐ ┌───┴┐ ┌┴───┐
│ 0 │ │ 1 │ │ 0 │ │ 1 │
└┬──┬┘ └───┬┘ └┬──┬┘ └┬──┬┘
┌──┘ └─┐ │ ┌──┘ └─┐ ┌─┘ └──┐
┌┴───┐ ┌┴───┐ ┌─┴──┐ ┌───┴┐ ┌───┴┐ ┌─┴──┐ ┌┴───┐
│ 00 │ │ 01 │ │ 11 │ │ 00 │ │ 01 │ │ 10 │ │ 11 │
└────┘ └────┘ └────┘ └────┘ └┬──┬┘ └────┘ └────┘
┌─┘ │
┌───┴┐ ┌┴───┐
│010 │ │011 │
└────┘ └────┘
┌───┐
с) ┌──┐ ┌──┐ ┌──┐ ┌──┐ d) │ │
│ │ │ │ │ │ │ │ └┬─┬┘
└──┘ └┬─┘ └─┬┘ └┬┬┘ ┌──┘ └──┐
┌─┘ └─┐ ┌─┘└──┐ ┌──┴┐ ┌┴─┐
┌┴──┐ ┌─┴─┐ ┌──┴┐ ┌┴──┐ │ 0 │ │ 1│
│ 0 │ │ 1 │ │ 0 │ │ 1 │ └┬─┬┘ └┬─┘
└───┘ └───┘ └───┘ └───┘ ┌─┘ └─┐ │
┌┴─┐ ┌┴─┐ ┌┴─┐
│00│ │01│ │10│
└──┘ └──┘ └──┘
Рис. 6.13. Изображения бинарных деревьев
Бинарные деревья, изображенные на рис.6.13(a) и 6.13(d),
представляют собой разные позиционные деревья, хотя они не явля-
ются разными упорядоченными деревьями.
В позиционном бинарном дереве каждая вершина представлена
единственным образом посредством строки символов над алфавитом
{0,1}, при этом корень характеризуется пустой строкой. Любой сын
вершины "u" характеризуется строкой, префикс (начальная часть)
которой является строкой, характеризующей "u".
Примером бинарного дерева является фамильное дерево с отцом
и матерью человека в качестве его потомков. Еще один пример - это
арифметическое выражение с двухместными операциями, где каждая
операция представляет собой ветвящийся узел с операндами в ка-
честве поддеревьев.
Представить m-арное дерево в памяти ЭВМ сложно, т.к. каждый
элемент дерева должен содержать столько указателей, сколько ребер
выходит из узла (при m-3,4.5.6... соответствует 3,4,5,6... указа-
телей). Это приведет к повышенному расходу памяти ЭВМ, разнообра-
зию исходных элементов и усложнит алгоритмы обработки дерева. По-
этому m-арные деревья, лес необходимо привести к бинарным для
экономии памяти и упрощению алгоритмов. Все узлы бинарного дерева
представляются в памяти ЭВМ однотипными элементами с двумя указа-
телями (см.разд. 6,2,5), кроме того, операции над двоичными де-
ревьями выполняются просто и эффективно.