Графы и деревья
Поскольку любое дерево является графом , то его можно задавать любым из способов, перечисленных в п. «Способы представления графов «. Однако существуют и специальные способы представления, предназначенные только для деревьев . Мы рассмотрим только два наиболее распространенных частных случая.
Представление корневого дерева
Этот способ подходит только для тех корневых деревьев , у которых точно известно максимальное количество потомков для любой вершины .
type ukazatel = ^tree; tree = record znachenie : integer; siblings : array[1..S] of ukazatel; end;
Разумеется, в общем случае значение переменной S (количество потомков ) может достигать N-1 ( N — количество всех вершин в дереве ). Однако ясно, что в такой ситуации особого смысла в динамической древесной структуре нет: экономии памяти не получается. Гораздо лучше, если у всех вершин примерно одинаковое и заранее известное количество потомков .
Представление бинарного дерева
Разновидностью описанного выше частного случая является бинарное корневое дерево : каждая его вершина имеет не более двух потомков :
type ukazatel = ^tree; tree = record znachenie : integer; left_sibling : ukazatel; right_sibling: ukazatel; end;
Примеры использования деревьев
Здесь мы ограничимся только примерами использования бинарных корневых деревьев : именно такой вид графа чаще всего применяется в программировании.
Дерево двоичного поиска
Дерево двоичного поиска для множества чисел S — это размеченное бинарное дерево , каждой вершине которого сопоставлено число из множества S , причем все пометки удовлетворяют следующим условиям:
- существует ровно одна вершина , помеченная любым числом из множества S ;
- все пометки левого поддерева строго меньше, чем пометка текущей вершины ;
- все пометки правого поддерева строго больше, чем пометка текущей вершины .
Если выражаться простым языком, то структура дерева двоичного поиска подчиняется простому правилу: «если больше — направо, если меньше — налево».
Например, для набора чисел 7 , 3 , 5 , 2 , 8 , 1 , 6 , 10 , 9 , 4 , 11 получится такое дерево (см. рис. 11.14).
Для того чтобы правильно учесть повторения чисел, можно ввести дополнительное поле, которое будет хранить количество вхождений для каждого числа.
Более подробно процессы построения и анализа дерева бинарного поиска будут изложены в следующей лекции, посвященной алгоритмам, использующим деревья и графы .
Дерево частотного словаря
Дерево частотного словаря — это результат построения дерева двоичного поиска не для чисел, а для слов некоторого текста. Генерирование дерева частотного словаря полезно при подсчете количества вхождений каждого слова в некоторый текст.
Приведем описание структуры этого дерева :
type ukazatel = ^tree; derevo = record slovo : string[20]; kolichestvo : integer; levyj : ukazatel; pravyj: ukazatel; end;
Дерево синтаксического анализа
Дерево синтаксического анализа арифметического выражения — это бинарное дерево , листьями которого служат операнды, а остальными вершинами — операции, причем уровень вершины соответствует приоритету выполнения операции: чем ближе к листьям , тем приоритет выше.
Например, на рис. 11.15 изображено дерево синтаксического анализа для выражения ((a / (b + c)) + (x * (y — z))) .
Деревья синтаксического разбора строятся компиляторами во время синтаксического анализа программ. Помимо арифметических выражений, которые являются простейшим случаем, аналогичные, но более сложные деревья строятся для всех грамматических конструкций компилируемой программы.
Источник
Способы изображения древовидной структуры
В данном разделе будут рассмотрены возможные варианты изображения деревьев. Из всех рассмотренных вариантов будет выбран один для реализации поставленной задачи. Этот способ должен быть достаточно удобен для восприятия, а также для реализации средствами языка программирования C++.
1) Первый способ, и наиболее распространенный – Классическая диаграмма (см. рисунок 2).
Рисунок 2 – Классическая диаграмма
2) Вложенные скобки. Легко реализуется на языках программирования, но неудобен для восприятия (см. Рисунок 3).
Рисунок 3 — Вложенные скобки
3) Вложенные множества. Данный способ наглядный и удобный для восприятия, но возможны проблемы с его реализацией (см. Рисунок 4).
Рисунок 4 — Вложенные множества
4) Ломаная последовательность (см. Рисунок 5).
Рисунок 5 — Ломаная последовательность
Двоичное (бинарное) дерево
Двоиичное деерево — древовидная структура данных, в которой каждый узел имеет не более двух потомков. Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.
То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной).
Например, согласно этой грамматике, двоичное дерево можно было бы записать так (см. Рисунок 6):
Рисунок 6 — Двоичное дерево
Двоичное дерево поиска
Деревья двоичного поиска широко распространены в программировании. Значение содержимого каждой вершины дерева двоичного поиска:
1) Оба поддерева — левое и правое, являются двоичными деревьями поиска.
2) У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных узла X.
3) У всех узлов правого поддерева произвольного узла X значения ключей данных больше, нежели значение ключа данных узла X.
Распространенность деревьев двоичного поиска в программировании является следствием эффективности методов поиска в этих деревьях.
Рисунок 7 — Двоичное дерево поиска
Разработка программного комплекса. Описание алгоритмов, используемых в программном комплексе
После анализа предметной области было решено использовать следующие языковые средства C++ для решения поставленной задачи:
- Для хранения вершин дерева с описанием связей – структуры. Структуры в С++ используются для логического и физического объединения данных произвольных типов, так же как массивы служат для группирования данных одного типа.
- Также нам потребуется возможность обходить все вершины, т.к. обход дерева придется осуществлять несколько раз, удобно будет вынести это действие в отдельную функцию и при необходимости вызывать ее в теле основной программы. По мере увеличения размера и сложности программного комплекса следует разделить его на небольшие легко управляемые части, называемые функциями. Каждая функция в вашей программе должна выполнять определенную задачу. Если программе необходимо выполнить определенную задачу, то она вызывает соответствующую функцию, обеспечивая эту функцию информацией, которая ей понадобится в процессе обработки.
Источник
3.2. Деревья и леса
Другой подход к представлению иерархических структур представляют собой деревья и леса. Это наиболее распространенные структуры, которые используются как базовые большим количеством алгоритмов обработки данных, в связи с чем заслуживают самого пристального внимания.
Аналогично другим структурам данных, таким как линейные и иерархические списки, можно ввести понятие АТД «Дерево» или «Лес», представив формальную функциональную спецификацию. Однако такая спецификация будет мало полезна, поскольку имеется огромное количество алгоритмов, использующих деревья (леса), причем часто это деревья специального вида со своими специфическими функциями. Для большинства таких алгоритмов применение универсального типа «Дерево» или «Лес» приведет к неэффективной реализации. Поэтому деревья и леса обычно используются как составная часть более сложных АТД (очереди с приоритетами, множества, словари и т. д.). Некоторые из этих АТД будут рассмотрены далее.
В данной главе сосредоточим максимум внимания на деревьях и лесах как структурах данных. Для этого сначала рассмотрим их как абстрактные математические объекты, а затем перейдем к различным формам представления в памяти и соответствующим алгоритмам.
3.2.1. Определения
Когда речь идет об иерархических структурах, то под термином «дерево» обычно понимают дерево с корнем (корневое дерево). Однако заметим, что корневое дерево — это частный случай более общего определения дерева, называемого иначе свободным деревом. Свободные деревья, в свою очередь, являются частным случаем графов и определяются в терминах теории графов. Они будут рассмотрены позже.В данной главе будем рассматривать только корневые деревья, называя их просто деревьями.
Особый вид иерархических структур — бинарные деревья — будут рассмотрены отдельно.
Формально дерево можно рекурсивно определить следующим образом[8].
Дерево (tree) — конечное множество T одного или более узлов (nodes) со следующими свойствами:
- Существует один выделенный узел, называемый корнем (root) этого дерева T. Дерево может состоять и из одного корня.
- Остальные узлы (если они есть) распределены среди k непересекающихся множеств T1, Т2, . Tk, и каждое их этих множеств, в свою очередь, является деревом. Деревья T1, Т2, . Tk называются поддеревьями (subtrees) этого корня.
Из этого определения следует, что каждый узел дерева является корнем некоторого другого дерева (поддерева).
Совокупность нескольких непересекающихся деревьев называется лесом (forest —иногда переводится как бор). Например, все потомки одного узла дерева образуют лес. Лес всегда можно преобразовать в дерево, добавив один единственный корневой элемент и связав его с корнями всех деревьев, из которых состоит лес. Поэтому лес и дерево — это два неразрывно сязанных понятия. Для того, чтобы подчеркнуть общность этих понятий, лес из n деревьев иногда называют деревом с n-кратным корнем.
3.2. Способы представления деревьев
Существует множество способов представления деревьев, одни из них используют двухмерные рисунки для наглядного отображения отношений иерархии, в других эти отношения удается отобразить и при помощи одномерного представления. Остановимся на наиболее часто используемых способах.
Рис.3.2. Графическое изображение дерева
Традиционно деревья изображают графически, располагая корень вверху (т. е. дерево растет вниз), как показано на рис. 3.2. Очевидно, такое представление связано с тем, что человеку привычнее рисовать и читать рисунок сверху вниз. Узлы дерева обычно изображают с помощью окружностей, соединяя каждый узел с его сыновьями линиями (связями). Связи обычно изображают без стрелки на конце.
Другим представлением может быть так называемый уступчатый список. На рис.3.3,а,б так представлено дерево из рис.3.2.
Рис.3.3. Представление дерева: а – в виде уступчатого списка; б – в виде “упрощенного”уступчатого списка
Здесь двухмерность рисунка поддерживается посредством отступов.
Более компактными являются одномерные способы изображения деревьев. Например, от списка с отступами можно легко перейти к десятичной системе обозначений Дьюи, которая используется в библиографии. Например, для нашего дерева она будет выглядеть так:
1.a, 1.1.b, 1.1.1.i, 1.1.2.j, 1.2.c, 1.2.1.h,
Другой вид одномерного представления дерева — это так называемая скобочная запись, в которой отношения иерархии представляются с помощью вложенности скобок. Один из возможных вариантов скобочной записи [8] для дерева (рис.3.2) выглядит так:
Можно немного сократить количество скобок:
a ( b ( i, j ), c ( h ), d ( e, f ( k ), g ) )
Такой способ называется левым скобочным представлением дерева, поскольку корень каждого поддерева расположен слева от скобки, открывающей список его поддеревьев. Возможны и другие способы перечисления порядка узлов, например, правое скобочное представление, в котором корень расположен справа. Заметим, что различные формы скобочного представления связаны с понятием обхода дерева, который будет подробно рассмотрен ниже.
В заключение упомянем еще один очень компактный способ представления деревьев, который основан на очень важном свойстве иерархической структуры. На рис. 3.2 хорошо видно, что дерево разветвляется от корня к листьям, т. е. каждый узел (кроме корня) имеет только один связанный с ним родительский (вышестоящий) узел. Из этого следует, что возможно такое простое представление дерева, в котором для каждого узла указана одна единственная ссылка на его родителя (для корня — пустая ссылка).
Например, представим дерево из рис. 3.2. в виде таблицы, содержащей для каждого узла обозначение его родителя. Для экономии места расположим таблицу горизонтально, хотя логичнее представить дерево в виде таблицы из двух столбцов— «узел»-«его родитель».
Предствление дерева из рис. 3.2 с помощью ссылок на родителей
Источник