Логическое представление и изображение деревьев.

Имеется ряд способов графического изображения деревьев. Пер-

вый способ заключается в использовании для изображения поддеревь-

ев известного метода диаграмм Венна, второй - метода вкладываю-

щихся друг в друга скобок, третий способ - это способ, применяе-

мый при составлении оглавлений книг. Последний способ, базирую-

щийся на формате с нумерацией уровней, сходен с методами, исполь-

зуемыми в языках программирования. При применении этого формата

каждой вершине приписывается числовой номер, который должен быть

меньше номеров, приписанных корневым вершинам присоединенных к

ней поддеревьев. Отметим, что корневые вершины всех поддереьев

данной вершины должны иметь один и тот же номер.

МЕТОД ВЛОЖЕННЫХ СКОБОК

(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), кроме того, операции над двоичными де-

ревьями выполняются просто и эффективно.